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

Assuming, (after confirming base case)

F_k+2F_k − (F_(k+1)² = (−1)^k. (Assumption P)

With the induction step, you want to prove

F_k+3F_k+1 - (F_k+2)² = (-1)^k+1

so,
(-1)^k+1 = (-1)^k*(-1)^1 = -1 * ( F_k+2F_k − (F_(k+1)² ) (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 F_k+2 = F_k + F_k+1
For simplicity, I would leave the bolded and then work in the other direction as well
In other words, working with F_k+3F_k+1 - (F_k+2)² so that it's equal to what is in the bold, since A = B = C implies A = C

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

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

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

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

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.