遞推關系式求解：T(n)=T(n-1)+n/2 及 T(n)=8T(n-1)-15T(n-2)

題目

1. T(n) = T(n-1) + n/2, T(1) = 1
2. T(n) = 8T(n-1) - 15T(n-2), T(1) = 1, T(2) = 4

詳細求解

(1) 一階線性非齊次遞推

T(n) = T(n-1) + n/2
     = T(n-2) + (n-1)/2 + n/2
     = ...
     = T(1) + Σ_{k=2}^{n} k/2
     = 1 + (1/2) * Σ_{k=2}^{n} k
     = 1 + (1/2) * [n(n+1)/2 - 1]
     = 1 + (n(n+1) - 2) / 4
     = (n² + n + 2) / 4

驗證：n=1 → (1+1+2)/4=1 ✓；n=2 → (4+2+2)/4=2，遞推 T(2)=T(1)+2/2=1+1=2 ✓。

(2) 二階線性齊次遞推（常係數）

特征方程：r² - 8r + 15 = 0 → (r-3)(r-5)=0 → r₁=3, r₂=5。

通解：T(n) = A·3ⁿ + B·5ⁿ。

代入初始條件：

n=1: 3A + 5B = 1
n=2: 9A + 25B = 4

解得：A = 1/2, B = -1/10。

確切解：

T(n) = (1/2)·3ⁿ - (1/10)·5ⁿ
     = (5·3ⁿ - 5ⁿ) / 10
     = (3ⁿ·5 - 5ⁿ) / 10

驗證：n=1 → (15-5)/10=1 ✓；n=2 → (45-25)/10=2 ≠ 4 ❌ （此處原答案有誤，重新計算）

重新求解：

3A + 5B = 1
9A + 25B = 4
→ 乘第一式 3: 9A + 15B = 3
  減去: 10B = 1 → B = 0.1
  代入: 3A + 0.5 = 1 → A = 1/6

正確確切解：

T(n) = (1/6)·3ⁿ + (1/10)·5ⁿ
     = 3ⁿ⁻¹/2 + 5ⁿ⁻¹/2

驗證：n=1 → 1/2+1/2=1 ✓；n=2 → 3/2+5/2=4 ✓；n=3 → 9/2+25/2=17，遞推 8·4-15·1=17 ✓。