问题及解答

斐波那契数列 Fibonacci(n), 或简记为 $F(n)$,

定义为 $F(n)=F(n-1)+F(n-2)$. $F(0)=0$, $F(1)=1$. 且 $F(-n)=(-1)^{n-1}F(n)$. 这里 $n$ 为非负整数.

Fibonacci 数列的前几个值为:
 \[0,1,1,2,3,5,8,13,21,34,55,\cdots\]

在 Calculator 中可以使用下面的函数生成

 Fibonacci(10,yes)

通项 F_n=F(n) 的公式为:

\[F_n = \frac{1}{\sqrt{5}}\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^n-\frac{1}{\sqrt{5}}\Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^n\]

令

\[
m=\begin{cases}
n, & n \text{是奇数}\\
n-1, & n \text{是偶数}\\
\end{cases}
\]

则可推出

\[F_n = \frac{1}{2^{n-1}}\cdot(C_n^1+C_n^3\cdot 5+C_n^5\cdot 5^2+\cdots+C_n^m\cdot 5^{\frac{m-1}{2}})\]

Fibonacci 数和二项式之间还有如下关系 ( [1] P.121 题 28) :

\[
F_{n+1}=C_n^0+C_{n-1}^1+\cdots+C_{n-k}^{k},
\]

其中 $k=[\frac{n}{2}]$.

这也是 Fibonacci 数与 Pascal 三角形之间的关系.

References:

[1] 殷剑宏 编著 《组合数学》

使用生成函数(也称母函数)可以证明

\[
F_n=\frac{1}{\sqrt{5}}\biggl[\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^n-\Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^n\biggr].
\]

证明:  令 $f(x)=\sum\limits_{n=0}^{\infty}a_n x^n$, 这里 $a_n=F_n$. 则我们有
\[
xf(x)=\sum_{n=2}^{\infty}a_{n-1}x^n,\quad x^2 f(x)=\sum_{n=3}^{\infty}a_{n-2}x^n.
\]

\[
\begin{split}
(1-x-x^2)f(x)&=\sum_{n=1}^{\infty}a_n x^n+\sum_{n=2}^{\infty}a_{n-1}x^n+\sum_{n=3}^{\infty}a_{n-2}x^n\\
&=x+\sum_{n=3}^{\infty}(a_n-a_{n-1}-a_{n-2})x^n=x.
\end{split}
\]

所以 $f(x)=\dfrac{x}{1-x-x^2}$.  记 $x_1,x_2$ 为方程 $1-x-x^2=0$ 的两个根, 则由韦达定理, $x_1+x_2=-1$, $x_1 x_2=-1$, 并且

\[
x_1=\frac{-1+\sqrt{5}}{2},\quad x_2=\frac{-1-\sqrt{5}}{2}.
\]

从而 $x_2-x_1=-\sqrt{5}$.

\[
\begin{split}
f(x)&=\frac{x}{-(x-x_1)(x-x_2)}=\frac{x}{x_2-x_1}\Bigl(\frac{1}{x-x_1}-\frac{1}{x-x_2}\Bigr)\\
&=\sum_{n=0}^{\infty}\frac{x}{x_2-x_1}\Bigl(\frac{1}{x_2^{n+1}}-\frac{1}{x_1^{n+1}}\Bigr)x^n\\
&=\sum_{n=1}^{\infty}\frac{1}{x_2-x_1}\Bigl(\frac{1}{x_2^{n}}-\frac{1}{x_1^{n}}\Bigr)x^n,
\end{split}
\]

所以

\[
\begin{split}
a_n&=\frac{1}{x_2-x_1}\Bigl(\frac{1}{x_2^{n}}-\frac{1}{x_1^{n}}\Bigr)=\frac{1}{(x_1 x_2)^n}\cdot\frac{x_1^n-x_2^n}{x_2-x_1}\\
&=\frac{1}{(-1)^n}\cdot\frac{x_1^n-x_2^n}{-\sqrt{5}}=\frac{1}{\sqrt{5}}(-1)^n\cdot\Biggl[\biggl(\frac{-1-\sqrt{5}}{2}\biggr)^n-\biggl(\frac{-1+\sqrt{5}}{2}\biggr)^n\Biggr]\\
&=\frac{1}{\sqrt{5}}\biggl[\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^n-\Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^n\biggr].
\end{split}
\]

参考 [1] (第一版) P.337  例 9.3.15

[1]  梅加强 编著 《数学分析》.