# [006]-斐波那契数列数列求通项 from scratch

> source: 文章/fibonacci/index.md

# [006]-斐波那契数列数列求通项 from scratch

## de Moivre 的最初解法

首先引入一个结论：
$$
1 - x^n = (1 + x + x^2 + \cdots + x^{n-1})(1 - x)
$$
使用等比数列求和的方法很容易得证，高中基础方法，在此不赘述

对上式取极限有：
$$
1 + x + x^2 + \cdots + x^n = \frac{1}{1-x}
$$
de Moivre 使用了生成函数法(Generating Function)，考虑到$F_0 = 0, f_1 = 1, F_n = F_{n-1} + F_{n-2}$，构造生成函数：
$$
G(x) = \sum_{x=0}^\infty F_n x^n
$$
由此我们有：
$$
G(x) = F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \cdots \tag{1}
$$

$$
xG(x) = F_0 x + F_1 x^2 + F_2 x^3 + F_3 x^4 + \cdots \tag{2}
$$

$$
x^2G(x) = F_0 x^2 + F_1 x^3 + F_2 x^4 + F_3 x^5 + \cdots \tag{3}
$$

让$(1) - (2) - (3)$有：
$$
G(x) - xG(x) - x^2G(x) = F_0 + (F_1 - F_0)x + (F_2 - F_1 - F_0)x^2 + \cdots
$$
于是
$$
G(x) = \frac{x}{1 - x - x^2}
$$
我们要将其展开为幂级数，因此需要因式分解分母

对于$1 -x - x^2 = 0$，很容易知道它的两个根：$r_1 = \frac{1+\sqrt{5}}{2}, r_2 = \frac{1-\sqrt{5}}{2}$

则
$$
\frac{x}{1 - x - x^2} = \frac{x}{(1 - r_1x)(1 - r_2x)} = \frac{A}{1 - r_1x} + \frac{B}{1 - r_2x}
$$
待定系数法拆开还原可以得到$A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}$

因此有
$$
G(x) = \frac{1}{\sqrt{5}}\frac{1}{1 - r_1 x} - \frac{1}{\sqrt{5}}\frac{1}{1 - r_2 x}
$$
根据我们之前的结论：
$$
\frac{1}{1 - rx} = \sum_{n = 0}^\infty r^nx^n, \abs{rx} < 1
$$
