The Fibonacci numbers Fn are given by the recurrence
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (for n > 1).
The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .
The generating function for the Fibonacci numbers is z/(1-z-z2), which can be proved easily from the recurrence (see GeneratingFunctions). Expanding the generating function using partial fractions gives the formula
![\[F_n = \frac{1}{\sqrt{5}}\left(\phi^n - (1-\phi)^n\right),\]](attachments/FibonacciNumbers/latex_0b1d06e930726180b8e3cfdd0e620761bdc161b6_p1.png "\[F_n = \frac{1}{\sqrt{5}}\left(\phi^n - (1-\phi)^n\right),\]")
where
![\[\phi = \frac{1 + \sqrt{5}}{2}\]](attachments/FibonacciNumbers/latex_e5fcb1c285665760ad8d4b0e5f473c63f6e30855_p1.png "\[\phi = \frac{1 + \sqrt{5}}{2}\]")
is the golden_ratio.