# Proof by induction

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• May 26th 2006, 08:44 AM
Natasha1
Proof by induction
I need to proove by induction that for the Fibonacci sequence

(Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1

Fn being a Fibonacci number

Is there anyone capable of doing this or know where on the internet I can find it. I have spent over 1 hrs trying to find something, without success.
• May 26th 2006, 08:47 AM
ThePerfectHacker
Quote:

Originally Posted by Natasha1
I need to proove by induction that for the fibonacci sequence

(Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1

Is there anyone capable of doing this or know where on the internet I can find it. I have spent over 1 hrs trying to find something, without success.

Something is wrong because $n=1$
$F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0$
• May 26th 2006, 09:01 AM
Natasha1
Quote:

Originally Posted by ThePerfectHacker
Something is wrong because $n=1$
$F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0$

This formula shows that for even Fib numbers you get -1 and odd ones you get +1
• May 26th 2006, 09:05 AM
ThePerfectHacker
Quote:

Originally Posted by Natasha1
This formula shows that for even Fib numbers you get -1 and odd ones you get +1

But the formula is clearly wrong.
Unless you want to say, that starting with some value for $n$ it is correct, for example, $n>1$. I believe I have seen this identity somewhere and will search through my book if I can find it. Then possibly posts their proof.
• May 26th 2006, 09:35 AM
Natasha1
What I am trying to say is:

1, 1, 2, 3, 5, 8, 13.....

if you do take f1*f3 - f2^2 you get 1
for the next in the series f2 you get f2*f4 - f3^2 you get -1

What I'm saying is that you keep having 1, -1, 1, -1 for ever.... and i need to proove that. Can't find it on the net?
• May 26th 2006, 09:35 AM
rgep
Quote:

(Fn * Fn+2) - (Fn+1)^2 = (-1)^n+1
Presumably should be read as $(F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}$. I assume the convention F0 = 0, F1 = 1, so that F2 = 1: in that case the inductive hypothesis is correct for n=0.
• May 26th 2006, 09:36 AM
Natasha1
Quote:

Originally Posted by rgep
Presumably should be read as $(F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}$. I assume the convention F0 = 0, F1 = 1, so that F2 = 1: in that case the inductive hypothesis is correct for n=0.

rgep you are spot on!
• May 26th 2006, 10:12 AM
ThePerfectHacker
Okay,
$F(n)^2-F(n+1)F(n-1)$= $F(n)(F(n-1)+F(n-2))-F(n+1)F(n-1)$*
$=F(n)F(n-1)+F(n)F(n-2)-F(n+1)F(n-1)$
$=(F(n)-F(n+1))F(n-1)+F(n)F(n+2)$
$=(-1)(F(n-1)^2-F(n)F(n-2))$*
*)Used the fibonacci recrusion formula,

Thus,
$F(n)^2-F(n+1)F(n-1)$= $(-1)(F(n-1)^2-F(n)F(n-2))$
Note, the subscripts decrease by one with a negative in front.
Thus,
$(-1)(F(n-1)^2-F(n)F(n-2))$= $(-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Thus,
$F(n)^2-F(n+1)F(n-1)$= $(-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Countinuing this $n-2$ times we have,
$F(n)^2-F(n+1)F(n-1)$= $(-1)^{n-2}(F(2)^2-F(3)F(1))$= $(-1)^{n-2}(-1)=(-1)^{n-1}$

Q.E.D.
• May 26th 2006, 10:21 AM
Natasha1
Quote:

Originally Posted by ThePerfectHacker
Okay,
$F(n)^2-F(n+1)F(n-1)$= $F(n)(F(n-1)+F(n-2))-F(n+1)F(n-1)$*
$=F(n)F(n-1)+F(n)F(n-2)-F(n+1)F(n-1)$
$=(F(n)-F(n+1))F(n-1)+F(n)F(n+2)$
$=(-1)(F(n-1)^2-F(n)F(n-2))$*
*)Used the fibonacci recrusion formula,

Thus,
$F(n)^2-F(n+1)F(n-1)$= $(-1)(F(n-1)^2-F(n)F(n-2))$
Note, the subscripts decrease by one with a negative in front.
Thus,
$(-1)(F(n-1)^2-F(n)F(n-2))$= $(-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Thus,
$F(n)^2-F(n+1)F(n-1)$= $(-1)^2(F(n-2)^2-F(n-1)F(n-3))$
Countinuing this $n-2$ times we have,
$F(n)^2-F(n+1)F(n-1)$= $(-1)^{n-2}(F(2)^2-F(3)F(1))$= $(-1)^{n-2}(-1)=(-1)^{n-1}$

Q.E.D.

Here's a virtual kiss x :-). By the way the recursive formula is fn = fn-1 + fn-2, for n = 2, 3, 4, ... where f0 =1, f1 = 1, no?. Which would make this invalid as f0 = 0, f1 = 1, so that f2 = 1
• May 26th 2006, 10:23 AM
ThePerfectHacker
Quote:

Originally Posted by Natasha1
Here's a virtual kiss x :-). By the way the recursive formula is fn = fn-1 + fn-2, for n = 2, 3, 4, ... where f0 =1, f1 = 1, no?. Which would make this invalid as f0 = 0, f1 = 1, so that f2 = 1

f0 is not used here,
f1=1
f2=1
f3=2
....
• May 26th 2006, 10:24 AM
Natasha1
is this an induction proof?
• May 26th 2006, 10:30 AM
ThePerfectHacker
Quote:

Originally Posted by Natasha1
is this an induction proof?

Not really.
--
You can turn it into an induction proof.

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))$ as explained in my other proof. 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$ and the proof is complete.
• May 26th 2006, 10:39 AM
earboth
Quote:

Originally Posted by ThePerfectHacker
Something is wrong because $n=1$
$F(1)F(3)-(F(2))^2=2-1=2=(-1)^1+1=0$

Hello,

$F(1)F(3)-(F(2))^2=\underbrace{2-1=2}_\csub{\mbox{That looks a little bit funny to me}}...$

and that's exactly $(-1)^{1+1}$ as it is given with the formula.

Greetings

EB
• May 26th 2006, 10:41 AM
ThePerfectHacker
Quote:

Originally Posted by earboth
Hello,

$F(1)F(3)-(F(2))^2=\underbrace{2-1=2}_\csub{\mbox{That looks a little bit funny to me}}...$

and that's exactly $(-1)^{1+1}$ as it is given with the formula.

Greetings

EB

:( I guess I never will win the Fields Medal.

That is why I never get 100 on tests.
• May 28th 2006, 01:28 AM
Natasha1
Could someone please add the extra couple of lines for me, I'm a little stuck, Thanks!

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}$

So we have:

$(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$
$(F_k \cdot F_{k+2}) - (F_{k+1})^2 + k+1= (-1)^{k+1} + k+1$
Could someone write what goes here please?
.
.
$(F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$

Hence the equation holds true for n = k + 1
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last