线性递推方程通解的特征根解法

简单的说，对于一个数列，设 f ( n ) f(n) f(n)为该数列的第n项，如果我们找到了一个递推式，使得f(n)可以表示为它前面的若干项的常系数一次多项式，则称它是一个线性递推数列。 如斐波那契数列： f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2) 就是一个线性递推方程。 卡特兰数列： f ( n ) = ∑ i = 0 n − 1 f ( i ) f ( n − 1 − i ) f(n)=\sum_{i=0}^{n-1}f(i)f(n-1-i) f(n)=∑i=0n−1​f(i)f(n−1−i)就不是一个线性递推方程。 线性递推方程又可以分为齐次和非齐次两种。 齐次线性递推方程是指除了数列中的若干项的线性组合外，没有其他部分了。 如f(n)=f(n-1)+f(n-2)。这是一个齐次线性递推方程。 而如果还存在其他项且不为0，则是非齐次线性递推方程。 如果f(n)=f(n-1)+f(n-2)+C(n)，C(n)是一个非0的项，它可以是常数，也可以是关于n的一个函数。那么它就是非齐次线性递推方程。 如果线性递推方程中f(n)表示为其前k项的线性组合，则称它为k阶线性递推方程。

我们发现，对于一个k阶齐次线性递推方程： (1) a n = p 1 a n − 1 + p 2 a n − 2 + ⋯ + p k a n − k a_n=p_1a_{n-1}+p_2a_{n-2}+\dots+p_ka_{n-k} \tag{1} an​=p1​an−1​+p2​an−2​+⋯+pk​an−k​(1)，要想唯一的确定的该数列，必须给出k个初始值{ a 0 , a 1 , … , a k − 1 a_0,a_1,\dots,a_{k-1} a0​,a1​,…,ak−1​}。如果不给出初始值，则可能会有许多的数列都符合这个递推式。这些数列可以称之为此递推式的通解。 我们发现等比数列比较符合这种齐次线性递推方程式。设公比为q，线性递推方程两边乘上公比，左边可以由 a n a_n an​转移到 a n + 1 a_{n+1} an+1​，等式仍然成立。我们大胆假设 a n = x n , ( x ≠ 0 ) a_n=x^n,(x \neq 0) an​=xn,(x̸​=0),代入上述递推方程式，则有 (2) x n = p 1 x n − 1 + p 2 x n − 2 + ⋯ + p k x n − k x^n=p_1x^{n-1}+p_2x^{n-2}+\dots+p_kx^{n-k} \tag{2} xn=p1​xn−1+p2​xn−2+⋯+pk​xn−k(2) 因为x不为0，所以两边除以 x n − k x^{n-k} xn−k,得到 (3) x k = p 1 x k − 1 + p 2 x k − 2 + ⋯ + p k x^k=p_1x^{k-1}+p_2x^{k-2}+\dots+p_k \tag{3} xk=p1​xk−1+p2​xk−2+⋯+pk​(3) 考虑复根，这个方程有k个根.我们先假设没有重根。那么，这k个根都能使得(1)成立。 于是我们可以得到原k阶齐次线性递推方程(1)的k个数列，第i个数列即是一个公比为 x i x_i xi​的等比数列。 根据乘法分配律，我们知道，如果 α \alpha α和 β \beta β是符合(1)的两个数列，则数列 C 1 α + C 2 β C_1\alpha+C_2\beta C1​α+C2​β也符合式(1)。所以，式(1)的k个解的任意线性组合也是式（1）的解。我们称这k个等比数列为式(1)的基底。于是我们可以知道式(1)的通解可以表示为以下形式： a n = C 1 x 1 n + C 2 x 2 n + ⋯ + C k x k n a_n=C_1x_1^n+C_2x_2^n+\dots+C_kx_k^n an​=C1​x1n​+C2​x2n​+⋯+Ck​xkn​ 设线性递推方程的表示的数列的前k项值为{ b 0 , b 1 , … , b k − 1 b_0,b_1,\dots,b_{k-1} b0​,b1​,…,bk−1​}，则有 (4) { C 1 x 1 0 + C 2 x 2 0 + ⋯ + C k x k 0 = b 0 C 1 x 1 1 + C 2 x 2 1 + ⋯ + C k x k 1 = b 1 … … C 1 x 1 k − 1 + C 2 x 2 k − 1 + ⋯ + C k x k k − 1 = b k − 1 \left \{ \begin{array} {rcl} C_1x_1^0+C_2x_2^0+\dots+C_kx_k^0;=;b_0 \\ \\C_1x_1^1+C_2x_2^1+\dots+C_kx_k^1;=;b_1 \\ \\ \dots \\ \dots \\ \\ C_1x_1^{k-1}+C_2x_2^{k-1}+\dots+C_kx_k^{k-1};=;b_{k-1}\end{array}\right.\tag{4} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​C1​x10​+C2​x20​+⋯+Ck​xk0​C1​x11​+C2​x21​+⋯+Ck​xk1​……C1​x1k−1​+C2​x2k−1​+⋯+Ck​xkk−1​​===​b0​b1​bk−1​​(4)

用矩阵表示为： ( 1 1 … 1 x 1 1 x 2 1 … x k 2 ⋮ ⋮ ⋮ ⋮ x 1 k − 1 x 2 k − 1 … x k k − 1 ) ( C 1 C 2 ⋮ C k ) = ( b 0 b 1 ⋮ b k − 1 ) \left( \begin{matrix} 1 ; 1 ;\dots ; 1 \\ x_1^1 ;x_2^1 ; \dots ;x_k^2 \\ \vdots ; \vdots;\vdots ;\vdots \\ x_1^{k-1} ;x_2^{k-1} ; \dots ;x_k^{k-1} \end{matrix} \right) \left( \begin{matrix} C_1 \\ C_2 \\ \vdots \\ C_k \end{matrix} \right)= \left( \begin{matrix} b_0 \\b_1 \\ \vdots \\b_{k-1} \end{matrix} \right) ⎝⎜⎜⎜⎛​1x11​⋮x1k−1​​1x21​⋮x2k−1​​……⋮…​1xk2​⋮xkk−1​​⎠⎟⎟⎟⎞​⎝⎜⎜⎜⎛​C1​C2​⋮Ck​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​b0​b1​⋮bk−1​​⎠⎟⎟⎟⎞​

其中第一个矩阵为著名的范德蒙德矩阵，它的行列式为 (5) ∏ 1 ≤ j ; k ≤ n ( x k − x j ) \prod_{1\leq j ; k \leq n}(x_k-x_j) \tag{5} 1≤j