前面有一篇关于Fibonacci数列的欧拉计划问题2，里面提到Fibonacci通项公式，只附带了一个维基百科的链接。由于欧拉计划的习题里所使用的Fibonacci数列是以【1、2、…】开头的，并不是传统的【1、1、2、…】开头的，所以在这个习题里面的通项公式我按直觉的方式，把【n】改为【n+1】就完事了。
但数学与人类直觉之间的关系，有很微妙的历史——有些大名鼎鼎的数学家的确是靠直觉/灵感获得很多漂亮的定理和公式的，而有些却留下了一些使全人类感到遗憾的“猜想”。
所以我决定还是老老实实做一次推导过程。
首先，给出Fibonacci数列的递归定义：
\(
Fib_n =
\begin{cases}
1,& \text{if } n = 1\\
2,& \text{if } n = 2\\
Fib_{n-1} + Fib_{n-2}
\end{cases}
\)
然后假设有一个等比数列\(\{a_n\}\)，它相邻两项之间的比值为\(x\)，这个数列的每项与\(\{Fib_n\}\)的每项有如下关系：
- \(a_n = Fib_n + y \times Fib_{n-1}\)；
- \(a_n = x \times a_{n-1}\)；
- 所以有：\(Fib_n + y \times Fib_{n-1} = x \times (Fib_{n-1} + y \times Fib_{n-2})\)；
- 上述等式展开、移项之后，就有：
- \(Fib_n = x \times Fib_{n-1} + xy \times Fib_{n-2} – y \times Fib_{n-1}\)；
- \(Fib_n = (x – y) \times Fib_{n-1} + xy \times Fib_{n-2} = Fib_{n-1} + Fib_{n-2}\)。
观察递归定义最后一行，于是可以直接得出一个二元一次方程组：
\(
\begin{equation}
\left\{
\begin{aligned}
x-y &= 1 \\
xy &= 1 \\
\end{aligned}
\right.
\end{equation}
\)
消元\(y = x – 1\)，得：\(x(x – 1) = 1 \Rightarrow x^2 – x – 1 = 0\)。
解开该一元二次方程，得：\(x = \frac{-(-1) \pm \sqrt{(-1)^2-4 \times 1 \times (-1)}}{2 \times 1}=\frac{1 \pm \sqrt 5}{2}\)。
又假设\(x > y, x > 0, y > 0\)，所以有：
\(
\begin{equation}
\left\{
\begin{aligned}
x &= \frac{\sqrt{5} + 1}{2} \\
y &= \frac{\sqrt{5} – 1}{2} \\
\end{aligned}
\right.
\end{equation}
\)
又因为\(\{ Fib_n + y \times Fib_{n-1} \}\)（即\(\{a_n\}\)）是以\(x\)为比值的等比数列，根据等比数列通项公式\(a_n = a_1 \times x^{n-1}\)、\(a_2 = a_1 \times x\)、\(a_n = a_2 \times x^{n-2}\)，所以有：
- \(a_2 = Fib_2 + y \times Fib_1 = 2 + y \times 1 = 2 + y\)；
- \(a_{n+1} = a_2 \times x^{n+1-2} = (2 + y) \times x^{n-1}\)；
- 且从前面有\(y = x – 1\)，代入得：\(a_{n+1} = (2 + x – 1) \times x^{n-1} = (1 + x) \times x^{n-1} = x^{n-1} + x^n\)；
- 且\(a_{n+1} = Fib_{n+1} + y \times Fib_n\)，得：\(Fib_{n+1} + y \times Fib_n = x^{n-1} + x^n\)；
- 然后等式两边都除以\(x^{n+1}\)，得：\(\frac{Fib_{n+1}}{x^{n+1}} + \frac{y}{x} \frac{Fib_n}{x^n} = \frac{1}{x^2} + \frac{1}{x}\)。
又设一个数列\(\{b_n = \frac{Fib_n}{x^n}\}\)，上述等式则可表达为：\(b_{n+1} + \frac{y}{x} b_n = \frac{1}{x^2} + \frac{1}{x}\)。
求数列\(\{b_n\}\)的通项公式，引入未知数\(\lambda\)，使得\(b_{n+1} + \lambda = -\frac{y}{x} (b_n + \lambda)\)，移项后得：\(b_{n+1} + \frac{y}{x} b_n = -\lambda (1 + \frac{y}{x}) = \frac{1}{x^2} + \frac{1}{x}\)。
即有：
- 等式左边：\(-\lambda (1 + \frac{y}{x}) = \frac{-\lambda (x+y)}{x}\)；
- 等式右边：\(\frac{1}{x^2} + \frac{1}{x} = \frac{1+x}{x^2}\)；
- 即：\(\frac{-\lambda (x+y)}{x} = \frac{1+x}{x^2}\)；
- 即：\(-\lambda (x+y) = \frac{1+x}{x}\)；
- 又由于\(1 = xy\)，所以有：\(-\lambda (x+y) = \frac{xy+x}{x} = y + 1\)；
- 又由于\(y + 1 = x\)，所以有：\(-\lambda (x+y) = x\)；
- 即：\(\lambda = -\frac{x}{x+y}\)。
根据前面计算出来的\(x\)和\(y\)的值，\(\lambda\)肯定是一个非零、有意义的值，所以可以判断，\(\{b_n + \lambda\}\)是一个以\(-\frac{y}{x}\)为比值的等比数列，其通项公式为：\(b_n + \lambda = (b_1 + \lambda) \times (-\frac{y}{x})^{n-1}\)。
所以便会有：\(\frac{Fib_n}{x^n} + \lambda = (\frac{Fib_1}{x} + \lambda) \times (-\frac{y}{x})^{n-1}\)，代入\(Fib_1\)、\(\lambda\)、\(x\)、\(y\)、化简：
- \(\frac{Fib_n}{x^n} – \frac{x}{x+y} = (\frac{1}{x} – \frac{x}{x+y}) \times (-\frac{y}{x})^{n-1}\)；
- \(\frac{Fib_n}{x^n} = (\frac{1}{x} – \frac{x}{x+y}) \times (-\frac{y}{x})^{n-1} + \frac{x}{x+y}\)；
- \(Fib_n = x^n[(\frac{1}{x} – \frac{x}{x+y}) \times (-\frac{y}{x})^{n-1} + \frac{x}{x+y}]\)；
- \(Fib_n = x^n \frac{x+y-x^2}{x(x+y)} (-\frac{y}{x})^{n-1} + \frac{x^{n+1}}{x+y} = x^n \frac{x+y-x^2}{x+y} \frac{(-y)^{n-1}}{x^n} + \frac{x^{n+1}}{x+y}\)；
- \(Fib_n = \frac{x+y-x^2}{x+y} (-y)^{n-1} + \frac{x^{n+1}}{x+y} = \frac{x(1-x)+y}{x+y} (-y)^{n-1} + \frac{x^{n+1}}{x+y}\)；
- 因为\(1-x=y\)，所以\(Fib_n = \frac{x(-y)+y}{x+y} (-y)^{n-1} + \frac{x^{n+1}}{x+y} = \frac{y(1-x)}{x+y} (-y)^{n-1} + \frac{x^{n+1}}{x+y}\)；
- 因为\(1-x=y\)，所以\(Fib_n = \frac{y(-y)}{x+y} (-y)^{n-1} + \frac{x^{n+1}}{x+y}\)；
- \(Fib_n = \frac{-y^2}{x+y} (-y)^{n-1} + \frac{x^{n+1}}{x+y} = \frac{-(-y)^2}{x+y} (-y)^{n-1} + \frac{x^{n+1}}{x+y}\)；
- \(Fib_n = \frac{-(-y)^{n+1}}{x+y} + \frac{x^{n+1}}{x+y} = \frac{x^{n+1}-(-y)^{n+1}}{x+y}\)；
- \(Fib_n = \frac{(\frac{\sqrt{5} + 1}{2})^{n+1}-(\frac{1 – \sqrt{5}}{2})^{n+1}}{\sqrt{5}}\)。
整个过程与维基百科的大同小异，由于数列移了一位，求\(\lambda\)和最后几步的化简过程变得没那么直观了。
打赏作者
