# Fibonacci Proof by Induction

• Nov 14th 2012, 01:10 PM
Walshy
Fibonacci Proof by Induction
Assuming F represents the Fibonacci sequence, use mathematical induction to prove that for all integers n >= 0, Fsub(n+2)Fsub(n) − (Fsub(n+1))^2 = (−1)^n.

I have gotten to the inductive goal when plugging in k+1, but am lost from here.

Thanks.
• Nov 14th 2012, 01:33 PM
Re: Fibonacci Proof by Induction
Assuming, (after confirming base case)

Fk+2Fk − (F(k+1)2 = (−1)k. (Assumption P)

With the induction step, you want to prove

Fk+3Fk+1 - (Fk+2)2 = (-1)k+1

so,
(-1)k+1 = (-1)k*(-1)^1 = -1 * ( Fk+2Fk − (F(k+1)2 ) (by Assumption P)

Can you take it from here? I currently don't have pencil and paper handy to give you the full answer.

You'll probably also have to use the fact that Fk+2 = Fk + Fk+1
For simplicity, I would leave the bolded and then work in the other direction as well
In other words, working with Fk+3Fk+1 - (Fk+2)2 so that it's equal to what is in the bold, since A = B = C implies A = C
• Nov 14th 2012, 02:05 PM
Walshy
Re: Fibonacci Proof by Induction
Yeah that makes sense, thanks. I'm in the process of trying to figure out the rest, will update.
• Nov 14th 2012, 02:19 PM
Re: Fibonacci Proof by Induction
I look forward to it. This problem did look very familiar from a number theory course I took.
• Nov 14th 2012, 03:33 PM
Walshy
Re: Fibonacci Proof by Induction
Yeah i figured it out. Thanks for all the help.
• Nov 14th 2012, 03:36 PM