Cassini and Catalan identities

Cassini's identity (sometimes called Simson's identity) and Catalan's identity are mathematical identities for the Fibonacci numbers. Cassini's identity, a special case of Catalan's identity, states that for the nth Fibonacci number,

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

Catalan's identity generalizes this:

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

Vajda's identity generalizes this:

${\displaystyle F_{n+i}F_{n+j}-F_{n}F_{n+i+j}=(-1)^{n}F_{i}F_{j}.}$

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).^[1] However Johannes Kepler presumably knew the identity already in 1608.^[2] Eugène Charles Catalan found the identity named after him in 1879.^[1] The 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.^[3][4] However the identity was already published in 1960 by Dustan Everman as problem 1396 in The American Mathematical Monthly.^[1]

Proof of Cassini identity[]

Proof by matrix theory[]

A quick proof of Cassini's identity may be given (Knuth 1997, p. 81) 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 nth power of a matrix with determinant −1:

${\displaystyle 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}.}$

Proof by induction[]

Consider the induction statement:

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

The base case ${\displaystyle n=1}$ is true.

Assume the statement is true for ${\displaystyle n}$. Then:

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

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

${\displaystyle F_{n+1}(F_{n-1}+F_{n})-F_{n}(F_{n}+F_{n+1})=(-1)^{n}}$

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

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

so the statement is true for all integers ${\displaystyle n>0}$.

Proof of Catalan identity[]

We use Binet's Theorem, that ${\displaystyle F_{n}={\frac {\phi ^{n}-\psi ^{n}}{\sqrt {5}}}}$, where ${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}}$ and ${\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}}$.

Hence, ${\displaystyle \phi +\psi =1}$ and ${\displaystyle \phi \psi =-1}$.

So,

${\displaystyle 5(F_{n}^{2}-F_{n-r}F_{n+r})}$

${\displaystyle =(\phi ^{n}-\psi ^{n})^{2}-(\phi ^{n-r}-\psi ^{n-r})(\phi ^{n+r}-\psi ^{n+r})}$

${\displaystyle =(\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})}$

${\displaystyle =-2\phi ^{n}\psi ^{n}+\phi ^{n}\psi ^{n}(\phi ^{-r}\psi ^{r}+\phi ^{r}\psi ^{-r})}$

Using ${\displaystyle \phi \psi =-1}$,

${\displaystyle =-(-1)^{n}2+(-1)^{n}(\phi ^{-r}\psi ^{r}+\phi ^{r}\psi ^{-r})}$

and again as ${\displaystyle \phi ={\frac {-1}{\psi }}}$,

${\displaystyle =-(-1)^{n}2+(-1)^{n-r}(\psi ^{2r}+\phi ^{2r})}$

The Lucas number ${\displaystyle L_{n}}$ is defined as ${\displaystyle L_{n}=\phi ^{n}+\psi ^{n}}$, so

${\displaystyle =-(-1)^{n}2+(-1)^{n-r}L_{2r}}$

Because ${\displaystyle L_{2n}=5F_{n}^{2}+2(-1)^{n}}$

${\displaystyle =-(-1)^{n}2+(-1)^{n-r}(5F_{r}^{2}+2(-1)^{r})}$

${\displaystyle =-(-1)^{n}2+(-1)^{n-r}2(-1)^{r}+(-1)^{n-r}5F_{r}^{2}}$

${\displaystyle =-(-1)^{n}2+(-1)^{n}2+(-1)^{n-r}5F_{r}^{2}}$

${\displaystyle =(-1)^{n-r}5F_{r}^{2}}$

Cancelling the ${\displaystyle 5}$'s gives the result.

Notes[]

References[]

• Knuth, Donald Ervin (1997), The Art of Computer Programming, Volume 1: Fundamental Algorithms, The Art of Computer Programming, 1 (3rd ed.), Reading, Mass: Addison-Wesley, ISBN 0-201-89683-4

• Simson, R. (1753). "An Explication of an Obscure Passage in Albert Girard's Commentary upon Simon Stevin's Works". Philosophical Transactions of the Royal Society of London. 48: 368–376. doi:10.1098/rstl.1753.0056.

• Werman, M.; Zeilberger, D. (1986). "A bijective proof of Cassini's Fibonacci identity". Discrete Mathematics. 58 (1): 109. doi:10.1016/0012-365X(86)90194-9. MR 0820846.

External links[]

• Proof of Cassini's identity
• Proof of Catalan's Identity
• Cassini formula for Fibonacci numbers
• Fibonacci and Phi Formulae