 | この和を
S[n] = ∑[k:1→n] (2k - 1) 2^(k-1)
と置きます。すると
S[n+1]
= ∑[k:1→n+1] (2k - 1) 2^(k-1)
= 1 + ∑[k:1→n] (2(k+1) - 1) 2^((k+1)-1) ← インデックスを一つずらす
= 1 + 2 ∑[k:1→n] (2k - 1 + 2) 2^(k-1)
= 1 + 2 ∑[k:1→n] { (2k - 1) 2^(k-1) + 2^k }
= 2 S[n] + 2^(n+2) - 3
から、漸化式 S[n+1] - 2 S[n] = 2^(n+2) - 3 が得られます。
両辺 1/2^(n+1) 倍すると
S[n+1]/2^(n+1) - S[n]/2^n = 2 - 3/2^(n+1)
という S[n]/2^n に関する階差が得られ
S[n]/2^n
= S[1]/2 + ∑[k:1→n-1](2 - 3/2^(k+1))
= 1/2 + 2(n - 1) - 3/2 (1 - 1/2^(n-1))
= -3 + 2n + 3/2^n
となります。したがって S[n] = (2n - 3) 2^n + 3 です。
|