斐波那契数列与黄金分割比的关系

前言

众所周知，斐波那契数列的递推公式为：

$$f_i = \begin{cases} 0 & i=0 \\ 1 & i = 1 \\ f_{i-1}+f_{i-2} & i \ge 2 \end{cases}$$

为什么会把斐波那契数列与黄金分割比联系再一起呢？其实和斐波那契的通项公式有关。

斐波那契数列的通项公式

我们考虑使用生成函数推导斐波那契数列的通项公式（别问我为什么，问就是博客正好写了，搬运一下）。

关于生成函数
生成函数是指以某个序列为系数的多项式，其形式为：

$$F(x) = \sum_{i=0} a_i x^i$$

其中 $x$ 的存在并没有什么意义，所以又被称为形式幂级函数

我们定义斐波那契数列的生成函数 $F(x)$ 为：

$$F(x) = \sum_{i \ge 0} f_i x^i$$

我们对这个式子进行变换

$$\begin{aligned} F(x) &= \sum_{i \ge 0} f_i x^i \\ &= f_0 + x f_1 + \sum_{i \ge 2} f_i x^i \\ \end{aligned}$$

当 $i \ge 2$ 时，$f_i = f_{i-1} + f_{i - 2}$，所以：

$$\begin{aligned} F(x) &= f_0 + x f_1 + \sum_{i \ge 2} (f_{i-1} + f_{i-2}) x^i \\ &= f_0 + x f_1 + \sum_{i \ge 2} f_{i-1} x^i + \sum_{i \ge 2} f_{i-2} x^i \\ &= f_0 + x f_1 + \sum_{i \ge 2} f_{i-1} x^i + \sum_{i \ge 2} f_{i-2} x^i \\ &= f_0 + x f_1 + x \sum_{i \ge 2} f_{i-1} x^{i-1} + x^2 \sum_{i \ge 2} f_{i-2} x^{i-2} \\ &= f_0 + x f_1 + x \sum_{i \ge 1} f_{i} x^{i} + x^2 \sum_{i \ge 1} f_{i} x^i \end{aligned}$$

然后由 $\displaystyle F(x) = \sum_{i \ge 0} f_i x^i$ 且当 $i=0$ 时，$f_0 x^0 = 0$ 可得：

$$\begin{aligned} & F(x) = f_0 + x f_1 + x \sum_{i \ge 1} f_{i} x^i + x^2 \sum_{i \ge 1} f_{} x^i \\ & F(x) = f_0 + x f_1 + x F(x) + x^2 F(x) \\ \because \ & f_0 = 0, f_1 = 1 \\ \therefore \ & F(x) = x + x F(x) + x^2 F(x) \\ \end{aligned}$$

合并同类项，系数化为一，得：

$$\begin{aligned} & (1 - x - x^2) F(x) = x \\ \therefore \ & F(x) = \frac{x}{1 - x - x^2} \end{aligned}$$

这样，我们就得到了 $F(x)$ 的封闭形式。

对于这个式子，我们考虑使用待定系数法将其部分分式分解：

$$\begin{aligned} \frac{A}{1-ax} + \frac{B}{1-bx} &= \frac{x}{1 - x - x^2} \\ \\ \frac{A - Abx + B - aBx}{1 - (a + b)x + abx^2} &= \frac{x}{1 - x - x^2} \\ \\ \frac{(A+B) - (Ab + aB)x}{1 - (a + b)x + abx^2} &= \frac{x}{1 - x - x^2} \\ \end{aligned}$$

观察两边的系数，得到一个方程组：

$$\begin{cases} A + B = 0 \\ Ab + aB = -1 \\ a + b = 1 \\ ab = -1 \\ \end{cases} \Rightarrow \begin{cases} A = \frac{1}{\sqrt{5}} \\ B = - \frac{1}{\sqrt{5}} \\ a = \frac{1 + \sqrt{5}}{2} \\ b = \frac{1 - \sqrt{5}}{2} \\ \end{cases}$$

