利用生成函数求斐波那契数列通项公式

先吐槽一下,学习这玩意儿的时候真的是深深的明白了自己的弱小,人家的一个”解得”我居然解了两个小时。。qwq

前置知识

斐波那契数列:

普通生成函数:

简单来说用多项式$\sum_{i=0}^{\infty} a_ix^i$的系数表示序列的元素

同时因为我们不关心$x$的取值,因此$\sum_{i=0}^{\infty}a_ix^i$又称作以$x$为自由元的形式幂级数

常见的有:

$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots + x^{\infty}$

证明:
后半部分可以直接由通项公式得到$S_n = \frac{1-x^{n+1}}{1-x}$,当$x \in (-1, 1)$,那么$\lim_{n\to +\infty} x^{n+1} = 0$

将$x$替换为$xk$得

$\frac{1}{1-kx} = 1 + kx + k^2x^2 + k^3x^3 \dots + k^{\infty}x^{\infty}$

解法

设$A = 1 + 1x + 2x^2 + 3x^3 + 5x^4 + 8x^5 \dots$

根据递推式,我们可以这样变化,显然有

那么可以得到一个方程$A - xA - x^2A = 1$

整理一下$A =\frac{1}{1-x-x^2}$

这样我们就得到了斐波那契数列的生成函数,然而并没有什么卵用,因为我们不能直接通过观察看出每一项的系数。

现在考虑一下,我们接下来可以干什么。我们已经知道了$\frac{1}{1-x}$和$\frac{1}{1-kx}$所表示的序列。接下来要干的当然是把$\frac{1}{1-x-x^2}$往上面的两个式子转化。

$\frac{1}{1-x-x^2}$这玩意儿下半部分是个一元二次方程,我们可以配方

(解的时候可以直接把后面的式子拆开,把这两个式子对应项联立组成方程组, $\phi_1 \phi_2$的取值是可以反过来的)

这个时候我们发现已经找到与$\frac{1}{1-kx}$的联系了,我们可以把$\frac{1}{(1-\phi_1 x)(1-\phi_2 x)}$拆成求和的形式。可以裂一下项

原式变为$\frac{a}{1-\phi_1x} + \frac{b}{1-\phi_2 x}$,然后再解一个方程$a(1-\phi_2 x) + b(1-\phi_1x) = 1$

解这个方程就没那么休闲了,这里我们选择把$x$当做主元对方程进行变换

这样就好处理了,只要列个二元一次方程组

解一下可以得到$a = \frac{1}{\sqrt{5}} \phi_1, b = -\frac{1}{\sqrt{5}} \phi_2$

带回去

那么第$n$项的公式为

参考资料

生成函数-罗煜楚(版权原因暂不公开)

特别感谢张一钊老师qwq


一只菜鸡