自然数の累乗の和の公式(1)

数学

OKwaveの数学カテゴリに自然数の「累乗の和の公式」の質問があったので，それにつられてみます．

自然数$n$と$p$に対して，$S_{p}(n)=1^p+2^p+\cdots+n^p$を計算せよ．

という問題です．$p=0$，1，2，3では次のようになります．
\begin{eqnarray*}S_{0}(n)&=&n\\ S_{1}(n)&=&\frac{n(n+1)}{2}\\ S_{2}(n)&=&\frac{1}{6}n(n+1)(2n+1)\\ S_{3}(n)&=&\left\{\frac{n(n+1)}{2}\right\}^2\\ \end{eqnarray*}

高校の教科書風の計算

高校の教科書には$(k+1)^p-k^p$を利用した解法がでていることが多いと思います．ここで$_n\mathrm{C}_{k}$は二項係数とします．
\begin{eqnarray*} 2^{p+1} - 1^{p+1} &=& \sum_{r=0}^{p} {{}_{p+1}\mathrm{C}_{r}} 1^r \\ 3^{p+1} - 2^{p+1} &=& \sum_{r=0}^{p} {{}_{p+1}\mathrm{C}_{r}} 2^r \\ 4^{p+1} - 3^{p+1} &=& \sum_{r=0}^{p} {{}_{p+1}\mathrm{C}_{r}} 3^r \\ &\vdots&\\ +)~(n+1)^{p+1}-n^{p+1} &=& \sum_{r=0}^{p} {{}_{p+1}\mathrm{C}_{r}} n^r \\ \hline (n+1)^{p+1}-1^{p+1} &=& \sum_{k=1}^{n}\sum_{r=0}^{p} {{}_{p+1}\mathrm{C}_{r}} k^r = \sum_{r=0}^{p} {{}_{p+1}\mathrm{C}_{r}} \sum_{k=1}^{n} k^r = \sum_{r=0}^{p} {{}_{p+1}\mathrm{C}_{r}} S_{r}(n) \end{eqnarray*}
であるので，
\begin{eqnarray} (n+1)^{p+1}-1^{p+1} &=& (p+1) S_p(n) + \sum_{r=0}^{p-1} {{}_{p+1}\mathrm{C}_{r}} S_{r}(n) \end{eqnarray}
となって，求めたい$S_{p}(n)$は出てきました．ついでに，$S_{1}(n),S_{2}(n),\ldots,S_{p-1}(n)$もでてきてしまってますが．$S_r(n)$を何かの$r$乗とみなすとこの形は二項定理にとても似ていることです．

この式は$S_{p}(n)$の漸化式を与えています．二項係数$_n\mathrm{C}_{k}$が絡んでいるので計算は厄介かもしれませんが，下から順番に計算は可能です．$p=0$のときの$S_{0}(n)=n$は与えられていると考えて，$p=1$のときは
\begin{eqnarray*} (n+1)^2 -1^2 &=& 2S_{1}(n) + S_{0}(n)\\ S_{1}(n)&=& \frac{1}{2}(n^2+2n-n)=\frac{n(n+1)}{2} \end{eqnarray*}
$p=2$のときは
\begin{eqnarray*} (n+1)^3 -1^3 &=& 3S_{2}(n) + 3S_{1}(n)+S_{0} \\ 3S_{2}(n) &=& (n+1)^3-1 -\frac{3}{2}n(n+1)-n \\ &=& \frac{ 2n^3+6n^2+6n-3n^2 -3n -2n }{2} \\ &=& \frac{n}{2} (2n^3+3n+1) = \frac{1}{2}n(n+1)(2n+1)\\ S_{2}(n)&=&\frac{1}{6}n(n+1)(2n+1) \end{eqnarray*}
$p=3$のときは
\begin{eqnarray*} (n+1)^4-1^4 &=& 4S_{3}(n) + 6S_{2}(n) + 4S_{1}(n) + S_{0}(n) \\ 4S_{3}(n) &=& (n+1)^4-1 - 6S_{2}(n) - 4S_{1}(n) - S_{0}(n) \\ &=& n^4 + 4n^3 +6n^2+ 4n - n(n+1)(2n+1) -2n(n+1) -n \\ &=& n \left\{ n^3 + 4n^2 + 6n +4 -(n+1)(2n+1) -2(n+1) -1 \right\} \\ &=& n ( n^3 +2n^2 +n ) = n^2 (n^2+2n+1) = \left\{n(n+1)\right\}^2 \\ S_{3}&=& \left\{\frac{n(n+1)}{2}\right\}^2 \end{eqnarray*}
$p=4$のときは
\begin{eqnarray*} (n+1)^5-1^5 &=& 5S_{4}(n) + 10S_{3}(n) + 10S_{2}(n) + 5S_{1}(n) + S_{0}\\ 5S_{4}(n) &=& (n+1)^5-1 - 10S_{3}(n) - 10S_{2}(n) - 5S_{1}(n) - S_{0}\\ &=& n^5 + 5n^4 + 10n^3 + 10n^2 + 5n - \frac{5}{2}n^2(n+1)^2 - \frac{5}{3} n(n+1)(2n+1) - \frac{5}{2}n(n+1) -n \\ \frac{5}{n}S_{4}(n) &= & n^4 + \frac{5}{2} n^3 + \frac{5}{3} n^2 - \frac{1}{6} \\ \frac{5\cdot 6}{n}S_{4}(n) &= & 6n^4 + 15n^3+10n^2-1 =(n+1)(2n+1)(3n^2+3n-1)\\ S_{4}(n)&=&\frac{1}{30}n(n+1)(2n+1)(3n^2+3n-1) \end{eqnarray*}

