Fibonacci identity: $f_{n+1}f_{n-1} = f_n^2 + (-1)^n$

Solution 1:

Here's a slick proof using a determinant (turns out this is the same as given in the link by Aretino).

First we prove $$\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^n=\left[\begin{matrix}f_{n+1}&f_n\\f_n&f_{n-1}\end{matrix}\right]$$

This is easy enough via induction. The base case $n=1$ holds (when we also add the definition $f_0=0$). Now assuming it holds for $n=k$, we have

$$\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^{k+1}=\left[\begin{matrix}f_{k+1}&f_k\\f_k&f_{k-1}\end{matrix}\right]\left[\begin{matrix}1&1\\1&0\end{matrix}\right]=\left[\begin{matrix}f_{k+1}+f_k&f_{k+1}\\f_{k}+f_{k-1}&f_k\end{matrix}\right]=\left[\begin{matrix}f_{k+2}&f_{k+1}\\f_{k+1}&f_k\end{matrix}\right]$$ as desired.

Now we just take a determinant! $$\begin{align}&\det\left(\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^n\right)=\det\left( \left[\begin{matrix}f_{n+1}&f_n\\f_n&f_{n-1}\end{matrix}\right]\right) \\\implies&\det\left(\left[\begin{matrix}1&1\\1&0\end{matrix}\right]\right)^n=f_{n+1}f_{n-1}-f_n^2 \\\implies&(-1)^n=f_{n+1}f_{n-1}-f_n^2 \end{align}$$

Rearranging gives us the result $$f_{n+1}f_{n-1}=f_n^2+(-1)^n$$

Solution 2:

The identity you have given actually has a name (Cassini's Identity). Now, for any $n\geq 1$, let $S(n)$ denote the statement $$ S(n) : F_{n-1}F_{n+1} = F_n^2+(-1)^n. $$ Base step ($n=1$): $S(1)$ says that $F_0F_2=F_1-1$ and this is true since both sides equal zero.

Inductive step: For some fixed $k\geq 1$, suppose that $$ S(k) : F_{k-1}F_{k+1} = F_k^2+(-1)^k $$ holds. To be proved is that $$ S(k+1) : F_{k}F_{k+2} = F_{k+1}^2+(-1)^{k+1}. $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} F_kF_{k+2}&= F_k(F_k+F_{k+1})\\[0.5em] &= F_k^2+F_kF_{k+1}\\[0.5em] &= (F_{k-1}F_{k+1}-(1)^k)+F_kF_{k+1}\tag{by $S(k)$}\\[0.5em] &= (F_{k-1}+F_k)F_{k+1}-(-1)^k\\[0.5em] &= F_{k+1}F_{k+1}-(-1)^k\\[0.5em] &= F_{k+1}^2+(-1)^{k+1}. \end{align} we end up with the right-hand side of $S(k+1)$, completing the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

Solution 3:

This is a special case of Catalan's Identity where r=1 in

$f_{n+1}\,f_{n-1}=f_n^2 - \left(-1\right)^{n-r}f_r^2$

Proof can be found here.

Solution 4:

Here is a proof by induction (since you tagged it).

First of all, the statement doesn't make sense for $n=1$, so I'm assuming you are tasked with proving it for $n\geq 2$. To establish the base case note that when $n=2$ we have that $$f_3f_1=2\cdot1=f_2^2+(-1)^2.$$

Now assume (for induction) that the result it true for $n-1$. Then in particular we have $$f_{n-1}^2=f_{n}f_{n-2}-(-1)^{n-1}=f_{n}f_{n-2}+(-1)^{n}.$$ Using this and the fact that $f_{n+2}=f_{n+1}+f_{n-1}$ we have $$f_{n+1}f_{n-1}=(f_{n}+f_{n-1})f_{n-1}=f_nf_{n-1}+f_{n-1}^2=f_nf_{n-1}+f_{n}f_{n-2}+(-1)^n$$ $$=f_{n}(f_{n-1}+f_{n-2})+(-1)^n=f_n^2+(-1)^n,$$ which is the result.

Solution 5:

This is not something that you "see", but rather something that you discover while fiddling with Fibonacci numbers and asking yourself "I wonder if there is a relationship between ... and ...?".

The way that you see it is just by creating a table of some quantities that you have been "fiddling" with

$$\begin{array}{cccc} k&f_k&f_{k-1}f_{k+1}&f_{k}^2\\ 0&0&&\\ 1&1&0&1\\ 2&1&2&1\\ 3&2&3&4\\ 4&3&10&9\\ 5&5&24&25\\ 6&8&65&64\\ 7&13&168&169\\ 8&21&442&441\\ 9&34&1155&1156\\ 10&55&&\\ \end{array} $$

It's not difficult to see the pattern.