Thread: 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.

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

Originally Posted by ThePerfectHacker

Something is wrong because

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

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 it is correct, for example, . I believe I have seen this identity somewhere and will search through my book if I can find it. Then possibly posts their proof.

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?

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

Presumably should be read as . I assume the convention F0 = 0, F1 = 1, so that F2 = 1: in that case the inductive hypothesis is correct for n=0.

Originally Posted by rgep

Presumably should be read as . 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!

Okay,
= *


*
*)Used the fibonacci recrusion formula,

Thus,
=
Note, the subscripts decrease by one with a negative in front.
Thus,
=
Thus,
=
Countinuing this times we have,
= =

Q.E.D.

Originally Posted by ThePerfectHacker

Okay,
= *


*
*)Used the fibonacci recrusion formula,

Thus,
=
Note, the subscripts decrease by one with a negative in front.
Thus,
=
Thus,
=
Countinuing this times we have,
= =

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

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
....

is this an induction proof?

Originally Posted by Natasha1

is this an induction proof?

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

Since there is a such as,

Then proof it hold for . But the expression,
as explained in my other proof. But,

Thus,

Thus, it hold true for and the proof is complete.

Originally Posted by ThePerfectHacker

Something is wrong because

Hello,



and that's exactly as it is given with the formula.

Greetings

EB

Originally Posted by earboth

Hello,



and that's exactly 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.

Could someone please add the extra couple of lines for me, I'm a little stuck, Thanks!

Step 1: For n = 1, we have





Hence the equation holds for n = 1

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



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:



So we have:



Could someone write what goes here please?
.
.


Hence the equation holds true for n = k + 1