S(n) = Σ[k=1,n] k/(2^(k-1)) と置く。
2S(n) = Σ[k=2,n+1] (k - 1)/(2^(k-1))
=Σ[k=1,n] (k - 1)/(2^(k-1)) + n/(2^n)
=Σ[k=1,n] k/(2^(k-1)) - Σ[k=1,n] 1/(2^(k-1)) + n/(2^n)
=S(n) - Σ[k=1,n] 1/(2^(k-1)) + n/(2^n)