Proof by induction

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• May 28th 2006, 10:02 AM
ThePerfectHacker
You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.
• May 28th 2006, 03:43 PM
Natasha1
Quote:

Originally Posted by ThePerfectHacker
You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.

I'm so rubbish at the induction proof. Could someone just show me what I need to do? It's due in for tomorrow please
• May 28th 2006, 04:40 PM
Natasha1
Is this better???

Step 1: For n = 1, we have

$\displaystyle (F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1$

Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

$\displaystyle (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

$\displaystyle (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$

Since there is a $\displaystyle k\geq 2$ such as,
$\displaystyle F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}$
Then proof it hold for $\displaystyle k+1$. But the expression,
$\displaystyle F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))$
But,
$\displaystyle F(k)^2-F(k+1)(k-1)=(-1)^{k-1}$
Thus,
$\displaystyle F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k$
Thus, it hold true for $\displaystyle k+1$.

$\displaystyle (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$

Hence the equation holds true for n = k + 1
• May 29th 2006, 12:58 AM
CaptainBlack
Quote:

Originally Posted by Natasha1
Is this better???

Step 1: For n = 1, we have

$\displaystyle (F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1$

Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

$\displaystyle (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

$\displaystyle F_{k+1} F_{k+3} - (F_{k+2})^2 =$$\displaystyle F_{k+1} (F_{k+2}+F_{k+1}) - (F_{k+2})^2 \displaystyle =F_{k+1} F_{k+2}+(F_{k+1})^2 - (F_{k+2})^2. Now: \displaystyle F_{k+1}=F_{k+2}-F_{k}, so: \displaystyle F_{k+1} F_{k+3} - (F_{k+2})^2=$$\displaystyle (F_{k+2}-F_{k}) F_{k+2}+(F_{k+1})^2 - (F_{k+2})^2$

$\displaystyle =-F_{k} F_{k+2}+(F_{k+1})^2=-1((F_k \cdot F_{k+2}) - (F_{k+1})^2)=(-1)^{k+2}$
.

Which proves that if the statement is true for $\displaystyle k$ it is true for
$\displaystyle k+1$.

RonL
• May 29th 2006, 06:48 AM
Soroban
Hello, Natasha!

An inductive proof requires some world-class acrobatics . . .

Quote:

I need to prove by induction that for the Fibonacci sequence:

$\displaystyle (F_n)\cdot(F_{n+2}) - (F_{n+1})^2 \;= \;(-1)^{n+1}$ . . . $\displaystyle F_n$ being a Fibonacci number

Verify $\displaystyle S(1):\;\;(F_1)\cdot(F_3) - (F_2)^2 \:=\:(-1)^2\quad\Rightarrow\quad 1\cdot2 - 1^2\:=\:1$ . . . yes!

Assume $\displaystyle S(k)$ is true: .$\displaystyle (F_k)(F_{k+2}) - (F_{k+1})^2\;=\;(-1)^{k+1}$

. . and we will try to prove $\displaystyle S(k+1)\:=\:(F_{k+1})(F_{k+3}) - (F_{k+2})^2\:=\:(-1)^{k+2}$

Since $\displaystyle F_k\,=\,F_{k+2} - F_{k+1}$ and $\displaystyle F_{k+2} \,=\,F_{k+3} - F_{k+1}$

$\displaystyle S(k)$ becomes: $\displaystyle (F_{k+2} - F_{k+1})(F_{k+3} - F_{k+1}) - (F_{k+1})^2 \;= \;(-1)^{k+1}$

Expand: $\displaystyle (F_{k+2})(F_{k+3}) - (F_{k+1})(F_{k+2}) - (F_{k+1})(F_{k+3}) + (F_{k+1})^2 -$$\displaystyle (F_{k+1})^2\;=\;(-1)^{k+1}$

We have: $\displaystyle (F_{k+2})(F_{k+3}) - (F_{k+1})(F_{k+2}) - (F_{k+1})(F_{k+3}) \;= \; (-1)^{k+1}$

Factor: $\displaystyle (F_{k+2})\cdot(\underbrace{F_{k+3} - F_{k+1}}) - (F_{k+1})(F_{k+3}) \;= \; (-1)^{k+1}$
. . . . . . . . . . .This is $\displaystyle F_{k+2}$

An we have: $\displaystyle (F_{k+2})^2 - (F_{k+1})(F_{k+3}) \;=\;(-1)^{k+1}$

Multiply by $\displaystyle -1:\;\;(F_{k+1})(F_{k+3}) - (F_{k+2})^2\;=\;(-1)^{k+2}$

. . . ta-DAA! . . . This is $\displaystyle S(k+1)\;!$

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12