Cassini's Identity

Theorem

Let $F_k$ be the $k$th Fibonacci number.

Then $F_{n+1}F_{n-1} - F_n^2 = \left({-1}\right)^n$.

This is also sometimes reported (slightly less elegantly) as $F_{n+1}^2 - F_n F_{n+2} = \left({-1}\right)^n$

Proof

We see that $F_2 F_0 - F_1^2 = 1 \times 0 - 1 = -1 = \left({-1}\right)^1$, so the proposition holds for $n=1$.

We also see that $F_3 F_1 - F_2^2 = 2 \times 1 - 1 = \left({-1}\right)^2$, so the proposition holds for $n=2$.

Suppose the proposition is true for $n=k$, that is, $F_{k+1}F_{k-1} - F_k^2 = \left({-1}\right)^k$.

We now see whether we can show that it follows from this that the proposition is true for $n=k+1$, that is, $F_{k+2}F_k - F_{k+1}^2 = \left({-1}\right)^{k+1}$.

So:

$\begin{align} F_{k+2} F_k - F_{k+1}^2 & = \left({F_k + F_{k+1}}\right) F_k - F_{k+1}^2 \\ & = F_k^2 + F_k F_{k+1} - F_{k+1}^2 \\ & = F_k^2 + F_k F_{k+1} - F_{k+1} \left({F_k + F_{k-1}}\right) \\ & = F_k^2 + F_k F_{k+1} - F_k F_{k+1} - F_{k+1} F_{k-1} \\ & = F_k^2 - F_{k+1} F_{k-1} \\ & = \left({-1}\right) \left({F_{k+1} F_{k-1} - F_k^2}\right) \\ & = \left({-1}\right) \left({-1}\right)^k \\ & = \left({-1}\right)^{k+1} \\ \end{align}$

So by the principle of mathematical induction, the proof is complete.

$\blacksquare$

Note that from the above we have that $F_{k+2} F_k - F_{k+1}^2 = \left({-1}\right)^{k+1}$ from which $F_{n+1}^2 - F_n F_{n+2} = \left({-1}\right)^n$ follows immediately.

Proof using Matrices

The same thing can be proved more elegantly by starting with the proof by induction of this identity:

$\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$

and then taking the determinant of both sides.

Base case:

$\begin{bmatrix} F_2 & F_1 \\ F_1 & F_0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^1$

Induction hypothesis:

$\begin{bmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^k$

The induction step follows from conventional matrix multiplication:

$\begin{bmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} F_{k+1} + F_k & F_{k+1} \\ F_k + F_{k-1} & F_k \end{bmatrix} = \begin{bmatrix} F_{k+2} & F_{k+1} \\ F_{k+1} & F_k \end{bmatrix}$

So by induction:

$ \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n $

Now we calculate the determinants:

The LHS follows directly from the order 2 determinant:

$\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} = F_{n+1} F_{n-1} - F_n^2$

Now for the RHS:

Base case:

$\begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix} = 1 \times 0 - 1 \times 1 = -1 = \left({-1}\right)^1$

Induction hypothesis:

$\begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^k = \left({-1}\right)^k$

The induction step follows from Determinant of Matrix Product:

$\begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^{k+1} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^k \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix} = \left({-1}\right)^k \left({-1}\right) = \left({-1}\right)^{k+1}$

Hence the result by induction.

Source of Name

This entry was named for Giovanni Domenico Cassini.

He first published it in 1680.

However, it had been mentioned as early as 1608 in a letter by Johannes Kepler.

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968) $\S 1.2.8 \ (4), \ (5)$, also Exercise $6$
• George E. Andrews: Number Theory (1971): $\S 1.1$: Exercise $10$