接下来我们要介绍一个前置知识——几何级数（等比数列求和）。

关于几何级数
几何级数是指形式为

$$\sum_{n=0}^{\infty} r^n$$

的级数。其中 $r$ 称为公比（其实就是等比数列）。当 $|r| < 1$ 时，级数收敛，其和为：

$$\sum_{n=1}^{\infty} r^n = \frac{1}{1 - r}$$

这个就是我们接下来展开要用到的公式。

我们运用几何级数将上面最初的表达式展开：

$$\begin{aligned} & \frac{A}{1-ax} = A\sum_{i=0}^{\infty} (ax)^i = A\sum_{i=0}^{\infty} a^i x^i \\ & \frac{B}{1-bx} = B\sum_{i=0}^{\infty} (bx)^i = B\sum_{i=0}^{\infty} b^i x^i \\ \end{aligned}$$

收敛性证明

用几何级数展开公式时有一个前提：$|r| < 1$，而上面两个式子的 $r$ 分别为 $ax$ 和 $bx$。
其中 $a = \frac{1 + \sqrt{5}}{2}, b = \frac{1 - \sqrt{5}}{2}$，所以：

$$\begin{aligned} & ax = \frac{1 + \sqrt{5}}{2} x \\ & bx = \frac{1 - \sqrt{5}}{2} x \end{aligned}$$

对于 $a,b,x$ 存在限制：

$$\begin{cases} |\frac{1 + \sqrt{5}}{2} x| < 1 \\ \\ |\frac{1 - \sqrt{5}}{2} x| < 1 \end{cases} \Rightarrow \begin{cases} |\frac{1 + \sqrt{5}}{2}| |x| < 1 \\ \\ |\frac{1 - \sqrt{5}}{2}| |x| < 1 \end{cases}$$

所以

$$\begin{cases} |x| < |\frac{\sqrt{5} - 1}{2}| \\ \\ |x| < |-\frac{\sqrt{5} + 1}{2}| \end{cases}$$

即

$$|x| < \min\Big(|\frac{\sqrt{5} - 1}{2}|, |-\frac{\sqrt{5} + 1}{2}|\Big) = \frac{\sqrt{5} - 1}{2}$$

因为 $F(x)$ 定义为形式幂级数，所以我们仅关注 $x^i$ 的系数，而不关注 $x$ 的具体的值，只要由满足条件的 $x$ 存在，就可以用上面的方式对原式展开。

用上面两个式子等量代换，得：

$$\begin{aligned} F(x) &= A \Bigg(\sum_{i=0}^{\infty} a^i x^i \Bigg) + B \Bigg( \sum_{i=0}^{\infty} b^i x^i \Bigg) \\ &= \textcolor{red}{\frac{1}{\sqrt{5}}} \Bigg( \sum_{i=0}^{\infty} \bigg( \frac{1 + \sqrt{5}}{2} \bigg)^i x^i \Bigg) - \textcolor{red}{\frac{1}{\sqrt{5}}} \Bigg( \sum_{i=0}^{\infty} \bigg( \frac{1 - \sqrt{5}}{2} \bigg) x^i \Bigg) \\ &= \frac{1}{\sqrt{5}} \Bigg( \sum_{\textcolor{blue}{i=0}}^{\infty} \bigg( \frac{1 + \sqrt{5}}{2} \bigg)^i x^i - \sum_{\textcolor{blue}{i=0}}^{\infty} \bigg( \frac{1 - \sqrt{5}}{2} \bigg)^i x^i \Bigg) \\ &= \frac{1}{\sqrt{5}} \sum_{i=0}^{\infty} \bigg( \Big(\frac{1 + \sqrt{5}}{2} \Big)^i x^i - \Big( \frac{1-\sqrt{5}}{2} \Big)^i x^i \bigg)\\ &= \frac{1}{\sqrt{5}} \sum_{i=0}^{\infty} \textcolor{green}{x^i} \bigg( \Big(\frac{1 + \sqrt{5}}{2} \Big)^i - \Big( \frac{1-\sqrt{5}}{2} \Big)^i \bigg) \\ &= \sum_{i=0}^{\infty} \frac{\big(\frac{1 + \sqrt{5}}{2} \big)^i - \big( \frac{1-\sqrt{5}}{2} \big)^i}{\sqrt{5}} x^i \\ \end{aligned}$$

