用生成函数求斐波那契数列（及所有线性递推数列）的通项公式
斐波那契数列的定义：
\[\begin{cases}f_0=0 \\ f_1=1 \\ f_i=f_{i-1}+f_{i-2}& (i>1)\end{cases} \]求出特征多项式
\[C(x)=x^2-x-1 \]\[S=\sum\limits^{\infty}_{i=0} f_ix^i \]递推关系
\[f_n=\sum\limits^k_{i=1}c_if_{n-i} \]的特征多项式为
\[C(x)=x^k-\sum\limits^k_{i=1}c_ix^{k-i} \]
为其生成函数。
推导：
\[\begin{aligned} S& =\sum\limits^{\infty}_{i=0} f_ix^i \\& =f_0+f_1x+\sum\limits^{\infty}_{i=2} (f_{i-1}+f_{i-2})x^i \\& =x+\sum\limits^{\infty}_{i=2} f_{i-1}x^i+\sum\limits^{\infty}_{i=2} f_{i-2}x^i \\& =x+x\sum\limits^{\infty}_{i=0} f_ix^i+x^2\sum\limits^{\infty}_{i=0} f_ix^i \\& =x+xS+x^2S \end{aligned}\]求解：
\[\begin{aligned} (x^2+x-1)S&=-x \\ S&=\dfrac{x}{1-x-x^2} \end{aligned}\]由于斐波那契数列的特征方程
\[\begin{aligned} C(x)&=0 \\ x^2-x-1&=0 \end{aligned}\]的根为
\[x_1=\dfrac{1+\sqrt{5}}{2} \quad x_2=\dfrac{1-\sqrt{5}}{2} \]所以 \(S\) 一定可以分解成
\[\dfrac{A}{1-x_1x}+\dfrac{B}{1-x_2x} \]的形式。
待定系数法（中间过程太长，故略去）：
\[\begin{aligned} \dfrac{A}{1-x_1x}+\dfrac{B}{1-x_2x}&=\dfrac{x}{1-x-x^2} \\ \dfrac{(1-x_2x)A+(1-x_1x)B}{(1-x_1x)(1-x_2x)}&=\dfrac{x}{1-x-x^2} \\ (1-x-x^2)((1-x_2x)A+(1-x_1x)B)&=x(1-x_1x)(1-x_2x) \\ \dots \\ A=\dfrac{\sqrt{5}}{5} \\ B=-\dfrac{\sqrt{5}}{5} \end{aligned}\]所以
\[S=\sum\limits^{\infty}_{i=0} (Ax_1^i+Bx_2^i)x^i \]对比系数，得：
\[\begin{aligned} f_n&=Ax_1^n+Bx_2^n \\& =\dfrac{\sqrt{5}}{5}\left( \left(\dfrac{1+\sqrt{5}}{2}\right)^n - \left(\dfrac{1-\sqrt{5}}{2}\right)^n \right) \end{aligned}\]觉得整个过程太麻烦？
线性递推通用公式：
设 \(C(x)=0\) 有根 \(q_1,q_2,\dots,q_t\)，重数分别为 \(m_1,m_2,\dots,m_t \quad(\sum m=k)\)。
\[f_n=\sum\limits^t_{i=1}\sum\limits^{m_i}_{j=1}d_{i,j}\binom{j+n-1}{n}q_i^n \]其中 \(d_{i,j}\) 为自由常量，通过数列的前几项列方程可确定她们。