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

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

Fibonacci Numbers

Golden Ratio in Geometry

71536390