おもしろい漸化式の問題

$a_0=m$のときの一般項を$a_{m,n}$と書くことにする．すなわち
$$a_{m,0}=m,a_{m,n+1}={\displaystyle \frac{1}{n+2}}((m+1{)}^{n+2}-1-\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k\cdot a_{m,k})$$
と書き直す．まず，$m=0$のときを考える(問題文で$m$は自然数と書いており正の整数だと捉えた人もいるだろうが，今回の解法ではどちらにしろ$m=0$の場合を考える必要がある)．
$$a_{0,0}=0,a_{0,n+1}=-{\displaystyle \frac{1}{n+2}}\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k\cdot a_{0,k}$$
となる．一般項はすぐにわかるように$a_{0,n}=0$である．
さて，ここからがこの漸化式の面白いところである．$a_{m,n}$の$n$に関しての漸化式を式変形し整理していく．
$$\begin{array}{rl}{a}_{m,n+1}& ={\displaystyle \frac{1}{n+2}}((m+1{)}^{n+2}-1-\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k\cdot a_{m,k})\\ & ={\displaystyle \frac{1}{n+2}}(\sum _{k=0}^{n+2}{}_{n+2}{\mathrm{C}}_k{m}^k-1-\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k\cdot a_{m,k})\\ & ={\displaystyle \frac{1}{n+2}}(m^{n+2}+(n+2)m^{n+1}-1+\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k{m}^k-\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k\cdot a_{m,k})\\ & ={\displaystyle \frac{1}{n+2}}(m^{n+2}+(n+2)m^{n+1}-1-\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k(a_{m,k}-m^k))\end{array}$$
$b_{m,n}=a_{m,n}-m^n,b_{m,0}=m-1$とおくと
$$\begin{array}{rl}{b}_{m,n+1}& ={\displaystyle \frac{1}{n+2}}(m^{n+2}+(n+2)m^{n+1}-1-\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k\cdot b_{m,k})-m^{n+1}\\ & ={\displaystyle \frac{1}{n+2}}(m^{n+2}-1-\sum _{k=0}^n{}_{n+2}{\mathrm{C}}_k\cdot b_{m,k})\end{array}$$
となり，$b_{m,n}=a_{m-1,n}$であるとわかる．よって次の等式が成り立つ．
$$a_{m,n}-a_{m-1,n}=m^n$$
これで$m$に関する階差数列を求めることができた．よって数列$\{a_n\}$の一般項は
$$a_n=a_{0,n}+\sum _{k=1}^m(a_{k,n}-a_{k-1,n})=\sum _{k=1}^m{k}^n$$
により${\displaystyle a_n=\sum _{k=1}^m{k}^n}$となる．