浅谈数列中常系数线性齐次递推关系的求解

翻书复习之时,看到斐波那契数列,于是将一些关于数列递推关系方面的内容整理了一下。

定义1:一个常系数的\(k\)阶线性齐次递推关系是形如\[a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{k}a_{n-k}\]的递推关系,其中\(c_{1},c_{2},\cdots,c_{k}\)是实数,\(c_{k}\neq 0\)。

这个定义中递推关系是线性的,因为它的右边是数列前项的倍数之和。这个递推关系是齐次的,因为所出现的各项都是\(a_{j}\)的倍数。数列各项的系数都是常数而不是依赖于\(n\)的函数。阶为\(k\)是因为\(a_{n}\)由序列前面的\(k\)项来表示。

例1:递推关系\(p_{n}=2p_{n-1}\)是\(1\)阶的线性齐次递推关系。递推关系\(f_{n}=f_{n-1}+f_{n-2}\)是\(2\)阶的线性齐次递推关系。

例2:递推关系\(a_{n}=a_{n-1}+a_{n-2}^{2}\)不是线性的。递推关系\(h_{n}=2h_{n-1}+1\)不是齐次的。递推关系\(b_{n}=nb_{n-1}\)不是常系数的。

求解常系数线性齐次递推关系的基本方法是寻找形如\(a_{n}=r^{n}\)的解,其中\(r\)是常数。注意\(a_{n}=r^{n}\)是递推关系\(a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{k}a_{n-k}\)的解,当且仅当\[r^{n}=c_{1}r^{n-1}+c_{2}r^{n-2}+\cdots+c_{k}r_{n-k}\]当等式两边除以\(r^{n-k}\)并且从左边减去右边时,我们得到等价的方程\[r^{k}-c_{1}r^{k-1}-c_{2}r^{k-2}-\cdots-c_{k-1}r-c_{k}=0\]因此,数列\(\left\{a_{n}\right\}\)以\(a_{n}=r^{n}\)作为解,当且仅当\(r\)使者后一个方程的解。这个方程叫作该递推关系的特征方程。方程的解叫做该递推关系的特征根。

我们首先看一个\(2\)阶常系数线性齐次递推关系的处理结果。然后,叙述相应的阶可能大于\(2\)的一般性结果。

定理1:设\(c_{1}\)和\(c_{2}\)是实数。假设\(r_{2}-c_{1}r-c_{2}=0\)有两个不等的根\(r_{1}\)和\(r_{2}\),那么数列\(\left\{a_{n}\right\}\)是递推关系\(a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}\)的解,当且仅当\(a_{n}=\alpha_{1}\cdot r_{1}^{n}+\alpha_{2}\cdot r_{2}^{n},n=0,1,2,\cdots\),其中\(\alpha_{1}\)和\(\alpha_{2}\)是常数。

例3:求斐波那契数列的通项公式。
解:斐波那契数列满足递推关系\(f_{n}=f_{n-1}+f_{n-2}\)和初始条件\(f_{1}=f_{2}=1\)。特征方程\(r^{2}-r-1=0\)的两个根是\(r_{1,2}=\frac{1\pm\sqrt{5}}{2}\)。因此,由定理1的斐波那契数列通项公式为:\[f_{n}=\alpha_{1}\cdot \left(\frac{1+\sqrt{5}}{5}\right)^{n}+\alpha_{2}\cdot \left(\frac{1-\sqrt{5}}{2}\right)^{n}\]其中\(\alpha_{1},\alpha_{2}\)为常数。可由初始条件\(f_{1}=f_{2}=1\)确定这两个常数,我们有\[\left\{\begin{matrix}
f_{1}=\alpha_{1}\cdot \left ( \frac{1+\sqrt{5}}{2} \right )+\alpha _{2}\cdot \left ( \frac{1-\sqrt{5}}{2} \right )=1\\\\
f_{2}=\alpha_{1}\cdot \left ( \frac{1+\sqrt{5}}{2} \right )^{2}+\alpha _{2}\cdot \left ( \frac{1-\sqrt{5}}{2} \right )^{2}=1
\end{matrix}\right.\]从而得到\(\alpha_{1}=\frac{\sqrt{5}}{5},\alpha_{2}=-\frac{\sqrt{5}}{5}\),于是斐波那契数列的通项公式为:\[f_{n}=\frac{\sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{5}\right)^{n}-\frac{\sqrt{5}}{5}\left(\frac{1-\sqrt{5}}{2}\right)^{n}\]

当存在二重特征根的时候,定理1不再适用。如果遇到这种情况,当\(r_{0}\)是特征方程的一个二重根时,那么\(a_{n}=nr_{0}^{n}\)是递推关系的另一个解。

定理2:设\(c_{1}\)和\(c_{2}\)是实数。假设\(r_{2}-c_{1}r-c_{2}=0\)只有一个根\(r_{0}\)。数列\(\left\{a_{n}\right\}\)是递推关系\(a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}\)的解,当且仅当\(a_{n}=\alpha_{1}\cdot r_{0}^{n}+\alpha_{2}\cdot n\cdot r_{0}^{n},n=0,1,2,\cdots\),其中\(\alpha_{1}\)和\(\alpha_{2}\)是常数。

例4:数列\(\left\{a_{n}\right\}\)满足\(a_{n}=6a_{n-1}-9a_{n-2}\),且\(a_{1}=6,a_{2}=27\),求数列\(\left\{a_{n}\right\}\)的通项公式。
解:\(r^{2}-6r+9=0\)唯一的根是\(r=3\)。因此这个递推关系的解是\[a_{n}=\alpha_{1}\cdot 3^{n}+\alpha_{2}\cdot n\cdot 3_{n}\]其中\(\alpha_{1},\alpha_{2}\)是常数。使用初始条件得\(\alpha_{1}=\alpha_{2}=1\),所以\(\left\{a_{n}\right\}\)的通项公式为\[a_{n}=3^{n}+n\cdot 3^{n}\]

例4:求满足\(a_{1}=5,a_{2}=15,a_{3}=47\)的递推关系\(a_{n}=6a_{n-1}-11a_{n-2}+6a_{n-3}\)的通项公式。
解:有这个递推关系的特征方程\(r^{3}-6r^{2}+11r-6=0\)得到三个特征根\(r_{1}=1,r_{2}=2,r_{3}=3\),于是递推关系的解的形式为:\[a_{n}=\alpha_{1}\cdot 1^{n}+\alpha_{2}\cdot 2^{n}+\alpha_{3}\cdot 3^{n}\]通过初始条件的到\(\alpha_{1}=1,\alpha_{2}=-1,\alpha_{3}=2\)。于是通项公式为:\[a_{n}=1-2^{n}+2\cdot 3^{n}\]

发表评论