常系数线性齐次递推关系
设
[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 eq 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}
]
得到以下方程组
[egin{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} ]
这个方程组的系数矩阵为
[egin{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_{1leq 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)，带入初始值
[egin{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]
]