一題遞迴關係式，數學請教

Question

題目為
S(0) = 0
S(n) = 3S(n-1)+3n


S(n) = 3S(n-1)+3n
       = 9S(n-2)+9(n-1)+3n
       = ...........
       = 3^nS(n-n)+3^n(1)+3^(n-1)(2)+...+3^(2)(n-1)+3n
      *= 3^n(1)+3^(n-1)(2)+...+3^(2)(n-1)+3n
      *= 1/4*3^(n+2)-3/2n-9/4

答案如上，我想問的是上面打*號的這兩行
推導到星號為止我了解，但數學不好不知最後答案怎麼算出來的

希望有人可以幫我解釋一下，希望越清楚越好

在這邊先多謝了！！！

sponge · Accepted Answer

最近這系統真的濫用自動檢舉，回答程式語法者都很無辜

在下認為應該是半形中括號或冒號等作祟

所以底下回答貼看看，堅持不用中括號

您 * 的第一條可寫成一般像的形式：

3^n(1)+3^(n-1)(2)+...+3^(2)(n-1)+3n = Σ 3^i(n+1-i)

註：Σ都是 i 從 1 到 n

Σ的一般項分二種討論

1. 3^i(n+1)

Σ中變數是 i, 所以 (n+1) 可提出來：

Σ 3^i(n+1)
=(n+1)Σ 3^i
=(n+1)(3+9+...+3^n), 用公比 3 的等比級數
=(n+1)( 3^(n+1)-3 )/2

2. Σ i*3^i

此部分使用生成函數 (generating function) 的方式推導：

1+x+...+x^n = Σ x^i = ( x^(n+1)-1 )/(x-1), 公比 x 的等比級數

上式兩邊對 x 微分成

1+2x+...+nx^(n-1) = Σ i*x^(i-1) = (n+1)x^n/(x-1) - ( x^(n+1)-1 )/(x-1)^2

兩邊同乘以 x, 造出Σ i*x^i

x+2x^2+...+nx^n = Σ i*x^i = (n+1)x^(n+1)/(x-1) - ( x^(n+2)-1 )/(x-1)^2

x=3 即欲推導的結果

因此拿以上結果簡化Σ 3^i(n+1-i)

Σ 3^i(n+1-i)
=( Σ 3^i(n+1) ) - Σ i*3^i
=(n+1)( 3^(n+1)-3 )/2 - (n+1)3^(n+1)/2 + ( 3^(n+2)-1 )/2^2
=3^(n+2)/4 - 3n/2 - 9/4

希望以上回答對您有幫助！

戰神派大星 · Answer

冏 我恨這系統... 動不動就違規 到底是哪個字眼...

Tai · Answer

Hi, 版主, 信寄給你了.

由於不管貼答案或是意見都被違規, 
現在只能祈求信件不會違規

今天又違規了 150 points. 
知識+ 的刪除系統這麼愛找級數運算的砸啊

2013-11-25 19:50:37 補充：
sponge 大的經驗收下了 - 半形中括號或冒號，謝謝下次試試看。
看 sponge大的推導也很舒服 :)

一題遞迴關係式，數學請教

3 個解答