# Thread: Fibonacci Proof by Induction

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

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

3. ## Re: Fibonacci Proof by Induction

Yeah that makes sense, thanks. I'm in the process of trying to figure out the rest, will update.

4. ## Re: Fibonacci Proof by Induction

I look forward to it. This problem did look very familiar from a number theory course I took.

5. ## Re: Fibonacci Proof by Induction

Yeah i figured it out. Thanks for all the help.

6. ## Re: Fibonacci Proof by Induction

No problem. By curiosity was there anything I missed noting that helped you solve the problem?

7. ## Re: Fibonacci Proof by Induction

No i don't think so. Your explanation was very thorough, and as u said, u didnt have a pencil and paper to work out the last part, but that wasn't too bad.