[Discrete Mathmatic cheat sheet] — Recurrence Relations

在數學上，遞迴關係（recurrence relation），也就是差分方程式（difference equation）。是一種遞推地定義一個序列的方程式：序列的每一項目是定義為前一項的函數。

1. Solve linear recurrsive relation — Homogeneous
2. Solve linear recurrsive relation — Non-homogeneous
3. Solve recurrsive relation using Generating Function
4. Application problems

Linear Recurrsive relation

其中Cn,Cn-1,….Cn-k 為非零的常數，稱為K階常係數方程式。

當 f(n) = 0，稱為 Homogeneous 。
當 f(n) ≠ 0，稱為 Non-homogeneous 。

Homogeneous Linear Recurrsive relation

我們取其 特徵方程式 ，並且依照根的種類3個Case。

1. 相異根
2. 重根
3. 共軛複數

Non-homogeneous Linear Recurrsive relation

非齊次解=齊次解+特解。

因此，我們需要上述的齊次解再加上特解

我們也將球特解的方式分為3個case

1. 多項式
2. 指數
3. 三角函數

Applications problems

Case I . String problem

[不連續]

長度為n的bit string中，有多少個不含連續0 ?

<Sol>

考慮An為解，則考慮以下兩種case

case1: A[n] = 1,則 An=An-1

case2: A[n] = 0,則 An=An-2

所以 得到 An = An-1+An-2

[偶數]

由{0,1,2,3}組成長度為n的string中，有多少個含有偶數個0 ?

<Sol>

考慮An為解，則考慮以下兩種case

case1: A[n] = 0,則後面長度為n-1的string，只能出現"奇數個0"
因此，有4^(n-1)-An-1

case2: A[n] ≠ 0,則後面長度為n-1的string，只能出現”偶數個0"
共有 3*An-1種 (可能為0、1、2)

所以 得到 An =4^(n-1)-An-1 + 3*An-1 = 4^(n-1)+ 2*An-1