退役OIer来诈尸了，祝大家新年快乐。
问题引入
下面的所有数列默认下标从 \(0\) 开始。
对于一个数列 \(\{a_n\}\)，如果其满足 \(k\) 阶常系数齐次线性递推 关系：
\[a_n=\sum_{i=1}^k p_i a_{n-i} \tag{*} \]其中 \(p_k \ne 0, n \geq k\)；
定义它的特征方程为：
\[x^k=\sum_{i=1}^{k}p_i x^{k-i} \]我们要证明的是：如果特征方程无重根，那么对于任意给出的初值 \(a_0,a_1,...a_{k-1}\)，都能做到将 \(a_n (n \in \mathbb{N}^*)\) 表示为
\[a_n=\sum_{i=1}^kc_ir_i^n \]的形式。其中 \(c_i\) 为常数， \(r_1,r_2,...r_k\) 是特征方程的所有根。（这些根可以是复数。）
开始证明
我们将证明分为两部分，在第一部分中，我们证明 \(n \geq k\) 的情况，而第二部分中，将证明 \(n < k\) 的情况。
第一部分：\(n \geq k\)
对于任意非零数 \(r\)，我们看到，\(a_n=r^n\) 是递推关系的解，当且仅当它满足递推关系，即，将其代入\((*)\)式，得到：
\[r^n=\sum_{i=1}^k p_i r^{n-i} \]两边同除 \(r^{n-k}\)，得到
\[r^k=\sum_{i=1}^k p_ir^{k-i} \]于是，这无穷多个方程退化为一个方程，即特征方程。所以我们得到 \(r^n\) 是递推关系的解当且仅当它是特征方程的根。
由于我们假定了 \(p_k \ne 0\)，所以 \(0\) 不是特征方程的根。于是，我们得到 \(a_n=r_i^n\) 都是递推关系 \((*)\) 的解。
根据 \((*)\) 的线性性和齐次性，我们得到，对于任意选定的常数 \(c_1,c_2,...c_k\)，
\[a_n=\sum_{i=1}^kc_ir_i^n \]都是 \((*)\) 的解，于是这部分就被证明了。
第二部分
我们要证明，对于任意给出的初值 \(a_0, a_1,...a_{k-1}\)，我们都一定能选定一组常数 \(c_1, c_2, ... c_k\)，使得对于 \(n < k\) 的情况，也有
\[a_n=\sum_{i=1}^kc_ir_i^n \]成立。
换句话说，这就是要证明如下方程组
\[\begin{equation*} \begin{cases} (\text{when}\ n=0):c_1+c_2+...+c_k=a_0 \\ (\text{when}\ n=1):c_1 r_1+c_2 r_2+...+c_k r_k=a_1 \\ (\text{when}\ n=2):c_1 r_1^2+c_2 r_2^2+...+c_k r_k^2=a_2 \\ ... \\ (\text{when}\ n=k-1):c_1 r_1^{k-1}+c_2 r_2^{k-1}+...+c_k r_k^{k-1}=a_{k-1} \end{cases} \end{equation*} \]对于任意的 \(c_1, c_2, ... c_k\) 都有解。证明这个命题对于高中生来说可能有些困难。但是，如果你有线性代数基础，下面的证明并不难理解。我们将上方程组改写为矩阵乘向量的形式：
\[\begin{bmatrix} 1 & 1 & \cdots & 1\\ r_{1} & r_{2} & \cdots & r_{k}\\ r_{1}^{2} & r_{2}^{2} & \cdots & r_{k}^{2}\\ \vdots & \vdots & \ddots & \vdots \\ r_{1}^{k-1} & r_{2}^{k-1} & \cdots & r_{k}^{k-1} \end{bmatrix}\begin{bmatrix} c_{1}\\ c_{2}\\ c_{3}\\ \vdots \\ c_{k} \end{bmatrix} =\begin{bmatrix} a_{0}\\ a_{1}\\ a_{2}\\ \vdots \\ a_{k-1} \end{bmatrix}\]于是，\(c_i\) 能被唯一确定的充要条件就变为矩阵
\[\begin{bmatrix} 1 & 1 & \cdots & 1\\ r_{1} & r_{2} & \cdots & r_{k}\\ r_{1}^{2} & r_{2}^{2} & \cdots & r_{k}^{2}\\ \vdots & \vdots & \ddots & \vdots \\ r_{1}^{k-1} & r_{2}^{k-1} & \cdots & r_{k}^{k-1} \end{bmatrix} \]可逆。也即其行列式不为 \(0\)。
事实上，这是著名的范德蒙德(Vandermonde)矩阵。运用数学归纳法，能够证明其行列式即为：
\[\prod_{1\le i < j \le k}(r_j-r_i) \]因此，当特征方程无重根时，也即 \(r_1,r_2,...r_k\) 互不相同时，它的确不为 \(0\)。于是，这证明了对于 \(n < k\)的情况，定理依然成立。
综上所述，我们对 \(n \in \mathbb{N}^*\) 的情况都证明了这样的解是成立的，因此我们成功完成了对这个定理的证明。
后记
事实上，关于这个结论我们有：
- 对于这样的常系数齐次线性关系，我们求解其通项公式的障碍在于高次方程的求根，而后者通常是困难的。
- 对于有重根的情况，我们假设是 \(s\) 重根，只需要更改重根前的系数 \(c_i\) 为一个 \(s-1\) 阶的关于 \(n\) 的多项式即可。系数依然唯一。由于本人水平精力有限，不做进一步探讨。