斐波那契数列(Fibonacci数列)
斐波那契数列 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] 殷剑宏 编著 《组合数学》