求一阶二阶线性递推式通项

摘要： 本文介绍了如何通过构造等比数列来求解一阶和二阶线性递推式的通项公式，并通过例题展示了具体的计算过程。

我在这学的
最近确实有点卷, 虽然这套题之前写过, 但是没仔细研究. 然后为了能不尴尬地讲题, 拉着GJY研究这个搞到两三点钟.
其实如果学过特征根的话很容易看出来这道题, 这不是没学过嘛. 然后问了好多大佬之后, 才找到特征根这个方向. 因为当时实在有点晚了, 只能耻辱下线.
第二天早上花了十几分钟分钟看完之后豁然开朗, 惊叹原来这么简单(不是
运算过程很简单, 但是构造还是有难度的. 幸好这是一个通解, 多用几次记下来就好了.
特征根好像是线性代数里面的内容(真的是好像)

一点补充写在前面:
在这篇文中, 因为等比数列比较容易求第$n$项, 所以我们希望把一个递推式转换成一个等比数列的形式.
在这里, 我先把递推式和等比数列给出, 再试图在它们之间建立联系(变量之间的等价关系).

1. 一阶

形如:

$$ x_n = px_{n-1} + q \qquad (a) $$

当$p=1$, 这是个等差数列.
当$p\neq1$, 考虑构造一个等比数列(这是一个通解式的构造):

$$ x_{n+1}-x_0=p(x_n-x_0) \qquad (b) $$

在这里, 每一项形如$x_i-x_0$, 这样就是一个公比为$p$的等比数列了.

我们考虑把$(b)$化成$(a)$的形式, 这样我们就可以将其中的变量建立联系.

$$ \begin{aligned} x_{n+1}&=px_n-px_0+x_0 \\ x_{n+1}&=px_n+(1-p)x_0 \qquad (b') \end{aligned} $$

到这里我们已经可以在$(b')$中清晰地看到$(a)$的模样了.
再进一步地, 我们将变量间建立联系.

$$ q=(1-p)x_0 \newline x_0=\frac{q}{1-p} $$

到此, 我们获得了等比数列$b$的所有常数$p,x_0$, 我们可以求出任意一项$x_n-x_0$, 自然也就能求出任意一项$x_n$.

所以$x_n=(x_1-x_0)p^{n-1}+x_0$.

2. 二阶

$$ x_n=px_{n-1}+qx_{n-2} \qquad (a) $$

这是一个二阶线性递推式, 为什么是二阶呢? 大概是因为用了两个$x$吧.

类似于一阶递推式, 我们希望构造出一个等比数列(同样的, 这是个通解式的构造):

$$ x_{n+1}-ax_n=b(x_n-ax_{n-1}) \qquad (b) $$

在这里, 每一项形如$x_i-ax_{i-1}$, 很类似$1.(b)$做法.

同样的, 我们尝试化为$(a)$的形式.

$$ x_{n+1}-ax_n=bx_n-abx_{n-1} \newline x_{n+1}=(a+b)x_n-abx_{n-1} \qquad (b') $$

然后对比$(a)$和$(b')$可以得到:

$$ \left\{ \begin{aligned} a+b&=p \\ ab&=-q \end{aligned} \right. $$

求解$a,b$, 我们考虑构造一个以$a,b$为根的一元二次方程. 考虑韦达定理:

$$ x^2-px-q=0 $$

这里这个方程称为这个数列的特征方程, $a,b$称为这个数列的特征根.

因为$a,b$是该方程的两个根, 所以它们是"对称"的, 考虑函数图像的对称性.

我们回到式子$(b)$, 因为它们是对称的, 所以我们可以得到两个等比数列:

$$ \left\{ \begin{aligned} x_{n+1}-ax_n&=b(x_n-ax_{n-1}) \\ x_{n+1}-bx_n&=a(x_n-bx_{n-1}) \end{aligned} \right. $$

等号右边可以化简:

$$ \left\{ \begin{aligned} x_{n+1}-ax_n&=b^{n-1}(x_2-ax_1) \\ x_{n+1}-bx_n&=a^{n-1}(x_2-bx_1) \end{aligned} \right. $$

为了求出$x_n$, 将它们作差, 消去左边的$x_{n+1}$:

$$ (a-b)x_n=a^{n-1}(x_2-bx_1)-b^{n-1}(x_2-ax_1) \newline x_n=\frac{a^{n-1}(x_2-bx_1)-b^{n-1}(x_2-ax_1)}{a-b} \qquad (c) $$

2.1例题:

$$ x_0=1,x_1=3,x_n=2x_{n-1}+2x_{n-2} $$

现在我们知道, 我们的目标是求出$a,b$, 直接解特征方程$x^2-(2)x-(2)=0$得:

$$ \left\{ \begin{aligned} a&=1+\sqrt{3} \\ b&=1-\sqrt{3} \end{aligned} \right. $$

带入🦁(啊不是, 是式子$2.(c)$:¹

$$ \begin{aligned} x_n&=\frac{(1+\sqrt{3})^{n-1}((3)-(1-\sqrt{3})(1))-(1-\sqrt{3})^{n-1}((3)-(1+\sqrt{3})(1))}{(1+\sqrt{3})-(1-\sqrt{3})} \\ \\ &=\frac{(1+\sqrt{3})^{n-1}(2+\sqrt{3})-(1-\sqrt{3})^{n-1}(2-\sqrt{3})}{(1+\sqrt{3})-(1-\sqrt{3})} \\ \\ &=\frac{\sqrt{3}+2}{2\sqrt{3}}(1+\sqrt{3})^{n-1}+\frac{\sqrt{3}-2}{2\sqrt{3}}(1-\sqrt{3})^{n-1} \end{aligned} $$

現在修好了.