斐波那契数列
1202年，意大利数学家斐波那契(Leonardo Fibonacci,约1170–1250)出版了他的《算盘全书(Liber Abacci》.他在书中提出了一个关于兔子繁殖的问题:
如果一对兔子每月能生1对小兔子(一雄一雄)。而每1对小兔子在它出生后的第三个月里，又能生1对小兔子，假定在不发生死亡的情况下，由1对初生的小兔子开始，50个月后会有多少对兔子?
在第1个月时，只有1对小兔子，过了1个月，那对兔子成熟了，在第3个月时便生下1对小兔子，这时有两对兔子，再过1个月，成熟的兔子再生1对小兔子，而另1对小兔子长大，有3对小兔子。如此推算下去，我们可以得到一个表格:
时间(月)初生兔子(对)成熟兔子(对)总兔子数(对)11012011311241235235635875813881321913213410213455\begin{array}{c|c|c|c}时间(月)&初生兔子(对)&成熟兔子(对)&总兔子数(对) \\ \hline1&1&0&1 \\ \hline2&0&1&1 \\ \hline 3&1&1&2 \\ \hline 4&1&2&3 \\ \hline 5&2&3&5 \\ \hline 6&3&5&8 \\ \hline 7&5&8&13 \\ \hline 8&8&13&21 \\ \hline 9&13&21&34 \\ \hline 10&21&34&55\end{array}时间(月)12345678910初生兔子(对)101123581321成熟兔子(对)0112358132134总兔子数(对)11235813213455
由此可知。从第1个月开始，以后每个月的兔子总对数是1,1,2,3,5,8,13,21,34,55,89,144,233,⋯1,1,2,3,5,8,13,21,34,55,89,144,233,\cdots1,1,2,3,5,8,13,21,34,55,89,144,233,⋯你发现这个数列的规律了吗?
如果用 FnF_nFn 表示第 nnn 个月的兔子的总对数，可以看出，Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}Fn=Fn−1+Fn−2 这是一个由递推关系给出的数列，称为斐波那契数列。
现用特征根法求该数列的通项公式
由递推公式得特征方程为xn=xn−1+xn−2x^n=x^{n-1}+x^{n-2}xn=xn−1+xn−2 即 x2−x−1=0x^2-x-1=0x2−x−1=0 解得 x1=1+52,x2=1−52x_1=\dfrac{1+\sqrt5}{2},x_2=\dfrac{1-\sqrt5}{2}x1=21+5,x2=21−5设Fn=A⋅(1+52)n+B⋅(1−52)nF_n=A\cdot\left(\dfrac{1+\sqrt5}{2}\right)^n+B\cdot\left(\dfrac{1-\sqrt5}{2}\right)^nFn=A⋅(21+5)n+B⋅(21−5)n将 F1=F2=1F_1=F_2=1F1=F2=1 代入得 {A⋅(1+52)+B⋅(1−52)=1A⋅(1+52)2+B⋅(1−52)2=1\begin{cases}A\cdot\left(\dfrac{1+\sqrt5}{2}\right)+B\cdot\left(\dfrac{1-\sqrt5}{2}\right)=1 \\[3ex] A\cdot\left(\dfrac{1+\sqrt5}{2}\right)^2+B\cdot\left(\dfrac{1-\sqrt5}{2}\right)^2=1\end{cases}⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧A⋅(21+5)+B⋅(21−5)=1A⋅(21+5)2+B⋅(21−5)2=1解得{A=15B=−15\begin{cases}A=\dfrac{1}{\sqrt5} \\[3ex] B=-\dfrac{1}{\sqrt5}\end{cases}⎩⎪⎪⎨⎪⎪⎧A=51B=−51所以Fn=15[(1+52)n−(1−52)n]F_n=\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^n-\left(\dfrac{1-\sqrt5}{2}\right)^n\right]Fn=51[(21+5)n−(21−5)n]
作者：LB_yifeng
