The **Fibonacci numbers** F_{n} are given by the recurrence

F

_{0}= 0F

_{1}= 1F

_{n}= F_{n-1}+ F_{n-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-z^{2}), which can be proved easily from the recurrence (see GeneratingFunctions). Expanding the generating function using partial fractions gives the formula

where

is the golden_ratio.