計算の仕方も，煩雑ではありますが見えました．また，以下のような性質も導出した漸化式から分かります．厳密に証明するには帰納法を用いれば容易です

$S_{p}(n)$は以下の性質をもつ．

  • $n$についての$(p+1)$次の多項式である．
  • 最高次の項$n^{p+1}$の係数は$\frac{1}{p+1}$である．
  • $n$を因数としてもつ．
  • $p\ge1$ならば，$(n+1)$を因数としてもつ．

しかし，これでは$S_{p}(n)$の全貌には程遠いです．

差分なる方法を使ってみる

「教科書的な方法」のアイデアの根本は$(k+1)^p-k^p$の和を二通りに計算して，次数を下げるということと，「ずらして足すと途中の項が消える」ことにありました．煩雑ではありますが，計算のしやすいのは間違いなく，コンピュータで再帰的に計算させるにはよい方法だと思います．しかし，公式として何とか書き下したいというときには不向きです．

そこで「ずらして足すと消える」という部分に注目します．関数fに対して，関数$\Delta f$を$(\Delta f)(x)=f(x+1)-f(x)$によって定めて，この$\Delta f$を関数fの差分と呼ぶことにします．

差分の基本的な性質としては，まず以下のものがあります．

関数f，gおよび定数a，bに対して，

  • $\Delta (af+bg) = a(\Delta f)+b(\Delta g)$（線型性）
  • $(\Delta (f')) = (\Delta f)'$（微分との順序交換）
  • $\sum_{k=1}^n (\Delta f)(k) = f(n+1)-f(1)$（差分の和）
  • $\Delta 1=0$
  • $\Delta x^p = \sum_{r=0}^{p-1} {{}_p\mathrm{C}_r}x^r$

これらの証明は容易なので省略します．

さて，$(k+1)^p-k^p$は$f(x)=x^p$とした場合の差分の形です．つまり，差分をとられる関数を先に定めて，
\begin{eqnarray*} \sum_{k=1}^n (\Delta f)(k) = f(k+1)-f(1) \end{eqnarray*}
を用いて，左辺の和の中に連なった$S_{i}(n)$を構築したことになります．しかし，素直に考えれば，左辺の和が直接$S_{p}(n)$になってくれさえすれば解決です．つまり，$(\Delta f)(x)=x^p$となる関数fを求めることさえできればよいことになります．ここで，すべての関数から探そうとすると探索範囲が広すぎるので，多項式だけを考えることにします．さらに，差分をとって一致する多項式は定数項だけの差があるので，定数項は0と仮定します．これらの仮定の下では，「存在すれば一意」となります．整理すると結局

問題
定数項が0の多項式fで$(\Delta f)(x)=x^p$を満たすものは存在するか

となります．

$(\Delta f)(x)=x^p$を$k$回微分すると$(\Delta f^{(k)})(x)=\frac{p!}{(p-k)!}x^{p-k}$です．$p+1$回微分すると0です．任意の実数$x$で，$F(x+1)-F(x)=0$を満たす多項式は定数しかありません．つまり，$f^{(p+1)}$は定数です．したがって，$f^{(p)}(x)=ax+b$（$a$，$b$は定数）となります．$(\Delta f^{(p)})(x)=p!$であることを考えれば，$a=p!$なので，$f^{(p)}(x)=(p!)x+A_{p}$（$A_p$は定数）とおくことにします．記号の整理の都合上，$A_{p+1}=p!$とおいて，
\begin{eqnarray*} f^{(p)}(x) = A_{p+1}x+A_{p} \end{eqnarray*}
です．この積分を繰り返します．
\begin{eqnarray*} f^{(p)}(x) &=& A_{p+1}x+A_{p} \\ f^{(p-1)}(x) &=& \frac{A_{p+1}}{2}x^2+A_{p}x+A_{p-1} \\ f^{(p-2)}(x) &=& \frac{A_{p+1}}{2\cdot3}x^3+\frac{A_{p}}{2}x^2+A_{p-1}x+A_{p-2} \\ &\vdots& \\ f(x)=f^{(0)} &=& \sum_{k=1}^{p+1} \frac{A_{k}}{k!} x^k + A_{0} \end{eqnarray*}
今，$f(0)=0$としているので，$A_0=0$です．

あとはこの係数$A_{i}$（$i=1,2,\ldots,p$）を求める作業が残っています．これは順番に計算できます．
\begin{eqnarray} f^{(p-1)}(x) &=& \frac{p!}{2}x^2+A_{p}x+A_{p-1} \\ \Delta f^{(p-1)}&=& p! x \end{eqnarray}
なので，$p!x = \frac{p!}{2}(2x+1)+A_{p}$より，$A_{p}=-\frac{p!}{2}$となり
\begin{eqnarray*} f^{(p-1)}(x) &=& \frac{p!}{2}x^2 - \frac{p!}{2} x+A_{p-1} \end{eqnarray*}
です．

fはpに依存しているので，これを明示的して，pのときのfを$F_{p}$と書くことにします．つまり，
\begin{eqnarray} F_{p}(x) &=& \sum_{k=1}^{p+1} \frac{A_{k}}{k!} x^k \\ S_{p}(n)&=&F_p(n+1)-F_p(1) \end{eqnarray}
です．

さて，$p=1$とすると，上の計算より
F_{1}(x)=\frac{1}{2}x^2-\frac{1}{2}x
となり，よって，
\begin{eqnarray} S_{1}(n) &=& F_1(n+1)-F_1(1) \\ &=& \frac{1}{2}(n+1)^2-\frac{1}{2}(n+1) = \frac{n(n+1)}{2} \end{eqnarray}

つぎに
\begin{eqnarray*} f^{(p-2)}(x) &=& \frac{p!}{2\cdot3}x^3 - \frac{p!}{2\cdot2} x^2+A_{p-1}x+A_{p-2} \\ (\Delta f^{(p-2)})(x) &=& \frac{p!}{2}x^{2} \end{eqnarray*}
(\Delta f^{(p-2)})を上の「展開式」から計算して，比較すれば $A_{p-1}=\frac{p!}{12}$が得られます．これより，
\begin{eqnarray*} F_{2}(x)&=&\frac{2}{2\cdot3}x^3 - \frac{2}{2\cdot2} x^2+\frac{2}{12}x \\ &=& \frac{1}{3}x^3 -\frac{1}{2}x^2 +\frac{1}{6}x \\ S_2(n)&=&F(n+1)-F(1) \\ &=& \frac{1}{3}(n+1)^3 - \frac{1}{2}(n+1)^2 +\frac{1}{6}(n+1) \\ &=& \frac{1}{6}n(n+1)(2n+1) (=\frac{1}{3}x^3 +\frac{1}{2}x^2 +\frac{1}{6}x) \end{eqnarray*}

これを続けていけば，$A_{p-2},A_{p-3},\ldots,A_{1}$が計算できるのは明らかです．係数を順番に求めていけばよいのですが，求める係数は一回の係数比較で一個だけなので，実は定数項だけを追いかければよいこともわかります．つまり，
\begin{eqnarray*} A_{p+1-k} = - \sum_{r=2}^{k+1} \frac{A_{p+r-k}}{r!} \quad (k\ge 1)\end{eqnarray*}
です．これによると，
\begin{eqnarray*} A_p &=& -\sum_{r=2}^{2} \frac{A_{p+r-1}} {r!}= -\frac{A_{p+1}}{2} =-\frac{p!}{2} \\ A_{p-1} &=& -\sum_{r=2}^{3} \frac{A_{p+r-2}} {r!} = -\left( \frac{A_p}{2!} + \frac{A_{p+1}}{3!} \right) \\ &=& -\left( -\frac{p!}{4} + \frac{p!}{6} \right) = \frac{p!}{12} \\ A_{p-2} &=& -\sum_{r=2}^{4} \frac{A_{p+r-3}} {r!} = -\left( \frac{A_{p-1}}{2!} + \frac{A_{p}}{3!} + \frac{A_{p+1}}{4!} \right)\\ &=& -\left( \frac{p!}{24} - \frac{p!}{12} + \frac{p!}{24} \right) = 0 \end{eqnarray*}
と計算できて，$p=3$のときは，
\begin{eqnarray*} F_{3}(x) &=& \frac{1}{4}x^4-\frac{1}{2}x^3 +\frac{1}{4}x^2 \\ S_{3}(n) &=& F_{3}(n+1)-F_3(1) &=& \frac{1}{4}x^4+\frac{1}{2}x^3 +\frac{1}{4}x^2 \\ &= &\left\{\frac{n(n+1)}{2}\right\}^2 \\ \end{eqnarray*}
と計算できます．

下から順番に計算していくのは変わりませんが，二項係数は消えましたし，教科書風の方法と比べて，最終的な計算そのものは簡便になりました．これなら何とか計算できますが，もうちょっと簡略化できます．

最初に戻ると，$F_{p}(x+1)-F_p(x)=x^p$，$F_p(0)=0$だったわけです．したがって，$F_p(1)=F_p(0)+0^p = 0$です．また，$F_p(x+1)=F_p(x)+x^p$です．これらより
\begin{eqnarray*} S_{p}(x)=F_p(x)+x^p \end{eqnarray*}
が得られます．今まで計算したものもこの関係が成り立っていますね．
さらに，$S_{p}(0)=F_{p}(0)=0$となり，$S_{p}(-1)=F_p(-1)+(-1)^p$，$F_{p}(0)-F_{p}(-1)=(-1)^pより，$S_{p}(-1)=F_p(0)=0$です．したがって，$S_{p}(n)$は$n(n+1)$で割り切れます（ただし，$p=0$のときは$n$だけです）．以上の議論の結果，

$S_{p}(n)$は以下の性質をもつ．

  • $n$についての$(p+1)$次の多項式である．
  • 最高次の項$n^{p+1}$の係数は$\frac{1}{p+1}$である．
  • $n$を因数としてもつ．
  • $p\ge1$ならば，$(n+1)$を因数としてもつ．

を証明したことになります（実際はもっと一般的なことまで示しています）．

さて，$p=4$の場合を計算してみましょう．
\begin{eqnarray*} -A_{p-3} &=& \frac{A_{p-2}}{2!} + \frac{A_{p-1}}{3!} + \frac{A_{p}}{4!}+\frac{A_{p+1}}{5!} \\ -\frac{A_{p-3}}{p!} &=& \frac{1}{12\cdot3!} + \frac{1}{2\cdot 4!} + +\frac{1}{5!} \\ &=& \frac{1}{6\cdot5!} \\ A_{1} = -\frac{1}{30} \end{eqnarray*}
ですので，
\begin{eqnarray*} S_{4}(n) &=& F_{4}(n) + n^4 = \frac{A_5}{5!}n^5 + \frac{A_4}{4!}n^4 + \frac{A_3}{3!}n^2 + \frac{A_2}{2!}n+A_1 + n^4 \\ &=& \frac{1}{5}n^5 -\frac{1}{2} n^4 + \frac{1}{3}n^3 - \frac{1}{30}n + n^4 \\ &=& \frac{1}{5}n^5 + \frac{1}{2} n^4 + \frac{1}{3}n^3 - \frac{1}{30}n \\ &=& \frac{1}{30}n(n+1)(2n+1)(3n^2+3n-1) \end{eqnarray*}

計算結果がだいぶ目に見えるようになってきました．