Solving the Fibonacci recurrence with generating functions
posted by benzi
posted 1y 60d ago
Then this generating function can be broken into partial fractions: If
are the roots of
, then
where
turns out to be 
, so
![u \quad=\quad \frac{1}{\sqrt{5}}\left[ \frac{-r_1}{x-r_1} + \frac{r_2}{x-r_2} \right].](equations/15535_3.png "u \quad=\quad \frac{1}{\sqrt{5}}\left[ \frac{-r_1}{x-r_1} + \frac{r_2}{x-r_2} \right].")
Each fraction can be expressed as a geometric series in
, i.e.,
![u \quad=\quad \frac{1}{\sqrt{5}}\left[ \frac{1}{1 - x/r_1} - \frac{1}{1 - x/r_2} \right] \quad=\quad \frac{1}{\sqrt{5}}\left[ \left(1 + \frac{x}{r_1} + \left(\frac{x}{r_1}\right)^2 + \cdots\right) - \left(1 + \frac{x}{r_2} + \left(\frac{x}{r_2}\right)^2 + \cdots\right) \right].](equations/15535_4.png "u \quad=\quad \frac{1}{\sqrt{5}}\left[ \frac{1}{1 - x/r_1} - \frac{1}{1 - x/r_2} \right] \quad=\quad \frac{1}{\sqrt{5}}\left[ \left(1 + \frac{x}{r_1} + \left(\frac{x}{r_1}\right)^2 + \cdots\right) - \left(1 + \frac{x}{r_2} + \left(\frac{x}{r_2}\right)^2 + \cdots\right) \right].")
In this series, the coefficient of
is ![\frac{1}{\sqrt{5}} \left[ \left(\frac{1}{r_2}\right)^n - \left(\frac{1}{r_2}\right)^n \right]](equations/15535_11.png "\frac{1}{\sqrt{5}} \left[ \left(\frac{1}{r_2}\right)^n - \left(\frac{1}{r_2}\right)^n \right]")
. This is thus the 
th Fibonacci number as above, so
![F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1}{r_2}\right)^n - \left(\frac{1}{r_2}\right)^n \right].](equations/15535_5.png "F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1}{r_2}\right)^n - \left(\frac{1}{r_2}\right)^n \right].")
are the roots of
, then
where
turns out to be , so
Each fraction can be expressed as a geometric series in
, i.e.,
In this series, the coefficient of
is . This is thus the th Fibonacci number as above, so