李尚轩

#OI

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

本文介绍一阶和二阶线性递推式求通项的方法：通过构造等比数列，将一阶递推式化为等比形式；对二阶递推式，构造特征方程求特征根，并利用两个对称等比数列推导通项公式，最后给出例题。

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

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

1. 一阶

形如:

xn=pxn−1+q(a)x_n = px_{n-1} + q \qquad (a)

当p=1p=1, 这是个等差数列. 当p≠1p\neq1, 考虑构造一个等比数列(这是一个通解式的构造): xn+1−x0=p(xn−x0)(b)x_{n+1}-x_0=p(x_n-x_0) \qquad (b)

在这里, 每一项形如xi−x0x_i-x_0, 这样就是一个公比为pp的等比数列了.

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

xn+1=pxn−px0+x0xn+1=pxn+(1−p)x0(b′)\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′)(b')中清晰地看到(a)(a)的模样了. 再进一步地, 我们将变量间建立联系.

q=(1−p)x0x0=q1−pq=(1-p)x_0 \newline x_0=\frac{q}{1-p}

到此, 我们获得了等比数列bb的所有常数p,x0p,x_0, 我们可以求出任意一项xn−x0x_n-x_0, 自然也就能求出任意一项xnx_n.

所以xn=(x1−x0)pn−1+x0x_n=(x_1-x_0)p^{n-1}+x_0.

2. 二阶

xn=pxn−1+qxn−2(a)x_n=px_{n-1}+qx_{n-2} \qquad (a)

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

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

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

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

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

xn+1−axn=bxn−abxn−1xn+1=(a+b)xn−abxn−1(b′)x_{n+1}-ax_n=bx_n-abx_{n-1} \newline x_{n+1}=(a+b)x_n-abx_{n-1} \qquad (b')

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

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

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

x2−px−q=0x^2-px-q=0

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

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

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

{xn+1−axn=b(xn−axn−1)xn+1−bxn=a(xn−bxn−1)\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.

等号右边可以化简:

{xn+1−axn=bn−1(x2−ax1)xn+1−bxn=an−1(x2−bx1)\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.

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

(a−b)xn=an−1(x2−bx1)−bn−1(x2−ax1)xn=an−1(x2−bx1)−bn−1(x2−ax1)a−b(c)(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例题:

x0=1,x1=3,xn=2xn−1+2xn−2x_0=1,x_1=3,x_n=2x_{n-1}+2x_{n-2}

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

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

带入🦁(啊不是, 是式子2.(c)2.(c):[^1]
xn=(1+3)n−1((3)−(1−3)(1))−(1−3)n−1((3)−(1+3)(1))(1+3)−(1−3)=(1+3)n−1(2+3)−(1−3)n−1(2−3)(1+3)−(1−3)=3+223(1+3)n−1+3−223(1−3)n−1\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}

[^1]: 最近換了markdown編譯器, LaTeX好像炸了.

現在修好了.

评论

0

还没有评论。