常系数线性齐次递推关系
设
\[h_0,h_1,h_2,\cdots ,h_n,\cdots
\]
是一个数列，称这个数列满足k阶线性递推关系是指存在量\(a_1,a_2,\cdots ,a_k\)和量\(b\)，使得
\[h_n=a_1h_{n-1}+a_2h_{n-2}+\cdots+a_kh_{n-k}+b
\]
若量\(b\)是常数0，则称线性递推关系是齐次的；若量\(a_1,a_2,\cdots ,a_k\)都是常系数，则称线性递推关系是常系数的。
定理
设q是一个非0数，则\(h_n=q^n\)是下面常系数线性齐次递推关系
\[h_n-a_1h_{n-1}-a_2h_{n-2}-\cdots-a_kh_{n-k}=0
\]
的解，当且仅当q是下面多项式方程
\[x^k-a_1x^{k-1}-a_2x^{k-2}-\cdots-a_k=0
\]
的根。若多项式方程有k个不同的根\(q_1,q_2,\cdots,q_k\)，则\(h_n\)有唯一的通项公式
\[h_n=c_1q_1^n+c_2q_2^n+\cdots+c_kq_k^n
\]
证明：
因为\(h_n=q^n\)为\(h_n-a_1h_{n-1}-a_2h_{n-2}-\cdots-a_kh_{n-k}=0\)的解当且仅当
\[q^n-a_1q^{n-1}-a_2q^{n-2}-\cdots-a_kq^{n-k}=0
\]
又由于假设\(q\neq 0\)，消去\(q^{n-k}\)，得到唯一的方程
\[q^k-a_1q^{k-1}-a_2q^{k-2}-\cdots-a_k=0
\]
所以得出方程有k个根\(q_1,q_2,\cdots,q_k\)，于是\(h_n\)的通解为
\[h_n=c_1q_1^n+c2q_2^n+\cdots+c_kq_k^n
\]
代入数列的初始值
\[h_0=b_0,h_1=b_1,\cdots,h_{k-1}=b_{k-1}
\]
得到以下方程组
\[\begin{cases}
c_1+c_2+\cdots+c_k=b_0\c_1q_1+c_2q_2+\cdots+c_kq_k=b_1\c_1q_1^2+c_2q_2^2+\cdots+c_kq_k^2=b_2\\vdots\c_1q_1^{k-1}+c_2q_2^{k-1}+\cdots+c_kq_k^{k-1}=b_{k-1}\\end{cases} \]
这个方程组的系数矩阵为
\[\begin{bmatrix}
1 & 1 & \cdots & 1\q_1 & q_2 & \cdots & q_k\q_1^2 & q_2^2 & \cdots & q_k^2\\vdots & \vdots & \ddots & \vdots\q_1^{k-1} & q_2^{k-1} & \cdots & q_k^{k-1}\\end{bmatrix}
\]
该矩阵叫做范德蒙矩阵，范德蒙矩阵是可逆的当且仅当\(q_1,q_2,\cdots,q_k\)互不相同，实际上它的行列式为
\[\coprod_{1\leq i < j \leq k}{(q_i-q_j)}
\]
所以当\(q_1,q_2,\cdots,q_k\)互不相同，\(h_n\)便有唯一通解
即得证
斐波那契数列通项公式
由于斐波那契数列为\(f_n=f_{n-1}+f_{n-2}\)，属于常系数线性齐次递推关系。
首先求解方程\(x^2-x-1=0\)的根
\[q_1=\frac{1+\sqrt{5}}{2},q_2=\frac{1-\sqrt{5}}{2}
\]
由于\(f0=0,f1=1\)，带入初始值
\[\begin{cases}
c_1+c_2=0\c_1(\frac{1+\sqrt{5}}{2})+c_2(\frac{1-\sqrt{5}}{2})=1\\end{cases} \]
得到
\[c_1=\frac{1}{\sqrt{5}},c_2=\frac{-1}{\sqrt{5}}
\]
所以
\[f_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]
\]
常系数线性齐次递推关系
原文：https://www.cnblogs.com/HachikoT/p/13844093.html
