Generating Functions - Key Proof

The Fibonacci generating function demonstrates how recurrence relations translate into functional equations, enabling extraction of closed formulas.

Proof:

The Fibonacci sequence satisfies $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$, with $F_0 = 0$ and $F_1 = 1$.

Let $F(x) = \sum_{n=0}^{\infty} F_n x^n$. Multiply the recurrence by $x^n$ and sum from $n = 2$ to $\infty$: $\sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n$

The left side is $F(x) - F_0 - F_1 x = F(x) - x$.

For the right side: $\sum_{n=2}^{\infty} F_{n-1} x^n = x \sum_{n=2}^{\infty} F_{n-1} x^{n-1} = x \sum_{m=1}^{\infty} F_m x^m = x(F(x) - F_0) = xF(x)$

$\sum_{n=2}^{\infty} F_{n-2} x^n = x^2 \sum_{n=2}^{\infty} F_{n-2} x^{n-2} = x^2 \sum_{k=0}^{\infty} F_k x^k = x^2 F(x)$

Therefore: $F(x) - x = xF(x) + x^2F(x)$ $F(x)(1 - x - x^2) = x$ $F(x) = \frac{x}{1-x-x^2}$

Extracting Binet's Formula:

Factor the denominator: $1 - x - x^2 = -(x-\phi)(x-\hat{\phi})$ where $\phi = \frac{1+\sqrt{5}}{2}$ and $\hat{\phi} = \frac{1-\sqrt{5}}{2}$ are roots of $x^2 = x + 1$, or equivalently, $1 = x + x^2$.

Actually, solving $1 - x - x^2 = 0$ gives $x = \frac{-1 \pm \sqrt{5}}{2}$, so the roots are $-\hat{\phi}$ and $-\phi$. We can write: $1 - x - x^2 = (1 - \phi x)(1 - \hat{\phi} x) \cdot (-\phi\hat{\phi})$

Note that $\phi \cdot \hat{\phi} = \frac{1+\sqrt{5}}{2} \cdot \frac{1-\sqrt{5}}{2} = \frac{1-5}{4} = -1$.

So: $1 - x - x^2 = -(1/\phi)(1/\hat{\phi})(1 - \phi x)(1 - \hat{\phi} x) = -(-1)(1 - \phi x)(1 - \hat{\phi} x) = (1-\phi x)(1-\hat{\phi}x)$

Wait, let me recalculate. If $r$ is a root of $r^2 = r + 1$, then $1 = r + r^2$, so $1 - r - r^2 = 0$. The polynomial $1 - x - x^2$ has roots where $x = \phi$ and $x = \hat{\phi}$... Actually, I need to be more careful.

The characteristic equation of $F_n = F_{n-1} + F_{n-2}$ is $r^2 = r + 1$, with roots $\phi$ and $\hat{\phi}$.

For the generating function denominator $1 - x - x^2$, setting equal to zero: $x^2 + x - 1 = 0$, giving $x = \frac{-1 \pm \sqrt{5}}{2}$. These are $-\hat{\phi}$ and $-1/\phi$ (since $1/\phi = \phi - 1 = \hat{\phi}$ from $\phi^2 = \phi + 1$).

Using partial fractions: $\frac{x}{1-x-x^2} = \frac{x}{(1-\phi x)(1-\hat{\phi}x)} = \frac{A}{1-\phi x} + \frac{B}{1-\hat{\phi}x}$

Solving: $A = \frac{1}{\sqrt{5}}$ and $B = -\frac{1}{\sqrt{5}}$.

Therefore: $F(x) = \frac{1}{\sqrt{5}} \left(\frac{1}{1-\phi x} - \frac{1}{1-\hat{\phi}x}\right) = \frac{1}{\sqrt{5}} \sum_{n=0}^{\infty} (\phi^n - \hat{\phi}^n) x^n$

Comparing coefficients: $F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}$, which is Binet's formula. $\square$