Fibonacci 数列

費波那契數列（Fibonacci Sequence）是數學上一個知名的數列，與黃金分割有一定的關係。該數列中的任意一項稱為費波那契數。

遞推定義

一個數列稱為費波那契數列，若它的每一項($F_n$)都可用以下的方法定義：

• $F_0 = 0, F_1 = 1;$
• 若$n \geqslant 2$，則$F_{n} = F_{n-1} + F_{n-2}.$

通項公式

$$F_n = k_1 q_1^{n-1} + k_2 q_2^{n-1} = \dfrac{1}{\sqrt{5}} \left( \dfrac{1+\sqrt{5}}{2} \right)^n - \dfrac{1}{\sqrt{5}} \left( \dfrac{1-\sqrt{5}}{2} \right)^n.$$

證明有很多種，一種代數證明詳見线性递推数列。

$\dfrac{\sqrt{5}-1}{2}$是黃金比例，亦是母函數的收斂半徑。

性質

1. 若$F_n$為第$n$個費波那契數則$\lim_{n \to \infty}\frac{F_n+1}{F_{n}} = \frac{1+\sqrt{5}}{2}$
2. Zeckendorf 定理：每個正整數都可表成有限個不連續的費波那契數的和。
3. 該數列的母函數為
   $$\frac{1}{1-x-x^2} = \sum_{n=0}^\infty F_{n+1} x^n = 1 + x + 2x + 3x^2 + 5x^3 + \cdots, \forall x: |x| < \frac{\sqrt{5}-1}{2}.$$
4. 该数列的任意六个连续数的和是第五个数的4倍，任意任意十个连续数的和是第七个数的11倍。
5. 该数列前$n$个数的和是第$n+2$个数减一。
6. 该数列的任意连续的四个数，中间两个数的乘积和其它两个数的乘积差1。

參見

• 黃金分割
• Zeckendorf 定理