组合数学求解递推关系2.ppt

3 线性 递推关系 1、定义称为 k阶线性递推关系。若系数不依赖 n，称为常系数递推式，否则称为变系数递推式。递推关系 例 1二阶常系数线性齐次式。 一阶变系数线性非齐次式。 例 2 Fibonacci数列 例 3 等比数列 二阶变系数线性齐次式。 一阶常系数齐次 等差数列 一阶常系数非齐次 阶乘数列 一阶变系数齐次 性质 2 2、线性齐次递推式解的性质性质 1 对线性齐次递推式：线性齐次递推式的所有解构成线性空间：1）解空间对线性运算封闭；2）所有解可以用一组基的线性组合表示。求解齐次递推式，归结为求出解空间的一组基（一组线性无关的解），根据初始条件确定系数（特解）。 性质 3 对线性齐次递推式：相应的特征方程为：性质 4 对线性齐次递推式例 4特征方程： 特征根： 通解： 解给定初始条件： 特解： 性质 5 对线性齐次递推式例 5特征方程： 二重特征根： 通解： 解性质 6 对线性齐次递推式例 6特征方程： 共轭复根 ： 通解： 解