（组合数学笔记）递推关系小结及典型题分析

文章目录

• ​​递推关系简介​​
• ​​常用性质及公式​​
• ​​典型例题及应用​​
• ​​小结​​

递推关系简介

递推关系（递归关系）是高中数学递推数列部分的推广，属于离散数学的范畴，是用其自身来定义的一个公式。常见的有汉诺塔问题（）和Fibonacci兔子问题（）。

常用性质及公式

• 递推关系解的线性组合还是其解。
• 二阶齐次递推关系，其特征方程对应的三种解的情况：

1. 为个不同实根，
2. 为重根，即：，有：
3. 为一对共轭复根，即，有：

• 定理： 非齐次递推关系特解形式

  设非齐次递推关系右端项， 是的多项式，则非齐次递推关系有形如的特解，其中是齐次递推关系特征方程的重根；如果不是特征方程的根，则取；是与同次数的多项式。

典型例题及应用

• 特殊行列式求值问题（找0元最少的行或列展开）

  解：设行列式值为。将该行列式按首行展开，再将第二项按首列展开，可得

  于是推得。特征方程为，

  代入初值得：

• 设表示从格点开始的长度为步的路径数，每步只允许下列三种走法之一：

  且不允许出现和这两种走法。试求序列的表达式。

  解：

  分析题目，若第一步走，则后面可选择的走法无限制，即有种走法；若第一步走，则后面只能选择走或者，走时，无限制，为，而走时，后面仍可选择走或者，…直到走完第步(为方便理解，可参看下图(1)。以此类推，可得的递推关系式为

  但是这个递推式不易求解，为此可先变换形式为：

  由此得：

  得：求解特征方程，得，由可得，.

小结