线性递推数列算法研究1
需积分: 0 149 浏览量
2022-08-03
15:45:02
上传
评论
收藏 547KB PDF 举报
线性递推数列算法研究
引言
常系数递推关系是组合数学中的一个研究方向，线性递推关系是最常见的递推关系，本文将介绍递推数
列的相关理论与算法
1. 线性递推数列
1.1 线性递推数列与递推方程
定义1 如果数列数列 满足递推方程
其中 是常数，则称数列 是线性递推数列
注意， 满足任何一个线性递推多项式即可，例如 不是线性递推方程，但我们不
难得到 ，因此 是线性递推数列
1.2 线性递推数列的通项公式
线性递推数列的通项公式可以通过如下方式求解：
先求递推公式对应的特征方程
的解，根据代数基本定理， 次多项式有 个根（重根重复计算）
如果特征方程有 个单根 ，则递推方程的解为
如果有 重根 ，以 替代 即可
将解代入递推方程即可验证其正确性（证明略），而 是由数列的初值条件
确定的
这个求解过程与常微分方程的通解的求解过程几乎异曲同工，读者可自行研究其中的联系，本文不作讨
论
例1 求斐波那契数列 的通项公式
解 线性递推方程 的特征方程为
特征方程有两个实根
因此线性递推方程的通解为
评论0