MathLabs
定理已证明

斐波那契生成函数的封闭形式

命题陈述

设 F0=0, F1=1F_0=0,\ F_1=1,且对 n≥2n\ge2 有 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}。则普通生成函数 F(x)=∑n=0∞FnxnF(x)=\sum_{n=0}^{\infty}F_nx^n 等于 F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2}。

为什么成立?

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

证明思路

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

左边等于 F(x)−F0−F1x=F(x)−xF(x)-F_0-F_1x=F(x)-x。右边第一个和是 x∑n≥2Fn−1xn−1=x∑m≥1Fmxm=x(F(x)−F0)=xF(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)。第二个和是 x2∑n≥2Fn−2xn−2=x2∑k≥0Fkxk=x2F(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)+x2F(x)F(x)-x=xF(x)+x^2F(x),即 (1−x−x2)F(x)=x(1-x-x^2)F(x)=x。

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

用到此定理的主题

生成函数

分步证明

该定理暂无分步证明。

参考文献

  1. Herbert S. Wilf (1994). generatingfunctionology
  2. Philippe Flajolet, Robert Sedgewick (2009). Analytic Combinatorics