生成函数

系数为常数的线性递推关系,只要乘以 $x$$^n$ 再对所有 $n$ 求和,就总会变成一个简单的代数(其实是有理)方程——递推关系变成了乘以一个关于 $x$ 的多项式。

把递推关系 $F_n=F_{n-1}+F_{n-2}$(对 $n\ge2$ 成立)乘以 $x^n$,再对 $n\ge2$ 求和:$\sum_{n\ge2}F_nx^n=\sum_{n\ge2}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n$。

左边等于 $F(x)-F_0-F_1x=F(x)-x$。右边第一个和是 $x\sum_{n\ge2}F_{n-1}x^{n-1}=x\sum_{m\ge1}F_mx^m=x(F(x)-F_0)=xF(x)$。第二个和是 $x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x^2\sum_{k\ge0}F_kx^k=x^2F(x)$。

于是 $F(x)-x=xF(x)+x^2F(x)$,即 $(1-x-x^2)F(x)=x$。

解出 $F(x)$ 得 $F(x)(1-x-x^2)=x$,因此 $F(x)=\frac{x}{1-x-x^2}$,这一个有理函数就打包了整个无穷的斐波那契数列。

任何分母含有互不相同的一次因子的有理生成函数,都可以分解为若干简单等比级数之和,而每个等比级数都能直接给出系数的显式公式。

分解分母:由于 $1-x-x^2=0$ 的根是 $x=1/\varphi$ 与 $x=1/\psi$,故有 $1-x-x^2=(1-\varphi x)(1-\psi x)$。

把 $\frac{x}{1-x-x^2}=\frac{A}{1-\varphi x}+\frac{B}{1-\psi x}$ 写成含常数 $A,B$ 的形式。通分并比较常数项与 $x$ 的系数,得到一个线性方程组,解得 $A=\frac{1}{\sqrt5}$,$B=-\frac{1}{\sqrt5}$,于是 $\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x}-\frac{1}{1-\psi x}\right)$。

把每一项展开为等比级数:$\frac{1}{1-\varphi x}=\sum_{n\ge0}\varphi^nx^n$,$\frac{1}{1-\psi x}=\sum_{n\ge0}\psi^nx^n$。

比较两边 $x^n$ 的系数即得公式 $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$,称为比内公式。