斐波那契数列的生成函数及其通项公式

· · 个人记录

给定斐波那契数列递推式

\left\{ \begin{aligned} & f_0 = f_1 = 1 \\ & f_n = f_{n-1} + f_{n-2} &(n\ge 2) \end{aligned} \right.

求其第 n 项的通项公式。

设斐波那契数列 \{f_n\} 的普通生成函数为 G(x) = \sum\limits_{n=0}^{\infty} f_n x^n 。

则有：

\begin{aligned} G(x) &= 1 + x + \sum\limits_{n=2}^{\infty}(f_{n-1} + f_{n-2})x^n \\ &= 1 + x + x\sum\limits_{n=2}^{\infty}f_{n-1}x^{n-1} + x^2\sum\limits_{n=2}^{\infty}f_{n-2}x^{n-2} \\ &= 1 + x + x\sum\limits_{n=1}^{\infty}f_{n}x^{n} + x^2\sum\limits_{n=0}^{\infty}f_{n}x^{n} \\ &= 1 + x + x(G(x) -1) + x^{2}G(x) \\ &= 1 + (x^2+x)G(x) \end{aligned}

解得：

G(x) = \frac{-1}{x^2 + x -1} = \frac{1}{\sqrt{5}}\left(\frac{-1}{x-\frac{-1+\sqrt{5}}{2}} + \frac{1}{x-\frac{-1-\sqrt{5}}{2}}\right)

考虑牛顿二项式定理：

(x+y)^\alpha = \sum\limits_{n=0}^{\infty} \binom{\alpha}{n} x^n y^{\alpha-n}

带入 \alpha = -1 , y = -p 得：

(x-p)^{-1} = \sum\limits_{n = 0}^{\infty} \binom{-1}{n} x^n (-p)^{-1-n}

将牛顿二项式系数 \binom{-1}{n} 展开得：

\binom{-1}{n} = \frac{(-1)\times(-2) \times \cdots \times (-1-n+1)}{n!} = (-1)^{n} \times\frac{1\times2\times\cdots\times n}{n!} = (-1)^n

将 (4) 式带入 (3) 式得：

(x-p)^{-1} = \sum\limits_{n=0}^{\infty} (-1)^{n} x^{n} (-p)^{-1-n} = \sum\limits_{n=0}^{\infty} \frac{(-1)^n}{(-p)^{n+1}} x^{n} = \sum\limits_{n=0}^{\infty} -p^{-n-1} x^{n}

将 (5) 式带入 (1) 式得：

G(x) = \frac{1}{\sqrt{5}} \left( \sum\limits_{n=0}^{\infty}\left(\frac{-1+\sqrt{5}}{2}\right)^{-n-1} x^n - \sum\limits_{n=0}^{\infty}\left( \frac{-1-\sqrt{5}}{2}\right)^{-n-1}x^n \right)

故：

f(n) = \frac{1}{\sqrt{5}} \left( \left( \frac{-1+\sqrt{5}}{2} \right)^{-n-1} - \left( \frac{-1-\sqrt{5}}{2} \right)^{-n-1} \right)