前置知识

斐波那契数列

$$ f_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ f_{i - 1} + f_{i - 2} & n > 1 \end{cases} $$

普通生成函数基本公式

众所周知生成函数中显然有 $x \in (-1, 1)$ 即函数收敛：

$$ \frac{1}{1 - x} = \sum_{i = 0} ^ {\infty} x ^ i $$

我们将 $kx$ 替换 $x$ 得到：

$$ \frac{1}{1 - kx} = \sum_{i = 0} ^ {\infty} k ^ i x ^ i $$

解法

我们构造 $f(x)$ 的生成函数 $F(x) = \sum_{i = 0} ^ {\infty} f(i) \cdot x ^i$：

$$ \begin{align*} F(x) & = & 0x ^ 0 + 1x + 1x ^ 2 + 2x^ 3 + 3x ^ 4 + 5x ^ 5 + \dots \\ xF(x) & = & 0x + 1x ^ 2 + 1x ^ 3 + 2x ^ 4 + 3x ^ 5 + \dots \\ x ^ 2 F(x) & = & 0x ^ 2 + 1x ^ 3 + 1x ^ 4 + 2x ^ 5 + \dots \end{align*} $$

那么有：

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

由于 $\frac{1}{1 - kx} = \sum_{i = 0} ^ {\infty} k ^ i x ^ i$，那么我们尝试把 $F(x)$ 裂项为如下形式：

$$ \frac{x}{1 - x - x ^ 2} = \frac{A}{1 - \phi_1 x} + \frac{B}{1 - \phi_2 x} $$

列出方程：

$$ 1 - x - x ^ 2 = (1 - \phi_1 x)(1 - \phi_2 x) \\ \phi_1 = \frac{1 + \sqrt 5}{2}, \phi_2 = \frac{1 - \sqrt 5}{2} $$

再列出方程：

$$ A(1 - \phi_2 x) + B(1 - \phi_1 x) = x \\ (A + B) - (A \phi_2 + B \phi_2 + 1)x = 0 \\ A = \frac{1}{\sqrt 5}, B = -\frac{1}{\sqrt 5} $$

故我们得到生成函数的具体形式：

$$ \begin{align*} F(x) = \frac{x}{1 - x - x ^ 2} & = \frac{1}{\sqrt 5}\left(\frac{1}{1 - \phi_1 x } - \frac{1}{1 - \phi_2 x}\right) \\ & = \frac{1}{\sqrt 5}\left(\sum_{i = 0} ^ {\infty} \phi_1 ^ i x ^ i - \sum_{i = 0} ^ {\infty} \phi_2 ^ i x ^ i\right) \\ & = \sum_{i = 0} ^ {\infty} \frac{\phi_1 ^ i - \phi_2 ^ i}{\sqrt 5} x ^ i \end{align*} $$

于是我们求出了斐波那契数列的通项公式：

$$ \begin{align*} f_n & = \frac{1}{\sqrt 5}(\phi_1 ^ n - \phi_2 ^ n) \\ & = \frac{1}{\sqrt 5}\left(\left(\frac{1 + \sqrt 5}{2}\right) ^ n - \left(\frac{1 - \sqrt 5}{2}\right) ^ n\right) \end{align*} $$