前面有一篇关于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\)和最后几步的化简过程变得没那么直观了。
打赏作者