(50g) Nth Fibonacci Number

[Han]

Another way to produce the constants obtained in Eddie's solution is to use formal series and generating functions to solve recurrence equations. Let \( a_n \) denote the \( n \)th term, and let
\[ f(x) = \sum_{n=0}^\infty a_n x^n \]
\[ a_{n+2} = a_{n+1} + a_{n} \quad \Longrightarrow \quad
a_{n+2}\cdot x^{n+2} = x \cdot a_{n+1}\cdot x^{n+1} + x^2 \cdot a_n \cdot x^n \]
Summing each side with \( n = 0, 1, 2, \dotsm \) produces
\[ \sum_{n=0}^\infty a_{n+2} x^{n+2} = x \sum_{n=0}^\infty a_{n+1}x^{n+1}
+ x^2 \sum_{n=0}^\infty a_n x^n \quad
\Longrightarrow \quad f(x)-a_1 x - a_0 = x \cdot [ f(x)-a_0 ] + x^2f(x) \]
Solve for \( f(x) \) to obtain
\[ f(x) = \frac{a_1 x -a_0x + a_0}{1-x-x^2} = \frac{1}{1-x-x^2} \]
In the last equality, we (for simplicity's sake) assume that \( a_0 = a_1 = 1 \). Using a partial fraction decomposition with \( \alpha = -\frac{1}{2}(1-\sqrt{5}) \) and \( \beta = -\frac{1}{2}(1+\sqrt{5}) \) gives
\[ f(x) = \frac{-1}{(x-\alpha)(x-\beta)} = \frac{A}{x-\alpha} + \frac{B}{x-\beta} \]
or
\[ -1 = A\cdot (x-\beta) + B\cdot (x-\alpha) \]
Letting \( x= \alpha \) and then \( x=\beta \) produces \(A = -\frac{1}{\alpha-\beta} = -\frac{1}{\sqrt{5}} \) and \( B = \frac{1}{ \sqrt{5}} \) respectively. Now rewrite \( f(x) \) as a sum of power series:
\[ f(x) = \frac{1}{\sqrt{5}} \left( -\frac{1}{x-\alpha} + \frac{1}{x-\beta} \right)
= \frac{1}{\sqrt{5}}\left( \frac{1}{\alpha-x} - \frac{1}{\beta-x}\right)
= \frac{1}{\sqrt{5}} \left( \frac{1}{\alpha\cdot (1-\frac{x}{\alpha})} -
\frac{1}{\beta \cdot (1-\frac{x}{\beta})} \right)
= \frac{1}{\sqrt{5}} \left( \frac{1}{\alpha} \sum_{n=0}^\infty \left(\frac{x}{\alpha}\right)^n - \frac{1}{\beta} \sum_{n=0}^\infty \left( \frac{x}{\beta}\right)^n \right) \]
by making use of the identity
\[ \frac{1}{1-t} = \sum_{n=0}^\infty t^n \]
So
\[ f(x) = \sum_{n=0}^\infty \underbrace{\frac{1}{\sqrt{5}}\left( \frac{1}{\alpha^{n+1}}-\frac{1}{\beta^{n+1}}\right)}_{\text{ this is } a_n} x^n \]
The exponent \( n+1 \) (as opposed to \( n \) ) is due to us setting \( a_0 = 1 \) and not \( a_0 = 0 \).