一类特征方程在数列递推中的应用

以下内容摘自《组合数学》（第五版）P86【例 2-41】。

---

求 \(S_n=1^3+2^3+\cdots+n^3\)。

---

\(\Delta S_n=S_{n+1}-S_n=(n+1)^3\) 是 \(n\) 的 \(3\) 次多项式，因此 \(S_n\) 满足递推关系：

\[S_n-5S_{n-1}+10S_{n-2}-10S_{n-3}+5S_{n-4}-S_{n-6}=0 \]

设：

\[\begin{aligned} S_n&=A_1\dbinom n1+A_2\dbinom n2+A_3\dbinom n3+A_4\dbinom n4\\ S_1&=1=A_1\\ S_2&=1^3+2^3=9=\dbinom 21+A_2,A_2=7\\ S_3&=9+3^3=36=3+7\dbinom 32+A_3,A_3=12\\ S_4&=36+4^3=100=4+7\times6+12\times4+A_4,A_4=6\\ \end{aligned} \]

因此，有：

\[S_n=\dbinom n1+7\dbinom n2+12\dbinom n3+6\dbinom n4 \]

Fibonacci 数列通项公式

设 \(f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}\)。

则有特征方程：

\[\begin{aligned} x^n-x^{n-1}-x^{n-2}&=0\\ x^{n-2}(x^2-x-1)&=0\\ \end{aligned} \]

解得 \(x^{n-2}=0\) 或 \(x^2-x-1=0\)。因为 \(x^n>0\)，因此 \(x^2-x-1=0\)，解得：

\[x_1=\dfrac{1+\sqrt5}2,x_2=\dfrac{1-\sqrt5}2 \]

\(f_n\) 一定形如：

\[f_n=c_1x^n+c_2x^n \]

待定系数法可得通项公式：

\[f_n=\dfrac1{\sqrt5}\left[\left(\dfrac{1+\sqrt5}2\right)^n-\left(\dfrac{1-\sqrt5}2\right)^n\right] \]

自然数幂次和

设 \(S_n=1+2+\cdots+n\)。

有：

\[\begin{aligned} S_n-S_{n-1}&=n\\ S_{n-1}-S_{n-2}&=n-1 \end{aligned} \]

两式相减可得：

\[S_n-2S_{n-1}+S_{n-2}=1 \]

同理，有：

\[S_{n-1}-2S_{n-2}+S_{n-3}=1 \]

两式相减，得：

\[S_n-3S_{n-1}+3S_{n-2}-S_{n-3}=0 \]

对应特征方程：

\[x^3-3x^2+3x-1=(x-1)^3=0 \]

\(x=1\) 为三重根。

因为 \(\Delta S_n=S_{n+1}-S_n=n+1\) 为关于 \(n\) 的 \(1\) 次多项式，因此设：

\[S_n=(an^2+bn+c)1^n \]

代入 \(S_1,S_2,S_3\)，有：

\[\begin{cases} 1&=a+b+c\\ 3&=4a+2b+c\\ 6&=9a+3b+c\\ \end{cases} \]

解得：

\[\begin{cases} a=\dfrac12\\ b=\dfrac12\\ c=0 \end{cases} \]

故，\(S_n=\dfrac12n^2+\dfrac12n\)。

---

设 \(S_n=1^3+2^3+\cdots+n^3\)。

有：

\[\begin{aligned} S_n-S_{n-1}&=n^3\\ S_{n-1}-S_{n-2}&=(n-1)^3 \end{aligned} \]

两式相减，得：

\[S_n-2S_{n-1}+S_{n-2}=3n^2-3n+1 \]

同理：

\[S_{n-1}-2S_{n-2}+S_{n-3}=3n^2-9n+7 \]

因此，有：

\[S_n-3S_{n-1}+3S_{n-2}-S_{n-3}=6n-6 \]

同理：

\[S_{n-1}-3S_{n-2}+3S_{n-3}-S_{n-4}=6n-12 \]

两式相减可得：

\[S_n-4S_{n-1}+6S_{n-2}-4S_{n-3}+S_{n-4}=6 \]

同理：

\[S_{n-1}-4S_{n-2}+6S_{n-3}-4S_{n-4}+S_{n-5}=6 \]

两式相减可得：

\[S_n-5S_{n-1}+10S_{n-2}-10S_{n-3}+5S_{n-4}-S_{n-5}=0 \]

对应特征方程为：

\[\begin{aligned} x^5-5x^4+10x^3-10x^2+5x-1&=0\\ (x-1)^5&=0 \end{aligned} \]

\(x=1\) 为五重根。

\(\Delta S_n=S_{n+1}-S_n=(n+1)^3\) 为关于 \(n\) 的 \(3\) 次多项式，设：

\[S_n=\left(an^4+bn^3+cn^2+dn+e\right)1^n \]

根据待定系数法，可解得通解。

齐次线性递推

可视为广义 Fibonacci 数列，解出特征根 \(x_1,x_2,\cdots,x_k\) 后可得通项公式：

\[f_n=c_1x_1^n+c_2x_2^n+\cdots+c_kx_k^n \]

非齐次线性递推

例如自然数幂次和，递推式是非齐次的，设非齐次部分关于 \(n\) 的项数为 \(k\)。

那么此时特征根的系数 \(c_i\) 不再为常数，系数 \(c_i\) 讲表述为关于 \(n\) 的 \(k+1\) 次多项式。

特征方程与组合数

例如，对于递推数列 \(S_n=S_{n-1}+n^2\)。

特征方程为：

\[x^3-3x^2+3x-1=(x-1)^3=0 \]

有三重根 \(x=1\)。

因此可以设 \(S_n=\left(an^3+bn^2+cn+d\right)1^n\)。

根据 \(S_0=0,S_1=1,S_2=5,S_3=14\)，可列：

\[\begin{cases} d=0\\ a+b+c=1\\ 8a+4b+2c=5\\ 27a+9b+3c=14\\ \end{cases} \]

解得：

\[\begin{cases} a=\dfrac13\\ b=\dfrac12\\ c=\dfrac16\\ d=0 \end{cases} \]

因此：

\[S_n=\dfrac13n^3+\dfrac12n^2+\dfrac16n=\dfrac{n(n+1)(n+2)}6 \]

---

然而已经得知 \(S_n\) 是关于 \(n\) 的 \(3\) 次多项式，因此可以有：

\[S_n=A\dbinom n3+B\dbinom n2+C\dbinom n1+D\dbinom n0 \]

这样根据组合数的性质，求解待定系数法会简单一些。

特征方程与生成函数

特征方程与生成函数有异曲同工之妙。

特征方程将递推式直接换为 \(x\)，并且带上相对应的指数。而生成函数则为每一项配备一个变量 \(x^n\)。