线性递推数列算法研究
引言
常系数递推关系是组合数学中的一个研究方向,线性递推关系是最常见的递推关系,本文
将介绍递推数列的相关理论与算法
1. 线性递推数列
1.1 线性递推数列与递推方程
定义1 如果数列数列
满足递推方程
其中
是常数,则称数列
是线性递推数列
注意,
满足任何一个线性递推多项式即可,例如
不是线性递推方程,但我们不难得到
,因此
是线性递推数列
1.2 线性递推数列的通项公式
线性递推数列的通项公式可以通过如下方式求解:
先求递推公式对应的特征方程
的解,根据代数基本定理,
次多项式有
个根(重根重复计算)
如果特征方程有
个单根
,则递推方程的解为
如果有
重根
,以
替代
即可
将解代入递推方程即可验证其正确性(证明略),而
是由数列的初值条件
确定的
这个求解过程与常微分方程的通解的求解过程几乎异曲同工,读者可自行研究其中的联系
,本文不作讨论
例1 求斐波那契数列
的通项公式
解 线性递推方程
的特征方程为