Explaining the proof of Fibonacci number using inductive reasoning

Question

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.

Answer 1

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

Answer 2

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.