Question

斐波那契数列特征方程

Answer 1

以斐波那契数列为引子，导出一般的二阶常系数线性递归式的求解问题。
所谓斐波那契数列指的是数列：1，1，2，3，5，8，13，21，……。即数列满足递推公式 F_{n+2} = F_{n+1} + F_{n}，（F_1 = F_2 = 1），用语言描述就是后一项等于前两项和。很多高中生、非数学专业本科生都对此数列的通项公式的求法比较感兴趣，在本文中，我将给出其通项公式的解法，其中关系到二阶常系数线性递归式的求解问题，需要说明的是，本文的内容不作为严格的数学证明，只是给出这种求解的引导，希望能给读者一些启发。

当我们并没有学习到更深一层次的数学理论时，比如线性代数，离散数学等，我们无法使用那些已经成熟的理论工具来求解斐波那契数列的通项公式，但是我们依然有一些办法可以得到，这种办法有时候可能只是在一些巧合或者偶然的情况下得到的，请看下面的解法思路。

我们假设有一个等比数列\left\{ x^n \right\} ，公比是x，x不为0，首项为1，可以满足斐波那契数列的递推公式，于是就有：

x^{n+2} = x^{n+1} + x^{n}，将等比数列\left\{ x^n \right\} 代入递推式中得到，

提取x^n，移项，即有：

(x^2 - x - 1)x^n = 0,

由于x^n \ne 0，可得：

x^2 - x - 1= 0，

解此一元二次方程，可得两个根为：x_1 = \frac{1+\sqrt{5} }{2}，x_2 = \frac{1- \sqrt{5} }{2}。

也就是说等比数列\left\{ x_1^n \right\} ，\left\{ x_2^n \right\} 是满足斐波那契数列递推公式的两个解，但是实际上这两个等比数列都不是斐波那契数列的通项公式，既然单独的解不是，那么它们的组合呢？容易验证它们的线性组合，即：c_1x_1^n+c_2x_2^n，c_1、c_2是两个待求解的常数，也是递推公式的解。

为了确定这两个常数，我们需要数列的前两项作为初始因子，细想一下，一个数列怎么能没有首项呢？例如等差数列由首项和公差确定，等比数列由首项公比确定，公差和公比至少需要数列的前两项确定，将F_1和F_2代入线性组合的式子里，可得：

\left\{\begin{aligned}
& c_1 \cdot (\frac{1+\sqrt{5} }{2}) + c_2\cdot \frac{1-\sqrt{5} }{2} = 1 & \\
& c_1 \cdot (\frac{1+\sqrt{5} }{2})^2 + c_2\cdot (\frac{1-\sqrt{5} }{2})^2 = 1 & \\
\end{aligned}\right.，

解得：c_1 = \frac{1}{\sqrt{5}}，c_2 = -\frac{1}{\sqrt{5}}。

于是斐波那契数列的通项公式为：F_{n} = \frac{1}{\sqrt{5} }[(\frac{1+\sqrt{5} }{2})^n - (\frac{1-\sqrt{5} }{2})^n]。

可以验证，上式就是斐波那契数列的通项公式。

这种方法抽象出来就是特征方程法，特征方程的解法在常系数微分方程中同样适用，解法的理论依据，我们在此不做详细的论证，有兴趣的读者可以去查阅相关资料。

我们先把上面的解法抽象出来。

设二阶常系数齐次递归式为：aH_{n+2} + bH_{n+1} + cH_{n} = 0，其中a、b、c、为常数，有一元二次方程ax^2 + bx + c = 0与之对应，称其为递归式的特征方程，设其两个根为x_1、x_2。

当x_1 \ne x_2，即特征方程有两个不等的实根时，递归式的通项公式为H_{n} = c_1x_1^n + c_2x_2^n，c_1、c_2是两个待求解的常数；
当x_1 = x_2，即特征方程有两个相等的实根时，我们可以构造出一个线性无关解c_2n，则递归式的通项公式为：H_{n} = (c_1 + c_2n)x^n，c_1、c_2是两个待求解的常数；
当特征方程没有实根时，则递归式不存在实数范围内的解，此时的数列变为复数范围内的数列，我们在此不做讨论。
c_1、c_2两个常数可以用数列的前两项H_1、H_2来确定。

特征方程的解法不限于二阶常系数齐次递归式，对更高阶的递归式也适用，二阶的意思是特征方程是二次，三阶即对应三次方程，更高阶则类推，等比数列属于一阶。常系数的意思是a、b、c是常数，而不是函数，齐次的意思是递归式的右边是0，而不是关于n的函数，若右边是关于n的函数，特征方程法也成立，只是需要外加一个关于此函数的特解。

对于常系数线性递归式的解法就说到这里，下面我们来看看斐波那契数列的一些性质。

极限性质：\lim_{n \rightarrow \infty }{\frac{F_{n}}{F_{n+1}}} = \frac{\sqrt{5} - 1}{2}\approx 0.618，即黄金分割比，因此斐波那契数列又称为黄金分割数列。
前n项和：\sum_{i = 1}^{n}{F_i} = F_{n+2} - 1，由通项公式可以看出斐波那契数列就是两个等比数列的线性组合，因此分别按照等比数列求和公式就可以求前n项和。
交错和性质：\sum_{i = 1}^{n} {(-1)^iF_i} = (-1)^nF_{n-2} - 1。
集合性质：集合\left\{ 1, 2, 3, ... ,n-1 \right\} 的不含相邻两数的子集数为：F_n。
行列式性质：F_1 = F_2 = |1|，F_3 = \begin{vmatrix}
1 & 1 \\
-1 & 1 \\
\end{vmatrix}，F_4 = \begin{vmatrix}
1 & 1 & 0 \\
-1 & 1 & 1 \\
0 & -1 & 1\\
\end{vmatrix}，……。
计数性质：以1步或2步登上n-1阶台阶的登法数为F_n。
组合数性质：\sum_{i = 0}^{n-1}{C_{n-i}^i} = F_n ,(i<n, i\leqslant n-i)。
还有许多其它性质，这里不再列举。