# Cassini and Catalan identities

https://en.wikipedia.org/wiki/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 \phi ={\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

1. ^ a b c Thomas Koshy: Fibonacci and Lucas Numbers with Applications. Wiley, 2001, ISBN  9781118031315, pp. 74-75, 83, 88
2. ^ Miodrag Petkovic: Famous Puzzles of Great Mathematicians. AMS, 2009, ISBN  9780821848142, S. 30-31
3. ^ Douglas B. West: Combinatorial Mathematics. Cambridge University Press, 2020, p. 61
4. ^ Steven Vadja: Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications. Dover, 2008, ISBN  978-0486462769, p. 28 (original publication 1989 at Ellis Horwood)