一，二阶常系数线性递推数列的特征方程/特征根
Vocalise
·
·
个人记录
一点东西。感觉还挺有用？
本文中一阶不保证齐次，而二阶需要保证齐次。
一阶递推数列
即：给定数列 \{a_n\}，a_0 已知，有
a_i=ca_{i-1}+q
求通项公式。
首先可以OGF试试。
cxA(x)=\sum_{n=1}^{\infty}ca_{n-1}x^n
(1-cx)A(x)=a_0+\sum_{n=1}^{\infty}qx^n=a_0+q\sum_{n=0}^{\infty}x^n-q
A(x)&=\frac{a_0+\frac q{1-x}-q}{1-cx} \\
&=\frac{a0}{1-cx}+\frac{qx}{(1-x)(1-cx)} \\
&=\frac{a_0}{1-cx}+\frac q{1-c}(\frac 1{1-x}-\frac 1{1-cx}) \\
&=\sum_{n=0}^{\infty}[a_0c^n+\frac q{1-c}(1-c^n)]x^n
\end{aligned}
于是得到通项
a_n=c^n(a_0-\frac q{1-c})+\frac q{1-c}
但是有没有更简单的方法呢？
构造等比数列：设有常数 d，使
(a_n-d)=c(a_{n-1}-d)
ca_{n-1}+q-d=ca_{n-1}-cd,d=\frac q{1-c}
则 d 可以方便地求出来，此时有数列 \{a_n-d\}
a_n-d=(a_0-d)\times c^n,a_n=c^n(a_0-\frac q{1-c})+\frac q{1-c}
就得到一样的结果。
上述推导中如果 c=1，则为等差数列，另外讨论。
这里还没出现题目中的两个概念。别急，下面就有了。
二阶递推数列（齐次）
即数列 \{a_n\}，a_0,a_1 已知，
a_n=c_1a_{n-1}+c_2a_{n-2}
OGF做法稍后。
同样尝试构造等比数列。设常数 p,q，使
a_{n+1}-pa_n=q(a_n-pa_{n-1})
化简得
a_{n+1}=(p+q)a_n-pqa_{n-1}
又有 c_1,c_2 已知，得到它们与 p,q 的关系。根据韦达定理，有唯一一个一元二次方程组使其两根分别为 p,q，它是
x^2-c_1x-c_2=0
这就称为二阶常系数齐次线性递推数列的特征方程。
两根 z_1,z_2 不分先后地称为其特征根。
一阶的情况比较简单，因此未给出特征方程与特征根的定义。
根据特征方程和特征根，可以快速给出通项公式。
得到等比数列
a_{n+1}-z_1a_n=(a_1-z_1a_0)z_2^n
这时仍不是想要的结果。根据上述结论，z_1,z_2 不分先后地满足一元二次方程，因此得到：
a_{n+1}-z_2a_n=(a_1-z_2a_0)z_1^n
两式相减得
a_n=\frac{a_1-z_1a_0}{z_2-z_1}z_2^n+\frac{a_1-z_2a_0}{z_1-z_2}z_1^n
得到通项公式。
或者可以根据等比数列累加：
a_n&=(a_1-z_2a_0)z_2^n+z_1a_{n-1}\cdots \\
&=(a_1-z_2a_0)z_2^{n-1}+z_1(a_1-z_2a_0)z_2^{n-2}+z_1^2a_{n-1}\cdots \\
&=z_2^na_0+(a_1-z_2a_0)\sum_{i=0}^{n-1}z_1^iz_2^{n-1-i} \\
&=z_2^na_0+\frac{(a_1-z_2a_0)(z_1^n-z_2^n)}{z_1-z_2}
\end{aligned}
这个和式的变形略去不提。
a_n&=z_2^na_0+\frac{z_1^na_1-z_2^na_1-z_1^nz_2a_0+z_2^{n+1}a_0}{z_1-z_2} \\
&=\frac{z_1^na_1-z_2^na_1-z_1^nz_2a_0+z_1z_2^na_0}{z_1-z_2} \\
&=\frac{a_1-z_2a_0}{z_1-z_2}z_1^n+\frac{a_1-z_1a_0}{z_2-z_1}z_2^n
\end{aligned}
同时还发现 a_n 只与 z_1,z_2 的次数有关，考虑如下形式：
a_n=g_1z_1^n+g_2z_2^n
还可以有一个归纳：对于 $a_0$ 满足上述形式，则
$$\begin{aligned}
a_n&=c_1a_{n-1}+c_2a_{n-2} \\
&=(z_1+z_2)(g_1z_1^{n-1}+g_2z_2^{n-1})-z_1z_2(g_1z_1^{n-2}+g_2z_2^{n-2}) \\
&=g_1z_1^n+g_2z_2^n+g_1z_1^{n-1}z_2+g_2z_1z_2^{n-1}-g_1z_1^{n-1}z_2-g_2z_1z_2^{n-1} \\
&=g_1z_1^n+g_2z_2^n
\end{aligned}$$
然而这并没有什么意义，$g1,g2$ 我们是可以直接求的。
最后尝试用OGF计算。
$$\begin{aligned}
A(x)=a_0+a_1x+&a_2x^2+a_3x^3+\cdots \\
c_1xA(x)=c_1a_0x+&c_1a_1x^2+c_1a_2x^3+\cdots \\
c_2x^2A(x)=&c_2a_0x^2+c_2a_1x^3+c_2a_2x^4\cdots \\
\end{aligned}$$
$$A(x)=c_1xA(x)+c_2x^2A(x)+a_0+a_1x-c_1a_0x$$
$$A(x)=\frac{a_0+a_1x-c_1a_0x}{1-c_1x-c_2x^2}$$
仍然考虑特征根为 $z_1,z_2$。接下来就是一些神仙的变化了。乘上 $(z_2-z_1)$。
$$\begin{aligned}
A(x)&=\frac{(z_2-z_1)a_1x+(z_2-z_1)a_0+(z_1+z_2)(z_1-z_2)a_0x}{(z_2-z_1)(1-c_1x-c_2x^2)} \\
&=\frac{(a_1-z_1a_0)(1-z_1x)-(a_1-z_2a_0)(1-z_2x)}{(z_2-z_1)(1-z_1x)(1-z_2x)} \\
&=\frac 1{z_2-z_1}\times(\frac{a_1-z_1a_0}{1-z_2x}-\frac{a_1-z_2a_0}{1-z_1x}) \\
&=\sum_{n=0}\frac{a_1-z_1a_0}{z_2-z_1}z_2^nx^n-\sum_{n=0}\frac{a_1-z_2a_0}{z_2-z_1}z_1^nx^n
\end{aligned}$$
$$a_n=\frac{a_1-z_1a_0}{z_2-z_1}z_2^n+\frac{a_1-z_2a_0}{z_1-z_2}z_1^n$$
发现有一个问题就是我们还没讨论 $z_1=z_2$ 的情况呢qwq
设 $z_1=z_2=z$，有
$$a_{n+1}-za_n=z(a_n-za_{n-1})$$
然后直接累加。
$$\begin{aligned}
a_n&=(a_1-za_0)z^{n-1}+za_{n-1}\cdots \\
&=(a_1-za_0)z^{n-1}+z(a_1-za_0)z^{n-2}+z^2a_{n-2}\cdots \\
&=n(a_1-za_0)z^{n-1}+z^na_0\\
&=(a_0+n\frac{a_1-za_0}z)z^n
\end{aligned}$$
如 $(a_0+nb)z^n$ 的形式自然也具有一般性。
自此便告一段落。
在[生成函数初识](https://www.luogu.com.cn/blog/void-basic-learner/generating-function-preview)这篇文章中两个例子可以方便地套用。
> 汉诺塔数列
$$h_0=0,h_n=2h_{n-1}+1$$
则常数 $d=-1$，有公式
$$\begin{aligned}
h_n&=(h_0-d)2^n+d \\
&=(0+1)2^n-1 = 2^n-1
\end{aligned}$$
> 菲波那契数列
$$f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}$$
特征方程为 $x^2-c_1x-c_2=0$，即
$$x^2-x-1=0$$
众所周知这个方程很优美，解得两根为
$$z_1=\frac{1+\sqrt 5}2,z_2=\frac{1-\sqrt 5}2$$
代入 $f_0=0,f_1=1$ 及形式 $f_n=g_1z_1^n+g_2z_2^n
0=g_1+g_2 \\
1=\frac{1+\sqrt 5}2g_1+\frac{1-\sqrt 5}2g_2
\end{cases}
解得
g_1=\frac 1{\sqrt 5} \\
g_2=-\frac 1{\sqrt 5}
\end{cases}
通项即为
f_n=\frac 1{\sqrt 5}((\frac{1+\sqrt 5}2)^n-(\frac{1-\sqrt 5}2)^n)