浅谈数列特征方程

· · 学习·文化课

数列特征方程初步。觉得水就当消遣看吧。

几个小问题。

1) 什么是通项公式？

课本上的解释为，如果数列 $\{a_n\}$ 的第 $n$ 项 $a_n$ 与 $n$ 之间的关系可以用一个公式来表示，这个公式叫做数列的通项公式。似乎听起来不是很靠谱的解释，不过目前也只能这样解释（我们目前所学的不靠谱的定义多的去了

通项公式与递推公式区别在于，通项公式是把项数直接代入可以求得值的公式。递推公式的第 $n$ 项与数列的前 $n$ 项之间存在一定的关系，把 $n$ 代入后，并不能直接求第 $n$ 项的值。

2) 为什么要求一个数列的通项？有何意义？

简单来说，就是方便计算和分析数列。

如果能得出一个数列的通项公式，便可以逐项计算（指无后效性和前效性的直接计算）。对于算法而言，可能复杂度可以直接从 O(n) 降到 O(1)；

还能得出一些性质，例如判断该数列的单调性？周期性？等等。如果没有通项公式，这些性质就很难得出。

3) 是否每一个数列都有通项公式？

先引入一个人尽皆知的数列 斐波那契数列。

\begin{cases}f_1=1\\f_2=1\\f_n=f_{n-1}+f_{n-2}&n\ge3\end{cases}

这个序列的数怎么算？就是这么一坨式子：

f_n=\dfrac{\sqrt5}{5}\cdot \left[ \left( \dfrac{1+\sqrt5}{2}\right)^n - \left( \dfrac{1-\sqrt5}{2}\right)^n\right]

即使你不知道怎么推的你也应该知道这个式子。

但这是个很奇怪的问题，一个整数序列却得出来一坨无理数表示的式子。这个问题现在解释不了，不过一会儿就能解释了。让我们先往下看。

我们先从一阶线性递推数列说起。

所谓“一阶线性递推数列”，是指下面的这种数列：若数列 \{ a_n \} 满足 a_{n+1}=p\cdot a_n + q，其中 p，q，a_1 是给定的实数，求数列 \left\{a_n \right\} 的通项公式。

如果 p=1，便是公差为 q 的等差数列。若 p\neq 1，那么我们就需要构造一个公比为 p 的等比数列以计算 \{a_n\} 的通项公式。

然后，我们需要寻找一个 x_0，使得 a_{n+1}-x_0=p(a_n-x_0)。

不妨设 b_n=a_n-x_0，则 \{b_n\} 为等比数列。这样 b_n=b_1\cdot p^{n-1}。

所以 a_n-x_0=p^{n-1}(a_1-x_0)，即 a_n=p^{n-1}(a_1-x_0)+x_0。

那么 x_0 怎么求？

由 a_{n+1}-x_0=p(a_n-x_0) 得 a_{n+1}=p(a_n-x_0)+x_0。

又 a_{n+1}=p\cdot a_n + q，得 a_{n+1}=p\cdot a_n+q=p\cdot a_n+(1-p)\cdot x_0。

所以 q=(1-p)\cdot x_0，x_0=\dfrac{q}{1-p}。

通过等比数列求和公式也可以得出一些其他的式子：

S_i=\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^nb_i-n\cdot x_0=\dfrac{b_1(1-p^n)}{1-p}-n\cdot x_0=\dfrac{(a_1-x_0)(1-p^n)}{1-p}-n\cdot x_0

这时候，数列的通项公式是一个常数加上一个等比的形式，比较容易计算。

考虑二阶线性递推数列。即数列 \{a_n\} 的递推式为 a_n=p\cdot a_{n-1}+q\cdot a_{n-2}，其中 p，q，a_1 是给定的实数，那么如何求数列的通项公式？

同样，我们设式子可以转化为 a_n-x_1\cdot a_{n-1}=x_2(a_{n-1}-x_1\cdot a_{n-2})。

整理式子 a_n-x_1\cdot a_{n-1}=x_2(a_{n-1}-x_1\cdot a_{n-2})

\Rightarrow a_n=(x_1+x_2)a_{n-1}-x_1x_2\cdot a_{n-2}

又 a_n=p\cdot a_{n-1}+q\cdot a_{n-2}

所以 \begin{cases}p=x_1+x_2\\q=x_1x_2\end{cases}

这像什么？韦达。

于是我们可以构造方程 x^2-px-q=0。x_1，x_2 分别是这个方程的两根。

这样才能转换为一个等比数列 \{b_n\}，b_n=a_n-x_1 \cdot a_{n-1}，公比为 x_2。

由等比数列的公式推出 \{b_n\} 通项，化简后可得

a_n=\dfrac{a_2-x_2a_1}{x_1-x_2}\cdot {x_1}^{n-1}-\dfrac{a_2-x_1a_1}{x_1-x_2}\cdot {x_2}^{n-1}

就像上面所说的一样。 设数列 a_n 的前两项 a_1，a_2 已知， a_n=p\cdot a_{n-1}+q\cdot a_{n-2}，则称方程 x^2-px-q=0 为该数列的特征方程。该方程若有两个根 x_1，x_2，则称这两个根为该数列的特征根。

再回到斐波那契数列。

我们知道斐波那契数列递推公式为 f_n=f_{n-1}+f_{n-2}

那么可以得出它的特征方程 x^2-x-1=0

解得 x_1=\dfrac{1+\sqrt{5}}{2}，x_2=\dfrac{1-\sqrt{5}}{2}

又 f_1=f_2=1

不妨设 f_n=A{x_1}^n+B{f_2}^n

所以 \begin{cases}f_1=A\cdot(\dfrac{1+\sqrt{5}}{2})+B\cdot(\dfrac{1-\sqrt{5}}{2})=1\\f_2=A\cdot(\dfrac{1+\sqrt{5}}{2})^2+B\cdot(\dfrac{1-\sqrt{5}}{2})^2=1\end{cases}

解得 A=\dfrac{\sqrt{5}}{5}，B=-\dfrac{\sqrt{5}}{5}

代入，可得 f_n=\dfrac{\sqrt5}{5}\cdot \left[ \left( \dfrac{1+\sqrt5}{2}\right)^n - \left( \dfrac{1-\sqrt5}{2}\right)^n\right]

这样就得到了上面所说的奇妙式子。

指形如 f_n=\dfrac{af_{n-1}+b}{cf_{n-1}+d}，已知 a，b，c，d，f_1，(c \ne0,ac-bd\ne0,f_1\ne\dfrac{af_1+b}{cf_1+d}) 求通项。

这里涉及到数列的不动点，不过我写不动了，，