# Proof by induction

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• May 28th 2006, 11: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, 04: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, 05:40 PM
Natasha1
Is this better???

Step 1: For n = 1, we have

$(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:

$(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:

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

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

$(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, 01:58 AM
CaptainBlack
Quote:

Originally Posted by Natasha1
Is this better???

Step 1: For n = 1, we have

$(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:

$(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:

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

$=F_{k+1} F_{k+2}+(F_{k+1})^2 - (F_{k+2})^2$.

Now:

$F_{k+1}=F_{k+2}-F_{k}$,

so:

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

$=-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 $k$ it is true for
$k+1$.

RonL
• May 29th 2006, 07: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:

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

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

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

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

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

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

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

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

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

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

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

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

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