第八章 遞迴關係與集合論

考前複習重點整理 | Recurrence Relations & Set Theory

📊遞迴關係基礎概念

遞迴關係 Recurrence Relation
用數列前面的項來定義後面項的數學關係式。就像爬樓梯，要到第n層必須先知道怎麼到第n-1層。
範例：斐波那契數列
F(n) = F(n-1) + F(n-2)

意思：第n項 = 前一項 + 前兩項

數列：1, 1, 2, 3, 5, 8, 13, 21...

初始條件 Initial Conditions
遞迴關係的起始值，決定整個數列的具體數值。
範例

對於 an = 2an-1：

如果 a0 = 1，則數列為：1, 2, 4, 8, 16...

如果 a0 = 3，則數列為：3, 6, 12, 24, 48...

階數 Order/Degree
遞迴關係中用到最遠的前項與當前項的距離。
範例

• an = an-1 + 5 → 一階

• an = an-1 + an-2 → 二階

• an = 3an-2 + an-5 → 五階

🔧線性齊次遞迴關係

線性齊次遞迴關係 Linear Homogeneous Recurrence Relation
必須滿足三個條件：
1. 線性：每項都是一次方（沒有平方、立方）
2. 齊次：等號右邊沒有額外的常數或函數
3. 常數係數：係數不隨n變化
一般形式：an = c1an-1 + c2an-2 + ... + ckan-k

快速判斷技巧

✅ 可以的：an = 3an-1 + 4an-2

❌ 不可以的：

  • an = nan-1 （係數n會變）
  • an = an-1² （有平方）
  • an = an-1 + 5 （有常數5）
特徵方程 Characteristic Equation
解線性齊次遞迴關係的關鍵工具。假設解的形式為 an = rn，代入後得到的方程式。
範例：解 an = 5an-1 - 6an-2

1. 假設 an = rn

2. 代入：rn = 5rn-1 - 6rn-2

3. 除以 rn-2：r² = 5r - 6

4. 特徵方程：r² - 5r + 6 = 0

5. 解得：r = 2 或 r = 3

6. 通解：an = c₁(2)n + c₂(3)n

⚡特殊情況處理

重根情況 Repeated Roots
當特徵方程有重複的根時，解的形式需要修改。
根的情況 解的形式
單根 r crn
二重根 r (c₁ + c₂n)rn
三重根 r (c₁ + c₂n + c₃n²)rn
k重根 r (c₁ + c₂n + ... + cknk-1)rn
非齊次遞迴關係 Non-homogeneous Recurrence Relation
等號右邊有額外的函數 F(n) 的遞迴關係。
形式：an = c₁an-1 + c₂an-2 + ... + F(n)
解法步驟

1. 先解對應的齊次方程（忽略F(n)）

2. 找一個特解（根據F(n)的形式猜測）

3. 通解 = 齊次解 + 特解

🔢位元字串計數問題

位元字串 Bit String
只由 0 和 1 組成的字串。長度 n 表示有 n 個位元。
1 0 1 1 0

長度為5的位元字串範例

常見問題類型

1. 包含連續00的位元字串

思路：用補集，先算不包含的，再用總數減去

2. 不包含連續000的位元字串

思路：考慮結尾是1, 01, 001的情況

範例：不包含連續00的位元字串數量

設 an = 長度n且不包含00的位元字串數量

• 如果結尾是1：前n-1位不能有00 → an-1種

• 如果結尾是0：倒數第二位必須是1（即結尾是10）→ an-2種

遞迴關係：an = an-1 + an-2（類似斐波那契！）

初始條件：a₁ = 2, a₂ = 3

🔵集合論與容斥原理

容斥原理 Inclusion-Exclusion Principle
計算多個集合聯集的元素個數時，先加總再減去重複計算的部分。
兩個集合：|A ∪ B| = |A| + |B| - |A ∩ B|
A
A∩B
B
三個集合：|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
範例：課程選修統計

微積分：50人，程式：40人，統計：30人

微積分且程式：15人，微積分且統計：10人，程式且統計：8人

三科都修：3人

問：至少修一科的學生有幾人？

解：50 + 40 + 30 - 15 - 10 - 8 + 3 = 90人

記憶口訣

「加單減雙加三減四...」

奇數個交集加，偶數個交集減！

📝重要公式速查表

概念 公式 用途
線性齊次遞迴 an = c₁an-1 + c₂an-2 + ... 基本遞迴形式
特徵方程（二階） r² - c₁r - c₂ = 0 求解遞迴關係
不同根的通解 an = A·r₁ⁿ + B·r₂ⁿ r₁ ≠ r₂時
重根的通解 an = (A + Bn)rⁿ r₁ = r₂ = r時
容斥原理（2集合） |A ∪ B| = |A| + |B| - |A ∩ B| 計算聯集大小

🎯考試解題策略

遇到遞迴關係題目

  1. 判斷類型：是否線性？是否齊次？係數是否為常數？
  2. 寫出特徵方程：把an = rⁿ代入
  3. 解特徵方程：找出所有根
  4. 寫通解：注意重根要乘以n的冪次
  5. 用初始條件：求出具體的係數值

遇到位元字串計數

  1. 理解限制條件：不能有什麼？必須有什麼？
  2. 考慮結尾情況：以什麼結尾會符合條件？
  3. 建立遞迴：每種結尾對應前面的哪種情況？
  4. 找初始值：n=1, 2, 3時直接數

遇到集合問題

  1. 畫文氏圖：視覺化幫助理解
  2. 標記已知數值：在圖上標出題目給的數字
  3. 套用容斥原理：記住「加單減雙」
  4. 檢查答案：結果應該合理（不能是負數、不能超過總和）