对比 $F(x)$ 最初的的定义：

$$F(x) = \sum_{i=0}^{\infty} f_i x^i$$

得斐波那契数列的通项公式为：

$$f_i = \frac{\big(\frac{1 + \sqrt{5}}{2} \big)^i - \big(\frac{1 - \sqrt{5}}{2} \big)^i}{\sqrt{5}}$$

其中就有黄金分割比 $\phi = \frac{\sqrt{5} - 1}{2}$ 的相反数。

更直观的体现

我们已经发现了斐波那契数列的通项公式中的黄金分割比，其实黄金分割比在斐波那契数列中还有更直观的体现。

我们取斐波那契数列相邻两项的比值：

$$\begin{aligned} \frac{f_i}{f_{i+1}} &= \frac{\big ( \frac{1+\sqrt{5}}{2} \big)^i - \big ( \frac{1 - \sqrt{5}}{2} \big)^i}{\big ( \frac{1+\sqrt{5}}{2} \big)^{i+1} - \big ( \frac{1 - \sqrt{5}}{2} \big)^{i+1}} \\ &= \frac{ \frac{2}{1+\sqrt{5}} \big( \frac{1 + \sqrt{5}}{2} \big)^{\textcolor{red}{i+1}} - \frac{2}{1-\sqrt{5}} \big( \frac{1 - \sqrt{5}}{2} \big)^{\textcolor{red}{i+1}} }{ \big(\frac{1+\sqrt{5}}{2} \big)^{i+1} - \big ( \frac{1 - \sqrt{5}}{2} \big)^{i+1}} \\ &= \frac{ \frac{\sqrt{5} - 1}{2} \big( \frac{1 + \sqrt{5}}{2} \big)^{i+1} - \big(\frac{\sqrt{5} - 1}{2} - \sqrt{5}\big) \big( \frac{1 - \sqrt{5}}{2} \big)^{i+1} }{ \big(\frac{1+\sqrt{5}}{2} \big)^{i+1} - \big ( \frac{1 - \sqrt{5}}{2} \big)^{i+1}} \\ &= \frac{ \frac{\sqrt{5} - 1}{2} \textcolor{red}{\big( \frac{1 + \sqrt{5}}{2} \big)^{i+1}} - \frac{\sqrt{5} - 1}{2} \textcolor{red}{\big( \frac{1 - \sqrt{5}}{2} \big)^{i+1}} - \sqrt{5}\big( \frac{1 - \sqrt{5}}{2} \big)^{i+1}}{ \textcolor{red}{\big(\frac{1+\sqrt{5}}{2} \big)^{i+1}} - \textcolor{red}{\big ( \frac{1 - \sqrt{5}}{2} \big)^{i+1}}} \\ &= \frac{\sqrt{5} - 1}{2} - \frac{\sqrt{5}\big( \frac{1 - \sqrt{5}}{2} \big)^{i+1}}{\big(\frac{1+\sqrt{5}}{2} \big)^{i+1} - \big ( \frac{1 - \sqrt{5}}{2} \big)^{i+1} } \\ &= \frac{\sqrt{5} - 1}{2} - \textcolor{red}{\frac{\sqrt{5}}{ \big( - \frac{3 + \sqrt{5}}{2} \big)^{i+1} - 1 }} \\ \end{aligned}$$

当 $i \to \infty$ 时，后面的分式的值趋向于 $0$，即：

$$\lim_{i \to \infty} \frac{f_i}{f_{i+1}} = \frac{\sqrt{5} - 1}{2}$$

所以，斐波那契数列相邻两项的比值趋向于黄金分割比 $\phi$。