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,

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

Catalan's identity generalizes this:

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

Vajda's identity generalizes this:

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 Fibonacii 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 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 $n$ th power of a matrix with determinant −1:

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}.

Notes

Thomas Koshy: Fibonacci and Lucas Numbers with Applications. Wiley, 2001, ISBN 9781118031315, pp. 74-75, 83, 88
Miodrag Petkovic: Famous Puzzles of Great Mathematicians. AMS, 2009, ISBN 9780821848142, S. 30-31
Douglas B. West: Combinatorial Mathematics. Cambridge University Press, 2020, p. 61
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)

gollark: observe, I have hackerized Discord.

gollark: If I ever want to run BF on DOS I'll keep it in mind.

gollark: This could seriously be very cool.

gollark: I could add colors and occasionally muck up the formatting slightly, have each sentence get its own header saying "Section 1, Clause 3" or something, maybe even have JS on the page subtly edit it as you scroll down!

gollark: It would actually support line wrapping, as well as Unicode, italic/bold/strikethrough, headers, external links, that sort of thing.

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 (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.

External links

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Koshy-1] 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

[West-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)