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

我在这学的
最近确实有点卷, 虽然这套题之前写过, 但是没仔细研究. 然后为了能不尴尬地讲题, 拉着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} $$

現在修好了.