Cassini and Catalan identities
Cassini'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,
Catalan's identity generalizes this:
Vajda's identity generalizes this:
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). Eugène Charles Catalan found the identity named after him in 1879.
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}.}](https://wikimedia.org/enwiki/api/rest_v1/media/math/render/svg/d33c58ed530977ce60f18c7a87e3aa18c0c35bd4)
References
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (June 2011) |
- Knuth, Donald Ervin (1997), The Art of Computer Programming, Volume 1: Fundamental Algorithms, The Art of Computer Programming, vol. 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 (0): 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.