（組合數學筆記）遞推關系小結及典型題分析

文章目錄

• ​​遞推關系簡介​​
• ​​常用性質及公式​​
• ​​典型例題及應用​​
• ​​小結​​

遞推關系簡介

遞推關系（遞歸關系）是高中數學遞推數列部分的推廣，屬于離散數學的範疇，是用其自身來定義的一個公式。常見的有漢諾塔問題（）和Fibonacci兔子問題（）。

常用性質及公式

• 遞推關系解的線性組合還是其解。
• 二階齊次遞推關系，其特征方程對應的三種解的情況：

1. 為個不同實根，
2. 為重根，即：，有：
3. 為一對共轭複根，即，有：

• 定理： 非齊次遞推關系特解形式

  設非齊次遞推關系右端項， 是的多項式，則非齊次遞推關系有形如的特解，其中是齊次遞推關系特征方程的重根；如果不是特征方程的根，則取；是與同次數的多項式。

典型例題及應用

• 特殊行列式求值問題（找0元最少的行或列展開）

  解：設行列式值為。将該行列式按首行展開，再将第二項按首列展開，可得

  于是推得。特征方程為，

  代入初值得：

• 設表示從格點開始的長度為步的路徑數，每步隻允許下列三種走法之一：

  且不允許出現和這兩種走法。試求序列的表達式。

  解：

  分析題目，若第一步走，則後面可選擇的走法無限制，即有種走法；若第一步走，則後面隻能選擇走或者，走時，無限制，為，而走時，後面仍可選擇走或者，…直到走完第步(為友善了解，可參看下圖(1)。以此類推，可得的遞推關系式為

  但是這個遞推式不易求解，為此可先變換形式為：

  由此得：

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

小結