__notoc__
Cassini's identity (sometimes called Simson's identity), Catalan's identity and Vajda's identity are mathematical identities for the Fibonacci numbers. Cassini's identity, a special case of the other two, states that for the nth Fibonacci number,
:<math> F_{n-1}F_{n+1} - F_n^2 = (-1)^n.</math>
Note here <math> F_0 </math> is taken to be 0, and <math> F_1 </math> is taken to be 1.
Catalan's identity generalizes this to allow <math>r \neq 1</math>:
:<math>F_n^2 - F_{n-r}F_{n+r} = (-1)^{n-r}F_r^2.</math>
Vajda's identity further generalizes this to allow <math>m \neq n</math>:
:<math>F_m F_n - F_{m-r} F_{n+r} = \left({-1}\right)^{m-r} F_r F_{r+n-m},</math>
also written as:
:<math>F_{n+i}F_{n+j} - F_n F_{n+i+j} = (-1)^n F_i F_j.</math>
History
Cassini's formula was discovered in 1680 by Giovanni Domenico Cassini, then director of the Paris Observatory, and independently proven by Robert Simson (1753).
Catalan's identity is named after Eugène Catalan (1814–1894). It can be found in one of his private research notes, entitled "Sur la série de Lamé" and dated October 1879. However, the identity did not appear in print until December 1886 as part of his collected works . This explains why some give 1879 and others 1886 as the date for Catalan's identity .
The Hungarian-British mathematician Steven Vajda (1901–95) published a book on Fibonacci numbers (Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, 1989) which contains the identity carrying his name. However, the identity had been published earlier in 1960 by Dustan Everman as problem 1396 in The American Mathematical Monthly, and in 1901 by Alberto Tagiuri in Periodico di Matematica.
Proof of Cassini identity
Proof by matrix theory
A quick proof of Cassini's identity may be given by recognising the left side of the equation as a determinant of a 2×2 matrix of Fibonacci numbers. The result is almost immediate when the matrix is seen to be the th power of a matrix with determinant −1:
:<math>F_{n-1}F_{n+1} - F_n^2
=\det\left[\begin{matrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{matrix}\right]
=\det\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^n
=\left(\det\left[\begin{matrix}1&1\\1&0\end{matrix}\right]\right)^n
=(-1)^n.</math>
Proof by induction
Consider the induction statement:
:<math>F_{n-1}F_{n+1} - F_n^2 = (-1)^n</math>
The base case <math>n=1</math> is true.
Assume the statement is true for <math>n</math>. Then:
:<math>F_{n-1}F_{n+1} - F_n^2 + F_nF_{n+1} - F_nF_{n+1} = (-1)^n</math>
:<math>F_{n-1}F_{n+1} + F_nF_{n+1} - F_n^2 - F_nF_{n+1} = (-1)^n</math>
:<math>F_{n+1}(F_{n-1} + F_n) - F_n(F_n + F_{n+1}) = (-1)^n</math>
:<math>F_{n+1}^2 - F_nF_{n+2} = (-1)^n</math>
:<math>F_nF_{n+2} - F_{n+1}^2 = (-1)^{n+1}</math>
so the statement is true for all integers <math>n>0</math>.
Proof of Catalan identity
We use Binet's formula, that <math>F_n=\frac{\phi^n-\psi^n}{\sqrt5}</math>, where <math>\phi=\frac{1+\sqrt5}{2}</math> and <math>\psi=\frac{1-\sqrt5}{2}</math>.
Hence, <math>\phi+\psi=1</math> and <math>\phi\psi=-1</math>.
So,
:<math>5(F_n^2 - F_{n-r}F_{n+r})</math>
:<math>= (\phi^n-\psi^n)^2 - (\phi^{n-r}-\psi^{n-r})(\phi^{n+r}-\psi^{n+r})</math>
:<math>= (\phi^{2n} - 2\phi^{n}\psi^{n} +\psi^{2n}) - (\phi^{2n} - \phi^{n}\psi^{n}(\phi^{-r}\psi^{r}+\phi^{r}\psi^{-r}) + \psi^{2n})</math>
:<math>= - 2\phi^{n}\psi^{n} + \phi^{n}\psi^{n}(\phi^{-r}\psi^{r}+\phi^{r}\psi^{-r})</math>
Using <math>\phi\psi=-1</math>,
:<math>= -(-1)^n2 + (-1)^n(\phi^{-r}\psi^{r}+\phi^{r}\psi^{-r})</math>
and again as <math>\phi=\frac{-1}{\psi}</math>,
:<math>= -(-1)^n2 + (-1)^{n-r}(\psi^{2r}+\phi^{2r})</math>
The Lucas number <math>L_n</math> is defined as <math>L_n=\phi^n+\psi^n</math>, so
:<math>= -(-1)^n2 + (-1)^{n-r}L_{2r}</math>
Because <math>L_{2n} = 5 F_n^2 + 2(-1)^n</math>
:<math>= -(-1)^n2 + (-1)^{n-r}(5 F_r^2 + 2(-1)^r)</math>
:<math>= -(-1)^n2 + (-1)^{n-r}2(-1)^r + (-1)^{n-r}5 F_r^2</math>
:<math>= -(-1)^n2 + (-1)^n2 + (-1)^{n-r}5 F_r^2</math>
:<math>= (-1)^{n-r}5 F_r^2</math>
Cancelling the <math>5</math>'s gives the result.