數列與遞迴的題目

1)n + 2 = A + B + ... + C (正整數 A , B , ... , C ≥ 2) 有 b(n+2) 種表示
⇒
n + 2 = A-2 個1之和 + 2 + B-2 個1之和 + 2 + ... + C-2 個1之和 + 2
有 b(n+2) 種表示
⇒
n = A-2 個1之和 + 2 + B-2 個1之和 + 2 + ... + C-2 個1之和
有 b(n+2) 種表示但 A-2 , B-2 , C-2 ≥ 0 , 故
n = A-2 個1之和 + 2 + B-2 個1之和 + 2 + ... + C-2 個1之和 有 a(n) 種表示,這表明 a(n) = b(n+2)。以 b(6) = a(4) 為例 :
6 = 2 + 2 + 2 對應 4 = 2 + 2 ,
6 = 2 + 4 = 2 + (1+1+2) 對應 4 = 2 + 1 + 1 ,
6 = 3 + 3 = (1+2) + (1+2) 對應 4 = 1 + 2 + 1 ,
6 = 4 + 2 = (1+1+2) + 2 對應 4 = 1 + 1 + 2 ,
6 = 6 = (1+1+1+1+2) 對應 4 = 1 + 1 + 1 + 1。
2)1 表為1或2之和有1種方法 : 1 , 故 a(1) = 1。
2 表為1或2之和有2種方法 : 1 + 1 和 2 , 故 a(2) = 2。
對於正整數 n ≥ 3 ,
把 n 表示成1或2之和時最後一個分拆數為1的共有 a(n-1) 種,
這是因為此時非所有非最後的分拆數之和 = n-1 ,
把 n 表示成1或2之和時最後一個分拆數為2的共有 a(n-2) 種,
這是因為此時非所有非最後的分拆數之和 = n-2 , 故有 a(n) = a(n-1) + a(n-2)。