>>870
　S_i = 納k=1,n] (k^i){m^(k-1)} とおく.

m=1 のときは
　S_0 = n,　S_1 = n(n+1)/2,　S_2 = n(n+1)(2n+1)/6,　S_3 = {n(n+1)/2}^2.

m≠1 のとき　漸化式は
　S_0 = {(m^n) -1} /(m-1),
　S_1 = {n･(m^n) - S_0} /(m-1),
　S_2 = {(n^2)(m^n) - 2S_1 + S_0} /(m-1),
　S_3 = {(n^3)(m^n) - 3S_2 + 3S_1 -S_0} /(m-1),
これに順次代入する。

　S_i = {納k=1,n] (k^i)[(m^k) - m^(k-1)] } /(m-1)
　　　= {納k=1,n] (k^i･m^k - (k-1)^i･m^(k-1)) + 納k=1,n] ((k-1)^i - k^i) m^(k-1) } /(m-1).
　　　　= {(n^i)(m^n) + 納j=0,i-1] (-1)^(i-j)･Ｃ[i,j] S_j } /(m-1).
ここで
　(k-1)^i - (k^i) = 納j=0,i-1] (-1)^(i-j)･Ｃ[i,j]･k^j.
を使った。

眠いのでここまで。