1. 概要
正整数の $0$ 乗和， $1$ 乗和， $2$ 乗和， $3$ 乗和について $$ \begin{aligned} \sum _ {n = 1} ^ N n ^ 0 &= N,\\ \sum _ {n = 1} ^ N n ^ 1 &= \frac12 N(N+1) = \frac12 N ^ 2 + \frac12 N,\\ \sum _ {n = 1} ^ N n ^ 2 &= \frac16 N(N+1)(2N+1) = \frac{1}{3}N ^ 3 + \frac12 N ^ 2 + \frac16 N,\\ \sum _ {n = 1} ^ N n ^ 3 &= \left(\frac12 N(N+1)\right) ^ 2 = \frac{1}{4}N ^ 4 + \frac{1}{2} N ^ 3 + \frac{1}{4} N ^ 2 \end{aligned} $$ といった公式を見たことがある人も多いと思います．
本記事では形式的べき級数の計算を通して，これらの公式を一般化することを目指します．
2. 前提知識
形式的べき級数の基本的な計算，$e ^ x$ の定義と性質．
3. Faulhaber の公式（Bernoulli の公式）
$k$ を非負整数とするとき，$\sum _ {n = 1} ^ N n ^ k$ は $N$ の $k+1$ 次多項式となることが知られています．このことを証明し，多項式の係数列を与える公式である Faulhaber の公式を導出します．
3.1. 公式の導出
$\displaystyle a _ k = \sum _ {n = 1} ^ {N}n ^ k$ として，形式的べき級数 $\displaystyle A(x) = \sum _ {k = 0} ^ {\infty}a _ k\dfrac{x ^ k}{k!}$ を考えてみましょう．これは
$$A(x) = \sum _ {k = 0} ^ {\infty}\left(\sum_{n = 1} ^ {N}n ^ k\right)\frac{x ^ k}{k!} = \sum _ {n = 1} ^ {N} \left(\sum _ {k = 0} ^ {\infty}\frac{(nx) ^ k}{k!}\right) = \sum _ {n = 1} ^ {N}e ^ {nx}$$
と変形できます．
さらに，等比数列の和について成り立つ $\displaystyle \sum _ {n = 1} ^ {N}r ^ n = \dfrac{r ^ {N + 1} - r}{r - 1}$ （$r\neq 1$ の場合）を用いると，次のように変形できます：
$$A(x) = \frac{(e ^ {(N + 1)x} - e ^ x)}{(e ^ x - 1)}=\frac{xe ^ x}{e ^ x - 1}\cdot \frac{e ^ {Nx} - 1}{x}.$$
注意
さて，このうち $\dfrac{xe ^ x}{e ^ x-1}$ が $N$ によらない形式的べき級数であることに注意して，
$$\frac{xe ^ x}{e ^ x-1}=\sum_{i=0} ^ {\infty}b _ ix ^ i$$
により $b_i$ を定めます．さらに
$$\frac{e ^ {Nx} - 1}{x} = \sum _ {j = 0} ^ {\infty}\frac{N ^ {j + 1}}{(j + 1)!}x ^ j$$
を用いれば，
$$A(x) = \frac{xe ^ x}{e ^ x - 1}\cdot \frac{e ^ {Nx} - 1}{x} = \sum _ {i = 0} ^ {\infty}b _ ix ^ i\cdot \sum _ {j = 0} ^ {\infty}\frac{N ^ {j + 1}}{(j + 1)!}x ^ j$$
が分かります．この両辺の $x ^ k$ の係数を比べることで，次が示されます．
$$\frac{xe ^ x}{e ^ x - 1} = \sum _ {i = 0} ^ {\infty}b _ ix ^ i$$ により有理数列 $\{b _ i\}$ を定めると，次が成り立つ： $$\sum _ {n = 1} ^ N n ^ k=\sum _ {i = 0}^k\frac{b _ i\cdot k!}{(k - i + 1)!}N ^ {k - i + 1}.$$
これで， $\sum _ {n = 1} ^ N n ^ k$ が $N$ の $k+1$ 次多項式になることが証明されました．またその係数を求めるには形式的べき級数 $\dfrac{xe ^ x}{e ^ x-1}$ の計算をすればよいことも分かりました．
3.2. 具体例
まず $k$ 乗和の公式を $b_i$ を使って表すと，次のようになります．
$$ \begin{aligned} \sum _ {n = 1} ^ N n ^ 0 &= b _ 0N,\\ \sum _ {n = 1} ^ N n ^ 1 &= \frac12 b _ 0N ^ 2 + b _ 1N,\\ \sum _ {n = 1} ^ N n ^ 2 &= \frac13 b _ 0N ^ 3 + b _ 1N ^ 2 + 2b _ 2N,\\ \sum _ {n = 1} ^ N n ^ 3 &= \frac14 b _ 0N ^ 4 + b _ 1N ^ 3 + 3b _ 2N ^ 2 + 6b _ 3N,\\ \sum _ {n = 1} ^ N n ^ 4 &= \frac15 b _ 0N ^ 5 + b _ 1N ^ 4 + 4b _ 2N ^ 3 + 12b _ 3N ^ 2 + 24b _ 4N,\\ \sum _ {n = 1} ^ N n ^ 5 &= \frac16 b _ 0N ^ 6 + b _ 1N ^ 5 + 5b _ 2N ^ 4 + 20b _ 3N ^ 3 + 60b _ 4N ^ 2 + 120b _ 5N. \end{aligned} $$
$b_i$ を計算すると $b_0=1,b_1=\dfrac12,b_2=\dfrac{1}{12},b_3=0,b_4=-\dfrac{1}{720},b_5=0,\ldots$ となり，これらを代入すると
$$ \begin{aligned} \sum _ {n = 1} ^ N n ^ 0&=N,\\ \sum _ {n = 1} ^ N n ^ 1&=\frac12 N ^ 2 + \frac12 N,\\ \sum _ {n = 1} ^ N n ^ 2&=\frac13 N ^ 3 + \frac12 N ^ 2 + \frac16 N,\\ \sum _ {n = 1} ^ N n ^ 3&=\frac14 N ^ 4 + \frac12 N ^ 3 + \frac14 N ^ 2 + 0N,\\ \sum _ {n = 1} ^ N n ^ 4&=\frac15 N ^ 5 + \frac12 N ^ 4 + \frac13 N ^ 3 + 0N ^2 - \frac{1}{30}N,\\ \sum _ {n = 1} ^ N n ^ 5&=\frac16 N ^ 6 + \frac12 N ^ 5 + \frac{5}{12}N ^ 4 + 0N ^ 3 -\frac{1}{12} N ^ 2 + 0N \end{aligned} $$
が得られます．
3.3. 補足：ベルヌーイ数による表示
$k$ 乗和の公式は導かれましたが，上では多くの文献で採用されているものとは異なる形で定理を述べています．現在よく使われているのはベルヌーイ数（Bernoulli number）を使った表示です．他の文献で学んだ場合に混乱が生じないように，本記事でもベルヌーイ数を使って改めて定理を述べておきます．
さらに混乱しやすい要素として，ベルヌーイ数には $2$ 種の定義が存在し，どちらを採用するかによって公式の形に少し差異が生まれます．
有理数 $B_0^-,B_1^-,B_2^-,\ldots$ を $$\frac{x}{e^x-1}=\sum_{i=0}^{\infty} \frac{B_i^-}{i!}x^i$$ により定義する．有理数 $B_0^+,B_1^+,B_2^+,\ldots$ を $$\frac{xe^x}{e^x-1}=\sum_{i=0}^{\infty} \frac{B_i^+}{i!}x^i$$ により定義する．これらを ベルヌーイ数（Bernoulli number）と呼ぶ．
現在では単にベルヌーイ数といった場合には， $B_n^-$ を指すことの方が主流だと思いますが，文献によっては $B_n^+$ を指す場合もあるので注意してください．
小さな $n$ に対するベルヌーイ数の値は次の通りです．
| $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $B_n^-$ | $1$ | $-\dfrac12$ | $\dfrac16$ | $0$ | $-\dfrac{1}{30}$ | $0$ | $\dfrac{5}{66}$ | $0$ | $-\dfrac{691}{2730}$ | $0$ | $\dfrac{7}{6}$ |
| $B_n^+$ | $1$ | $\dfrac12$ | $\dfrac16$ | $0$ | $-\dfrac{1}{30}$ | $0$ | $\dfrac{5}{66}$ | $0$ | $-\dfrac{691}{2730}$ | $0$ | $\dfrac{7}{6}$ |
次の補題から，$B_n^+$ と $B_n^-$ の値の差が生じるのは $n=1$ の場合に限られることが分かります．
次が成り立つ．
- $n \neq 1$ ならば $B_n^+ = B_n^-$．
- $B_1^+ = \frac{1}{2}$，$B_1^- = -\frac{1}{2}$．
- $n$ が $1$ 以外の奇数ならば $B_n^+ = B_n^- = 0$．
$f(x)=\dfrac{x}{e ^ x - 1}$, $g(x)=\dfrac{xe ^ x}{e ^ x - 1}$ とすると， $g(x) = f(x) + x$ が成り立ちます．ここから 1. および， $B_1^+-B_{1}^-=1$ が分かります．
さらに $g(x)=\dfrac{x}{1-e^{-x}}=\dfrac{-x}{e^{-x}-1}=f(-x)$ が成り立ちます．このことから $n$ が奇数ならば $B_n^++B_n^-=0$ が成り立ちます．
これらを合わせると 2, 3 が成り立つことも分かります． $\blacksquare$
$\sum_{n=1}^N n^k$ について，次が成り立つ： $$ \begin{aligned} \sum _ {n = 1} ^ N n ^ k &= \frac{1}{k + 1}\sum _ {i = 0} ^ {k} \binom{k + 1}{i}B _ i ^ + N ^ {k - i + 1}\\\ &= \frac{1}{k + 1}\sum _ {i = 0} ^ {k}\binom{k + 1}{i}B _ i ^ - (-1) ^ iN ^ {k-i+1}. \end{aligned} $$
$2$ つめの等号は 【補題 3】 より $B _ i ^ + = (-1) ^ iB _ i ^ -$ が成り立つことから分かります． $1$ つめの等号について，【定理 1】 の右辺と 【定理 4】 の右辺が一致することを確認しましょう．次が成り立つことを示せばよいです：
$$\dfrac{b_i\cdot k!}{(k-i+1)!}=\frac{1}{k + 1}\binom{k+1}{i}B _ i ^ +$$
これは $b_i=\dfrac{B_i^+}{i!}$ と同値ですが， $b_i,B_i^+$ の定義よりこれらはどちらも $[x ^ i]\dfrac{xe ^ x}{e ^ x - 1}$ に等しいので成り立ちます． $\blacksquare$
3.4. 補足：Lagrange 補間による方法
競技プログラミングで $\sum _ {n = 1} ^ N n ^ k$ を求める必要が生じた際には，必ずしも上のような $k$ 乗和の公式を求める必要はありません．
$F(N) = \sum _ {n = 1} ^ N n ^ k$ とするとき，$F(N)$ は $N$ の $k+1$ 次多項式になります．そして， $F(0), F(1), \ldots, F(k), F(k+1)$ を求めることは，繰り返し二乗法で $0 ^ k, \ldots, k ^ k$ を求めることで $\mathrm{O}(k\log k)$ 時間の計算量でできます（各素数の $k$ 乗のみを求めたあと $(ab) ^ k=a ^ kb ^ k$ を用いることで $\mathrm{O}(k)$ 時間で求めることもできます）．よって Lagrange 補間を用いれば， $F(N)$ を $\mathrm{O}(k)$ 時間で計算することができます．
よって，Faulhaber の公式そのものが必要となる場面は少ないです．
4. 発展
$k$ を非負整数として $r$ を $r\neq 1$ であるような定数とするとき， $\displaystyle\sum _ {n = 0} ^ {N - 1}r ^ nn ^ k$ について考えてみましょう（簡略化のため総和の範囲を $0\leq n\leq N-1$ としました）．上で扱った Faulhaber の公式とほとんど同じ方法により，この総和も求めることができます．
$\displaystyle a _ k = \sum _ {n = 0} ^ {N - 1}r ^ nn ^ k$ として， $\displaystyle A(x)=\sum _ {k = 0} ^ {\infty} a _ k\dfrac{x ^ k}{k!}$ とします．このとき
$$A(x) = \sum _ {n = 0} ^ {N - 1} (re ^ x) ^ n = \dfrac{1-(re ^ x) ^ N}{1-re ^ x}=\dfrac{1}{1-re ^ x}\cdot \left(1-(re ^ x) ^ N\right)$$
と計算することができます． $\dfrac{1}{1 - re ^ x}=\sum _ {i = 0} ^ {\infty} c _ ix ^ i$ により $c _ i$ を定義すれば，
$$A(x) = \sum _ {i = 0} ^ {\infty} c _ ix ^ i\cdot \left(1 - r ^ N\sum _ {j = 0} ^ {\infty}\dfrac{N ^ j}{j!}x ^ j\right)$$
が成り立ちます．ここから
$$\sum _ {n = 0} ^ {N - 1}r ^ n n ^ k = k! c _ k - r ^ N\left(\sum _ {i = 0} ^ k\frac{k!c_i}{(k-i)!}N ^ {k-i}\right)$$
を導くことができます．
4.1. 具体例
$r=2$ とすると， $c _ 0 = -1,c _ 1 = 2,c _ 2 = -3$ であり， $$ \begin{aligned} \sum _ {n = 0} ^ {N - 1}2 ^ nn ^ 0&=c _ 0-2 ^ Nc _ 0 = -1+2 ^ N,\\ \sum _ {n = 0} ^ {N - 1}2 ^ nn ^ 1&=c _ 1-2 ^ N(c _ 0N+c _ 1) = 2+2 ^ N(N - 2),\\ \sum _ {n = 0} ^ {N - 1}2 ^ nn ^ 2&=2c _ 2-2 ^ N(c _ 0N ^ 2+2c _ 1N + 2 c _ 2) = -6+2 ^ N(N ^ 2 - 4N + 6) \end{aligned} $$ が得られます．
5. 関連問題
- https://judge.yosupo.jp/problem/bernoulli_number
- https://codeforces.com/contest/622/problem/F
- https://atcoder.jp/contests/KeioPC2025/tasks/KeioPC2025_e
問題について
2 は $\sum _ {n = 1} ^ N n ^ k$ を計算する問題で，3.4 節で述べたように $\mathrm{O}(k)$ 時間で解くことができます．また少し計算量はタイトになりますが，Faulhaber の公式を使って $\mathrm{O}(k\log k)$ 時間で解くこともできます．
3 はいくつかの解法がありますが，Faulhaber の公式を使う方法が比較的簡単です．
6. まとめ
本記事では，形式的べき級数を用いて $\sum _ {n = 1} ^ N n ^ k$ や $\sum_{n=0} ^ {N-1}r ^ n n ^ k$ のような和を求める公式を導出する方法を解説しました．
これらの公式は競技プログラミングで実用する機会は多くはないと思います（私はどちらも使用経験があります）．しかし，中高数学の勉強を通して興味を持つ人が多くいるだろう題材であること，形式的べき級数を用いて非常に簡潔に証明されることから，この題材を解説してみました．楽しんでいただければ幸いです．
7. 参考文献
- Wikipedia．ファウルハーバーの公式．https://ja.wikipedia.org/wiki/ファウルハーバーの公式．（閲覧日: 2026-03-31）．
- Wikipedia．ベルヌーイ数．https://ja.wikipedia.org/wiki/ベルヌーイ数．（閲覧日: 2026-03-31）．
- Wikipedia．Bernoulli number．https://en.wikipedia.org/wiki/Bernoulli_number．（閲覧日: 2026-03-31）．
文献 1 ではベルヌーイ数の定義として $B_n^+$ が採用されています．
文献 2 ではベルヌーイ数の定義として $B_n^-$ が採用されていますが，$B _ n ^ {\pm}$ の定義の違いにより $S_k(n+1)$ に関する公式の記述に誤りがあるようです．
