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

  1. Ceva's Theorem: A Matter of Appreciation
  2. When the Counting Gets Tough, the Tough Count on Mathematics
  3. I. Sharygin's Problem of Criminal Ministers
  4. Single Pile Games
  5. Take-Away Games
  6. Number 8 Is Interesting
  7. Curry's Paradox
  8. A Problem in Checker-Jumping
  9. Fibonacci's Quickies
  10. Fibonacci Numbers in Equilateral Triangle
  11. Binet's Formula by Inducion
  12. Binet's Formula via Generating Functions
  13. Generating Functions from Recurrences
  14. Cassini's Identity
  15. Fibonacci Idendtities with Matrices
  16. GCD of Fibonacci Numbers
  17. Binet's Formula with Cosines
  18. Lame's Theorem - First Application of Fibonacci Numbers

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

 62628905

Search by google: