>>772
S(n) = Σ[k=1→n](k^2)/(2^k)
2S(n) = Σ[k=1→n](k^2)/(2^(k-1)) = Σ[k=0→(n-1)]((k+1)^2)/(2^k)

2S(n)-S(n) = 1-((n^2)/(2^n))+Σ[k=1→(n-1)](2k+1)/(2^k)
= 1-((n^2)/(2^n))+2Σ[k=1→(n-1)]{k/(2^k)} + Σ[k=1→(n-1)]{1/(2^k)}

Σ[k=1→(n-1)]{1/(2^k)} は等比数列の和
Σ[k=1→(n-1)]{k/(2^k)} についても同じように、2倍して引く手法で求まる。