2 通常の代数的手法

まずは、(2) の公式を求める、 通常の代数的な手法を紹介する。 例えば、$S_1(n)$ は、

  $$(k+1)^2 - k^2 = 2k+1$$ (3)

の式を $k=1$ から $k=n$ まで加えると、

$$\sum_{k=1}^n\{(k+1)^2-k^2\} = \sum_{k=1}^n (2k+1) = 2S_1(n)+S_0(n)$$

となるが、この左辺は

$$\begin{eqnarray*}\lefteqn{\sum_{k=1}^n\{(k+1)^2-k^2\} } \\ &=& \{2^2+3^2+4^2+\cdots+(n+1)^2\}-(1^2+2^2+3^2+\cdots+n^2) \\ &=& (n+1)^2-1\end{eqnarray*}$$

となり、また $S_0(n)=n$ なので、(3) は

$$(n+1)^2 - 1 = 2S_1(n) + n$$

となり、よって

$$S_1(n) = \frac{1}{2}\{(n+1)^2-1-n\} = \frac{1}{2}(n^2+n) = \frac{n}{2}(n+1)$$

が得られる。同様に $S_2(n)$ は、

  $$(k+1)^3 - k^3 = 3k^2+3k+1$$ (4)

の和を考えることで、

$$(n+1)^3-1 = 3S_2(n)+3S_1(n)+S_0(n)$$

が得られ、よって、

$$\begin{eqnarray*}S_2(n) &=& \frac{1}{3}\{(n+1)^3-1-3S_1(n)-S_0(n)\} \\ &=& ... ... \\ &=& \frac{1}{6}(2n^3+3n^2+n) \ =\ \frac{n}{6}(n+1)(2n+1)\end{eqnarray*}$$

となる。

このようにして、帰納的に $S_j(n)$ $(0\leq j\leq p-1)$ の式 から $S_p(n)$ を得るのが標準的な手法であり、 原理的に同じようにすればできる、という方法が示されて通常は終わりで、 高校や大学の教科書でこの先、すなわち $S_p(n)$ の漸化式を導いたり、 「ファウルハーバーの定理」を紹介、証明したりすることはまずない。