以下内容摘自《组合数学》（第五版）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$。
