问题:给定数列的递推关系

an+C1an−1+C2an−2+⋯+Ckan−k=0a_n+C_1a_{n-1}+C_2a_{n-2}+\cdots+C_ka_{n-k}=0

以及若干初始项

a0=d0,a1=d1,…,ak−1=dk−1a_0=d_0,a_1=d_1,\ldots,a_{k-1}=d_{k-1}

如何求出其通项公式?

这里略去推导,仅总结算法。首先将递推关系转化为特征多项式:

C(x)=xk+C1xk−1+⋯+Ck−1x+CkC(x)=x^k+C_1x^{k-1}+\cdots+C_{k-1}x+C_k

通项公式的形状强相关于C(x)C(x)的根

情形一:C(x)C(x)有kk个实单根

此时要求C(x)C(x)没有重根,也没有共轭复根(实系数多项式的根只能是实单根、实重根或共轭复根)

假设其根为

α1,…,αk\alpha_1,\ldots,\alpha_k

则其母函数一定可以写成

G(x)=∑i=1kAi1−αixG(x)=\sum_{i=1}^k\frac{A_i}{1-\alpha_i x}

对应的通项公式为

an=∑i=1kAiαina_n=\sum_{i=1}^k A_i\alpha_i^n

只需要求解出对应的待定系数A1,…,AkA_1,\ldots,A_k,为此,kk个未知数需要kk个方程,正好我们有kk个初始项,于是只需解下面的联立方程组:

{A1+⋯+Ak=d0A1α1+⋯+Akαk=d1A1α12+⋯+Akαk2=d2⋯A1α1k−1+⋯+Akαkk−1=dk−1\begin{cases} A_1+\cdots+A_k=d_0\\ A_1\alpha_1+\cdots+A_k\alpha_k=d_1\\ A_1\alpha_1^2+\cdots+A_k\alpha_k^2=d_2\\ \cdots\\ A_1\alpha_1^{k-1}+\cdots+A_k\alpha_k^{k-1}=d_{k-1} \end{cases}

这本质上就是上面的带待定系数的通项公式的前kk项得到的方程组

情形二:C(x)C(x)有实重根

假设C(x)C(x)有kk重根α\alpha,则其通项公式可以写成

an=(A1+A2n+A3n2+⋯+Aknk−1)αna_n=(A_1+A_2n+A_3n^2+\cdots+A_kn^{k-1})\alpha^n

同样地,只要利用ana_n的前kk项的值,解下面的联立方程求出待定系数即可:

{A1=d0A1+A2+⋯+Ak=d1/αA1+2A2+⋯+2k−1Ak=d2/α2⋯A1+(k−1)A2+⋯+(k−1)k−1Ak=dk−1/αk−1\begin{cases} A_1=d_0\\ A_1+A_2+\cdots+A_k=d_1/\alpha\\ A_1+2A_2+\cdots+2^{k-1}A_k=d_2/\alpha^2\\ \cdots\\ A_1+(k-1)A_2+\cdots+(k-1)^{k-1}A_k=d_{k-1}/\alpha^{k-1} \end{cases}

情形三:C(x)C(x)有共轭复根

假设C(x)C(x)有一对共轭复根α1,α2\alpha_1,\alpha_2,此时通项公式的形状与2个实单根是相同的:

an=A1α1n+A2α2na_n=A_1\alpha_1^n+A_2\alpha_2^n

但为了防止指数内出现虚数,可以利用复数的三角形式做如下处理,设:

α1=ρ(cos⁡θ+isin⁡θ)\alpha_1=\rho(\cos\theta+i\sin\theta)

α2=ρ(cos⁡θ−isin⁡θ)\alpha_2=\rho(\cos\theta-i\sin\theta)

则

α1n=ρn(cos⁡nθ+isin⁡nθ)\alpha_1^n=\rho^n(\cos n\theta+i\sin n\theta)

α2n=ρn(cos⁡nθ−isin⁡nθ)\alpha_2^n=\rho^n(\cos n\theta-i\sin n\theta)

于是通项公式化为

an=(A1+A2)ρncos⁡nθ+i(A1−A2)ρnsin⁡nθa_n=(A_1+A_2)\rho^n\cos n\theta+i(A_1-A_2)\rho^n\sin n\theta

假设数列初始项都是实数,那么由

a0=A1+A2a_0=A_1+A_2

知

A1+A2∈RA_1+A_2\in\mathbb{R}

又由

a1=A1α1+A2α2=A1(a+bi)+A2(a−bi)=(A1+A2)a+(A1−A2)bi\begin{aligned} a_1=&A_1\alpha_1+A_2\alpha_2\\ =&A_1(a+bi)+A_2(a-bi)\\ =&(A_1+A_2)a+(A_1-A_2)bi \end{aligned}

知

(A1−A2)i∈R(A_1-A_2)i\in\mathbb{R}

令

A1+A2=A,(A1−A2)i=B,A,B∈RA_1+A_2=A,\quad(A_1-A_2)i=B,\quad A,B\in\mathbb{R}

则通项公式事实上化为

an=Aρncos⁡nθ+Bρnsin⁡nθa_n=A\rho^n\cos n\theta+B\rho^n\sin n\theta

只需解方程

{A=d0Aρcos⁡θ+Bρsin⁡θ=d1\begin{cases} A=d_0\\ A\rho\cos\theta+B\rho\sin\theta=d_1 \end{cases}

即可

情形四:综合的情况

假设C(x)C(x)的根综合以上多种情况,例如

C(x)=(x−1)(x−2)2(x2+x+1)C(x)=(x-1)(x-2)^2(x^2+x+1)

则其根为

α=1,2,2,−1+3i2,−1−3i2\alpha=1,2,2,\frac{-1+\sqrt3 i}2,\frac{-1-\sqrt3 i}2

那么我们可以综合上面的各情形表达式,得到通项公式的形式:

an=A1+(A2+nA3)2n+(A4cos⁡2nπ3+A5sin⁡2nπ3)a_n=A_1+(A_2+nA_3)2^n+\left(A_4\cos \frac{2n\pi} 3+A_5\sin\frac{2n\pi}3\right)

然后取前5项的初始值d0,…,d4d_0,\ldots,d_4,代入公式解出待定系数即可