# Fibonacci numbers and proof by induction

Consider the Fibonacci numbers $F(0) = 0; F(1)=1; F(n) = F(n-1) + F(n-2)$.

Prove by induction that for all $n>0$,

$$F(n-1)\cdot F(n+1)- F(n)^2 = (-1)^n$$

I assume $P(n)$ is true and try to show $P(n+1)$ is true, but I got stuck with the algebra. How do we reach $P(n+1)$ from $P(n)$? Also, strong induction may be used instead.

-

Here is a pretty alternative proof (though ultimately the same), suggested by the determinant-like form of the claim. Let

$$M_n = \left(\begin{array}{cc} F(n+1) & F(n)\\ F(n) & F(n-1)\end{array}\right),$$

and note that

$$M_1 = \left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right),$$

and

$$M_{n+1} = \left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right) M_n.$$

It follows by induction that

$$M_n = \left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)^n.$$

Taking determinants (and using $\det(A^n) = \det(A)^n$) now gives the result.

-

Assume $F(n-1)F(n+1)-F(n)^2=(-1)^n$.

It is important to know what success will look like, so: We want to prove that $F(n)F(n+2)-F(n+1)^2=(-1)^{n+1}$. Immediately, this suggests to me that we should use our induction hypothesis right away, so substituting for $(-1)^n$ on the right we have that success will look like:

$F(n)F(n+2)-F(n+1)^2=F(n)^2-F(n-1)F(n+1)$

Note that we have not shown that this is true yet, this is the goal. Use the definitions of $F$ to get there: $F(n+2)=F(n+1)+F(n)$ and $F(n+1)=F(n)+F(n-1)$. Substituting this into $$F(n)F(n+2)-F(n+1)^2$$, we have $$F(n)F(n+2)-F(n+1)^2=\\F(n)[F(n+1)+F(n)]-F(n+1)[F(n)-F(n-1)]=\\F(n)^2-F(n+1)F(n-1)$$

Which is what we said success would look like! Now this is not really the proof, this is the scratch work for the proof. Take these steps and apply them backwards to write the actual proof.

Note that strong induction was not needed.

-

HINT: $F(n)F(n+2) - F(n+1)^2 = F(n)(F(n+1)+F(n)) - F(n+1)(F(n)+F(n-1))$.

-