PineWikiThe 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),\]](/pinewiki/FibonacciNumbers?action=AttachFile&do=get&target=latex_c4da854ce7bc7fc005c6ac7566347a84df164ac3_p1.png "\[F_n = \frac{1}{\sqrt{5}}\left(\phi^n - (1-\phi)^n\right),\]")
where
![\[\phi = \frac{1 + \sqrt{5}}{2}\]](/pinewiki/FibonacciNumbers?action=AttachFile&do=get&target=latex_dbe7d39db24ce1edeb08d1848efec91fb86db44a_p1.png "\[\phi = \frac{1 + \sqrt{5}}{2}\]")
is the golden_ratio.
