Induction proof on Fibonacci sequence: $F(n-1) \cdot F(n+1) - F(n)^2 = (-1)^n$

Solution 1:

Just to be contrary, here's a (more instructive?) proof that isn't directly by induction:

Lemma. Let $A$ be the $2\times 2$ matrix $\begin{pmatrix}1&1\\1&0\end{pmatrix}$. Then $A^n= \begin{pmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix}$ for every $n\ge 1$.

This can be proved by induction on $n$ since $$A\begin{pmatrix}F_n & F_{n-1} \\ F_{n-1} & F_{n-2}\end{pmatrix} = \begin{pmatrix}F_n+F_{n-1} & F_{n-1}+F_{n-2} \\ F_n & F_{n-1}\end{pmatrix} = \begin{pmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{pmatrix}$$

Now, $F_{n+1}F_{n-1}-F_n^2$ is simply the determinant of $A^n$, which is $(-1)^n$ because the determinant of $A$ is $-1$.

Solution 2:

Basis: $n = 1$

$$F_{n-1} \cdot F_{n+1} - F_{n}^2 = (-1)^n$$ $$F_{0} \cdot F_{2} - F_{1}^2 = (-1)^n$$ $$0 \cdot 1 - 1 = -1$$ $$-1 = -1 \text{, which is true}$$

Inductive hypothesis: $n=k$

We assume that the statement holds for some number $k$

$$F_{k-1} \cdot F_{k+1} - F_{k}^2 = (-1)^k$$

Inductive step: $n = k+1$

We need to prove that the following statement holds:

$$F_{k} \cdot F_{k+2} - F_{k+1}^2 = (-1)^{k+1}$$

Starting from the inductive hypothesis we have:

$$F_{k-1} \cdot F_{k+1} - F_{k}^2 = (-1)^k$$

Multiply both sides by $-1$:

$$F_{k}^2 - F_{k-1} \cdot F_{k+1}= (-1)^{k+1}$$

Using the property on Fibonacci numbers we have:

$$F_{k}^2 - (F_{k+1} - F_{k}) \cdot F_{k+1}= (-1)^{k+1}$$

$$F_{k}^2 + F_{k} \cdot F_{k+1} - F_{k+1}^2 = (-1)^{k+1}$$

$$F_{k}(F_{k} + F_{k+1}) - F_{k+1}^2 = (-1)^{k+1}$$

$$F_{k} \cdot F_{k+2} - F_{k+1}^2 = (-1)^{k+1}$$

Q.E.D.

Note that his identity is called Cassini identity for Fibonacci Numbers, which is a generalization of the Catalan identity for Fibonacci Numbers, which states:

$$F_n^2 -F_{n-r}F_{n+r} = (-1)^{n-r}F_r^2$$

Solution 3:

You have written the wrong Fibonacci number as a sum. You know something about $F_{n-1},\, F_n$ and $F_{n+1}$ by the induction hypothesis, while $F_{n+2}$ is new. So you should write $F_{n+2} = F_{n+1} + F_n$. And in the other summand, write one factor too as a sum,

$$F_n\cdot F_{n+2} - F_{n+1}^2 = F_n(F_{n+1} + F_n) - F_{n+1}(F_n + F_{n-1})$$

can be easily and fruitfully related to the induction hypothesis.