# Cassini's Identity

Cassini's identity is named after [Grimaldi, p. 10] the French-born Italian astronomer and mathematician Giovanni Domenico (Jean Domenique) Cassini (1625-1712) who found it in 1680. It was later (1753) discovered independently by the Scottish mathematician and landscape artist Robert Simson (1687-1768).

Let $\{F_n\}$ be the sequence of Fibonacci numbers, defined as

$F_{0}=F_{1}=1, F_{n+1}=F_{n}+F_{n-1}, n \ge 1.$

Then, for $n \ge 1$,

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

Cassini's identity underlies a bewildering dissection known as Curry's Paradox. I'll give four proofs of this now famous result.

### Proof 1

The first one is by induction. Let's first check that the identity holds for $n=1$: indeed, for $n=1$, $2\cdot 1 - 1^{2}=1=1^{1+1}$.

Assume that the identity holds for some $n=k$, i.e., $F_{k+1}F_{k-1}-F_{k}^{2}=(-1)^{k+1}$ We want to show that also $F_{k+2}F_{k}-F_{k+1}^{2}=(-1)^{k+2}$. To this end, we are going to establish

$F_{k+2}F_{k}-F_{k+1}^{2}=F_{k}^{2} - F_{k+1}F_{k-1}$.

Here is how:

\begin{align} F_{k}^{2} - F_{k+1}F_{k-1} &= F_{k}^{2} + F_{k}F_{k-1}- F_{k}F_{k-1} - F_{k+1}F_{k-1} \\ &= F_{k+1}F_{k} - F_{k}F_{k-1} - F_{k+1}F_{k-1} \\ &= F_{k+1}F_{k} - 2F_{k}F_{k-1} - F_{k-1}^{2} \\ &= (F_{k+1} + F_{k})F_{k} - (F_{k}+F_{k-1})^2 \\ &= F_{k+2}F_{k}-F_{k+1}^{2}. \end{align}

### Proof 1'

Here is another (and shorter) proof by inducton. Assume Cassini's identity holds for some $n = k\gt 0$: $F_{k+1}F_{k-1}-F_{k}^{2}=(-1)^{k+1}.$ Substitute $F_{n-1}=F_{n+1}-F_{n}$ to obtain

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

This is the same as

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

And further

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

But this is exactly Cassini's identity for $n = k+1$.

### Proof 2

This proof employs Binet's formula:

$F_{n}=\frac{1}{\sqrt{5}}({\phi}^{n}-{\tau}^{n}),$

where $\phi=\frac{1+\sqrt{5}}{2}$ and $\tau=\frac{1-\sqrt{5}}{2}$, the golden section and its negative reciprocal: $\phi \tau = -1$. Also $\phi - \tau=\sqrt{5}$. We thus have

\begin{align} F_{n+1}F_{n-1}-F_{n}^{2} &= \frac{1}{5}[(\phi^{n+1} - \tau^{n+1})(\phi^{n-1} - \tau^{n-1}) - (\phi^{n} - \tau^{n})^2] \\ &= \frac{1}{5}[\phi^{n+1}\tau^{n-1}-\phi^{n-1}\tau^{n+1}+2\phi^{n}\tau^{n}] \\ &= \frac{1}{5}(\phi\tau)^{n-1}(\phi^{2} - 2\phi\tau +\tau^{2}) \\ &= \frac{1}{5}(-1)^{n-1}(\phi-\tau)^{2} \\ &= (-1)^{n+1}. \end{align}

### Proof 3

For this proof, we use a little linear algebra. Elsewhere we defined the matrix

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

Matrix $A$ satisfies the following

### Proposition

For $n \ge 1$,

$A^{n+1}=\left( \begin{array}{cc} F_{n-1} & F_{n} \\ F_{n} & F_{n+1} \end{array} \right)$.

An easy proof is by induction. For $n = 1$,

$A^{1+1}=\left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 2 \end{array} \right)$.

And then for $n=k+1$,

$A^{k+2}=\left( \begin{array}{cc} F_{k-1} & F_{k} \\ F_{k} & F_{k+1} \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right) = \left( \begin{array}{cc} F_{k} & F_{k-1}+F_{k} \\ F_{k+1} & F_{k}+F_{k+1} \end{array} \right) = \left( \begin{array}{cc} F_{k} & F_{k+1} \\ F_{k+1} & F_{k+2} \end{array} \right)$.

The determinant $\mbox{det}(X)$ of a $2 \times 2$ matrix $X=\left(\begin{array}{cc} a&b \\ c&d\end{array}\right)$ is defined as $\mbox{det}(X)=ad-bc$. For example, $\mbox{det}(A^{n+1})=F_{n-1}F_{n+1}-F_{n}^2$. Determinants have an important property, $\mbox{det}(XY)=\mbox{det}(X)\mbox{det}(Y)$. For matrix $A$, $\mbox{det}(A)=-1$, so that $\mbox{det}(A^{n+1})=(-1)^{n+1}$, immediately implying Cassini's identity.

### Proof 4

This is what is known as the bijective proof.

Define $A(n)= \{(a_1, \ldots , a_r): \space r\ge 0, \space a_i=1 \space\mbox{or}\space 2, \space a_{1} + \ldots +a_{r} = n\}$.

Then $|A(n)|=F_{n}$. Indeed, $|A(0)|=|A(1)|=1$ and $|A(n+1)|=|A(n)|+|A(n-1)|$, because $a_{r}$ is either $1$ or $2$. (This is pretty much the same as the argument in the combinatorial proof below.)

Let generically $e=(2,2,2,\ldots ,2)$; and define bijection

$A(n)\times A(n) \setminus (e,e) \rightarrow A(n-1)\times A(n+1) \setminus (e,e)$

as follows. Let $[(a_1, a_2, \ldots, a_r),(b_1, b_2, \ldots, b_s)]\in A(n)\times A(n)$ and look for the first $1$ in $a_1,b_1,a_2,b_2,\ldots$

Case 1: The first $1$ is an $a_k$. Delete $a_k = 1$ from the first vector and insert it between $b_{k-1}$ and $b_{k}$ in the second vector.

Case 2: The first $1$ is a $b_k$, (then $a_k = 2$). Exchange $a_k$ and $b_k$.

This completes the proof. (It's left to the reader to determine how much is removed on both sides by the operation $\setminus (e,e)$.)

### Proof 5

This proof makes use of combinatorial arguments. I placed it on a separate page.

### Generalization

A generalization of Cassini's identity was discovered in 1879 by the Belgian mathematician Eugène Charles Catalan (1814-1894). The identity now bears his name:

For integer $n$, $k$, $1 \le k \le n$,

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

Catalan's identity submits to a modification of Proof 2 above. Another genralization is due to the French mathematician Philbert Maurice d'Ocagne (1862-1938)

For integer $n \gt m$,

$F_{m}F_{n+1} - F_{m+1}F_{n}=(-1)^{n}F_{n-m}.$

### References

1. R. Grimaldi, Fibonacci and Catalan Numbers: an Introduction, Wiley, 2012
2. M. Werman, D. Zeilberger, A Bijective Proof of Cassini's Fibonacci Identity, Discrete Mathematics 58 (1986) 109 ### Fibonacci Numbers 