# Explaining the proof of Fibonacci number using inductive reasoning

Fibonacci numbers are defined as follows.

$$F_{1}= F_{2} = 1$$ When $$n \geq 3$$, $$F_{n} = F_{n-1} + F_{n-2}$$

Task: Prove the following statement using mathematical induction:

• When $$n \geq 2$$, $$F_{n-1}F_{n+1} = F_{n}^2 + (-1)^n$$

The Base Case:

The Inductive Step:

I'm really confused about the inductive step. The answer makes absolutely no sense to me.

Questions:

1. For the inductive step, why is the yellow area equal to the green area?
2. For the inductive step, how do we arrive at the purple and red statement?

I think the answer given to me is too simplified and doesn't demonstrate a clear logical reasoning.

• My apologies for anyone who is color blind. It's just easier for me to color code the statements. Dec 9, 2018 at 22:18

1. The green part is $$f^2(k)+f(k)f(k+1)=(f(k-1)+f(k))f(k+1)-(-1)^k=f^2(k+1)+(-1)^{k+1},$$ i.e. the yellow part. Note that it's not supposed to be obvious at this stage that green = yellow; that they are is what the subsequent lines show. The important part is that red = yellow; that's why the inductive step works. The way the proof of this actually starts is by rewriting $$f(k+2)$$ as a sum to get the green expression.
2. The purple part is equal to the line above it, by summing the coefficients of $$f(k+1)$$ and taking care with powers of $$-1$$. The red part rewrites the summed coefficient from the recursion relation, and then notes a square is present.
1. Because, by definition, $$f(k+2)=f(k+1)+f(k)$$.
2. First of all, $$-(-1)^k=(-1)\times(-1)^k=(-1)^{k+1}$$. Then,$$f(k)f(k+1)+f(k-1)f(k+1)=\bigl(f(k)+f(k-1)\bigr)f(k+1).$$So,$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=\bigl(f(k)+f(k-1)\bigr)f(k+1)+(-1)^{k+1}.\tag1$$But, by definition, $$f(k+1)=f(k)+f(k-1)$$. So, $$(1)$$ becomes$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=\bigl(f(k+1)\bigr)^2+(-1)^{k+1}.$$