数列の和と差分

前提知識: 数列, 階差数列, 数学的帰納法, 二項係数

高校での出発点：$\sum k^2$ の公式と階差数列

高校では、自然数のべき和について次の公式を習う。
$$ \sum_{k=1}^n k=\frac{n(n+1)}2,\qquad \sum_{k=1}^n k^2=\frac{n(n+1)(2n+1)}6,\qquad \sum_{k=1}^n k^3=\left(\frac{n(n+1)}2\right)^2. $$
たとえば $n=10$ では $1^2+2^2+\cdots+10^2=385$ であり、右辺も $\frac{10\cdot11\cdot21}6=385$ である。
$\sum k^2$ の公式は、教科書では次のように導かれることが多い。恒等式
$$ (k+1)^3-k^3=3k^2+3k+1 $$
を $k=1,2,\dots,n$ について足すと、左辺は隣どうしが打ち消し合って $(n+1)^3-1$ だけが残る。右辺は $3\sum k^2+3\sum k+n$ なので、$\sum k$ の公式を代入して $\sum k^2$ について解けばよい。
もう 1 つの道具が 階差数列 である。数列 $(a_k)$ に対して $b_k:=a_{k+1}-a_k$ を並べた数列を階差数列といい、
$$ a_n=a_1+\sum_{k=1}^{n-1}b_k\qquad(n\ge2) $$
が成り立つ。これも「隣どうしの打ち消し合い」である。
この 2 つの計算には、いくつかの疑問が残る。

• $\sum k^m$ はなぜいつも $n$ の $m+1$ 次の多項式になるのか。
• $(k+1)^3-k^3$ のような「うまい恒等式」は、どうすれば機械的に見つかるのか。
• 係数 $\frac12,\frac16,\frac1{30},\dots$ にはどんな規則があるのか。
  本記事では、階差をとる操作を 差分作用素 $\Delta$ として取り出し、和と差分の関係が微分と積分の関係（微積分学の基本定理）とそっくりであることを見る。微分で $x^k$ が果たす役割を差分では 下降階乗冪 $x^{(k)}$ が果たし、これを使うとべき和の公式が機械的に得られる。最後に、係数の規則が Bernoulli 数 で与えられること（Faulhaber の公式）を、高校の微分・積分だけを使って証明する。
  和と差分を積分と微分に読みかえる対応の全体は 和と積分の対応表 で扱う。

取り出す構造：差分作用素

以下、関数 $f$ は整数全体 $\mathbb{Z}$（あるいは $0$ 以上の整数全体）の上で定義された実数値の関数とする。数列 $(a_k)$ は $k\mapsto a_k$ という関数と同じものと考える。

数列 $(a_k)$ の差分 $\Delta a$ は、高校でいう階差数列そのものである。定義から $\Delta$ は 線形 である：定数 $c$ と関数 $f,g$ について $\Delta(f+g)=\Delta f+\Delta g$、$\Delta(cf)=c\,\Delta f$。また定数関数の差分は $0$ である。
微分との類似ははっきりしている。導関数は $\frac{f(x+h)-f(x)}h$ で $h\to0$ とした極限であり、差分は $h=1$ に固定して極限をとらないものである。

不定和は不定積分（原始関数）の差分版である（差分と和の計算の体系的な扱いは GKP94 §2.6）。次の定理が、本記事全体の土台になる。

1 は微積分学の基本定理 $\int_a^bf(x)\,dx=F(b)-F(a)$ の差分版であり、2 は「積分を上端で微分するともとの関数に戻る」の差分版である。高校の階差数列の公式 $a_n=a_1+\sum_{k=1}^{n-1}b_k$ は、定理の 1 を $F=(a_k)$、$f=(b_k)$、区間の端を $1$ と $n$ として使ったものにほかならない。$(k+1)^3-k^3=3k^2+3k+1$ を足す計算も、$F(x)=x^3$ の差分が $3x^2+3x+1$ であることを使って 1 を適用している。
したがって、べき和を求める問題は $x^m$ の不定和を見つける問題 に言い換えられる。ここで困るのは、微分の公式 $\frac{d}{dx}x^k=kx^{k-1}$ に当たる簡単な公式が、差分にはないことである。実際
$$ \Delta x^2=(x+1)^2-x^2=2x+1,\qquad \Delta x^3=3x^2+3x+1 $$
であり、$\Delta x^k$ には $kx^{k-1}$ のほかに余分な項がつく。この余分な項を消すために、$x^k$ の代わりに別の「べき」を使う。

下降階乗冪：差分にとっての「べき」

たとえば $x^{(1)}=x$、$x^{(2)}=x(x-1)$、$x^{(3)}=x(x-1)(x-2)$ である。$n$ が $0$ 以上の整数なら $n^{(k)}={}_n\mathrm{P}_k$（$n$ 個から $k$ 個を並べる順列の数）であり、$\binom nk=\frac{n^{(k)}}{k!}$ である。$k>n$ なら因子 $n-n=0$ を含むので $n^{(k)}=0$ となる。
記号には流儀があり、$x^{(k)}$ を $x^{\underline k}$ や $(x)_k$ と書く本も、$x^{(k)}$ や $(x)_k$ で上昇階乗冪 $x(x+1)\cdots(x+k-1)$ を表す本もある。

これは微分の公式 $\frac{d}{dx}x^k=kx^{k-1}$ と同じ形である。thm-psd-ftc の 1 と組み合わせると、積分の公式 $\int_0^nx^k\,dx=\frac{n^{k+1}}{k+1}$ の差分版が得られる。

後半の式は Pascal の三角形で斜めに並ぶ数の和が、その終わりの右下の数に等しいことを表し、ホッケースティック恒等式 と呼ばれる（二項係数 の恒等式）。
例　$k=1$ では $\sum_{j=0}^{n-1}j=\frac{n(n-1)}2$ である。$k=2$ では $\sum_{j=0}^{n-1}j(j-1)=\frac{n(n-1)(n-2)}3$ であり、$n=4$ で左辺 $0+0+2+6=8$、右辺 $\frac{4\cdot3\cdot2}3=8$ である。
高校で「$k(k+1)$ の和は $\frac13n(n+1)(n+2)$」「$k(k+1)(k+2)$ の和は $\frac14n(n+1)(n+2)(n+3)$」と覚える公式も、この系の言い換えである。実際 $k(k+1)(k+2)=(k+2)^{(3)}$ なので、$j=k+2$ とおくと
$$ \sum_{k=1}^nk(k+1)(k+2)=\sum_{j=3}^{n+2}j^{(3)}=\sum_{j=0}^{n+2}j^{(3)}=\frac{(n+3)^{(4)}}4=\frac{n(n+1)(n+2)(n+3)}4 $$
である（$j=0,1,2$ の項は $0$）。
負の番号の下降階乗冪　$k\ge1$ に対して $x^{(-k)}:=\dfrac1{(x+1)(x+2)\cdots(x+k)}$ と定めると、同じ計算で $\Delta x^{(-k)}=-k\,x^{(-k-1)}$ が確かめられる。$k=1$ では
$$ \Delta x^{(-1)}=\frac1{x+2}-\frac1{x+1}=-\frac1{(x+1)(x+2)}=-x^{(-2)} $$
である。したがって $\sum_{k=1}^n\frac1{k(k+1)}=\sum_{j=0}^{n-1}j^{(-2)}=\bigl[-j^{(-1)}\bigr]_{j=0}^{j=n}=1-\frac1{n+1}=\frac n{n+1}$ となる。高校で「部分分数に分けて打ち消す」と教わる計算は、$x^{(-2)}$ の不定和が $-x^{(-1)}$ であることを使っている。

主定理：べき和は $n$ の $(m+1)$ 次多項式

$x^{(k)}$ の和は cor-psd-sum-falling ですぐに求まる。そこで、ふつうのべき $x^m$ を下降階乗冪の 1 次結合で書き直せばよい。たとえば
$$ x^2=x(x-1)+x=x^{(2)}+x^{(1)},\qquad x^3=x^{(3)}+3x^{(2)}+x^{(1)} $$
である（右辺を展開すれば確かめられる）。この係数を与えるのが第 2 種 Stirling 数である。

第 2 種 Stirling 数が全射の個数から出ることは 場合の数の数え方の体系 で扱う。
漸化式から $S(m,k)=0$（$k>m$）、$S(m,m)=1$、$S(m,1)=1$（$m\ge1$）がわかる。小さい値は次のとおりである。

$S(m,k)$ には数え上げの意味がある：$m$ 個の区別できる玉を、区別しない $k$ 個の箱に、空の箱がないように分ける方法の数（$m$ 元集合を $k$ 個の空でない部分集合に分割する方法の数）である。実際、$m+1$ 個目の玉が単独で 1 つの箱を占める分け方は $S(m,k-1)$ 通り、そうでない分け方は、残り $m$ 個を $k$ 個の箱に分けてから $m+1$ 個目をどれかの箱に入れるので $k\,S(m,k)$ 通りであり、同じ漸化式を満たす（初期値も一致する）。たとえば $\{1,2,3\}$ を 2 つに分ける方法は $\{1\}\{2,3\}$、$\{2\}\{1,3\}$、$\{3\}\{1,2\}$ の $3=S(3,2)$ 通りである。

計算例　$m=2$ では $S(2,1)=S(2,2)=1$ なので
$$ \sum_{j=0}^{n-1}j^2=\frac{n^{(3)}}3+\frac{n^{(2)}}2=\frac{n(n-1)(n-2)}3+\frac{n(n-1)}2=\frac{n(n-1)(2n-1)}6 $$
である。$n$ を $n+1$ に置きかえると、高校の公式 $\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}6$ になる。$m=3$ では
$$ \sum_{j=0}^{n-1}j^3=\frac{n^{(4)}}4+n^{(3)}+\frac{n^{(2)}}2=\frac{n^2(n-1)^2}4 $$
であり、$n\to n+1$ として $\sum_{k=1}^nk^3=\frac{n^2(n+1)^2}4$ を得る。
高校の方法との違いは、「うまい恒等式」を探す必要がないことである。$x^m$ を下降階乗冪に直す段階（$S(m,k)$ の表を引くか、漸化式で作る）と、各項を cor-psd-sum-falling で足す段階に分かれ、どちらも機械的である。

階差をくり返す：多項式の特徴づけ

thm-psd-power-sum により、べき和の数列 $a_n=\sum_{k=1}^nk^m$ は $n$ の多項式である。逆に、ある数列が多項式で書けるかどうかは、階差を何回かとることで判定できる。その根拠が次の Newton の公式である（階差による多項式の当てはめは Lev24 §4.3 にも詳しい）。

逆向きに、$f$ が $d$ 次の多項式（$d\ge1$）なら $\Delta f$ は $d-1$ 次の多項式である（$\Delta x^d=dx^{d-1}+(\text{低次})$ から最高次の項が 1 つ下がる）。よって $\Delta^df$ は $0$ でない定数、$\Delta^{d+1}f=0$ である。まとめると、数列が $d$ 次以下の多項式で表される ⇔ 階差を $d+1$ 回とると $0$ になる である。
計算例　$a_n=\sum_{k=1}^nk^2$ の値 $0,1,5,14,30,55,\dots$（$n=0,1,2,\dots$）から階差をくり返すと次の表になる。

各段の左端 $0,1,3,2$ が $(\Delta^ka)_0$ なので、thm-psd-newton により
$$ a_n=0+\binom n1+3\binom n2+2\binom n3=\frac{n(n+1)(2n+1)}6 $$
である（右辺を展開すると一致する）。ただしこの計算で「$\Delta^3a$ がずっと $2$ である」ことを確かめるには、$a$ が $3$ 次多項式であることを別に知っている必要がある（ここでは thm-psd-power-sum がそれを保証する）。有限個の値を見るだけでは結論できないことは、後の反例で見る。

Bernoulli 数と Faulhaber の公式

thm-psd-power-sum でべき和は求まるが、$n$ について展開したときの係数の規則は見えにくい。$\sum_{k=1}^nk^m$ を展開して並べると
$$ \begin{aligned} \sum_{k=1}^nk&=\tfrac12n^2+\tfrac12n,\\ \sum_{k=1}^nk^2&=\tfrac13n^3+\tfrac12n^2+\tfrac16n,\\ \sum_{k=1}^nk^3&=\tfrac14n^4+\tfrac12n^3+\tfrac14n^2,\\ \sum_{k=1}^nk^4&=\tfrac15n^5+\tfrac12n^4+\tfrac13n^3-\tfrac1{30}n \end{aligned} $$
となる。最高次の係数は $\frac1{m+1}$、次は常に $\frac12$ で、その先に $\frac16,\ 0,\ -\frac1{30}$ のような数が現れる。これらを統一的に与えるのが Bernoulli 数である。

$m=1$ の式 $B_0+2B_1=0$ から $B_1=-\frac12$、$m=2$ の式 $B_0+3B_1+3B_2=0$ から $B_2=\frac16$ である。続けると
$$ B_3=0,\quad B_4=-\frac1{30},\quad B_5=0,\quad B_6=\frac1{42},\quad B_8=-\frac1{30},\quad B_{10}=\frac5{66},\quad B_{12}=-\frac{691}{2730} $$
となる（$B_7=B_9=B_{11}=0$）。$B_1$ を $+\frac12$ とする流儀もあり、本によって違う（後の thm-psd-faulhaber の 2 つの式がその違いに対応する）。
Bernoulli 多項式は $B_0(x)=1$、$B_1(x)=x-\frac12$、$B_2(x)=x^2-x+\frac16$ などである。次の 2 つの性質は、定義から直ちに出る。

• 微分：$m\ge1$ で $B_m'(x)=m\,B_{m-1}(x)$。実際 $\binom mj(m-j)=m\binom{m-1}j$ なので $B_m'(x)=\sum_{j=0}^{m-1}\binom mj(m-j)B_jx^{m-j-1}=m\sum_{j=0}^{m-1}\binom{m-1}jB_jx^{m-1-j}$ である。
• 端点の値：$m\ge2$ で $B_m(1)=B_m(0)$。実際 $B_m(1)=\sum_{j=0}^m\binom mjB_j=B_m+\sum_{j=0}^{m-1}\binom mjB_j$ であり、最後の和は定義の式（$m-1\ge1$ の場合）により $0$ である。$B_m(0)=B_m$ と合わせて $B_m(1)=B_m(0)$ となる。

計算例　$m=4$ では $B_0=1,\ B_1=-\frac12,\ B_2=\frac16,\ B_3=0,\ B_4=-\frac1{30}$ を第 2 式に代入して
$$ \sum_{k=1}^nk^4=\frac15\Bigl(n^5+5\cdot\tfrac12n^4+10\cdot\tfrac16n^3+0-5\cdot\tfrac1{30}n\Bigr)=\frac{n^5}5+\frac{n^4}2+\frac{n^3}3-\frac n{30} $$
である。$n=3$ で $\frac{243}5+\frac{81}2+9-\frac1{10}=98$、実際 $1+16+81=98$ である。
証明の範囲　本記事で証明したのは、Bernoulli 数の定義（漸化式）から出発して、lem-psd-bernoulli-delta、thm-psd-faulhaber、prop-psd-bernoulli-odd が成り立つことまでである。次の事実は 証明しない（GKP94 §6.5）。

• 母関数による特徴づけ：$|t|<2\pi$ で $\dfrac t{e^t-1}=\sum_{m\ge0}B_m\dfrac{t^m}{m!}$。
• 偶数番目の符号は交互に変わり（$B_2>0,\ B_4<0,\ B_6>0,\dots$）、$|B_{2m}|$ は $m$ が大きいと急速に大きくなる。これは Euler の公式 $\sum_{k=1}^\infty\frac1{k^{2m}}=\frac{(-1)^{m+1}(2\pi)^{2m}B_{2m}}{2\,(2m)!}$ から従う（$m=1$ が Basel問題 の $\frac{\pi^2}6$）。

名前について　thm-psd-faulhaber は Bernoulli の公式とも呼ばれる。Faulhaber は、奇数乗の和が $T:=\frac{n(n+1)}2$ の多項式になることにも気づいていた（Knu93）。たとえば
$$ \sum_{k=1}^nk^3=T^2,\qquad \sum_{k=1}^nk^5=\frac{T^2(4T-1)}3,\qquad \sum_{k=1}^nk^7=\frac{T^2(6T^2-4T+1)}3 $$
である。奇数乗について一般にこれが成り立つことは本記事では証明しない（証明は Knu93）。

部分和分：部分積分の差分版

積の微分 $(fg)'=f'g+fg'$ から部分積分が得られるのと同じように、積の差分から 部分和分 が得られる。

微分の積の公式と違い、第 2 項の $g$ が $1$ つずれて $g(x+1)$ になる。この「ずれ」を忘れるのが部分和分の典型的な誤りである。
例　$\sum_{k=0}^{n-1}k\,2^k$ を求める。$\Delta2^k=2^{k+1}-2^k=2^k$ なので、$f(k)=k$、$g(k)=2^k$ とすると $\Delta g=2^k$、$\Delta f=1$ であり、
$$ \sum_{k=0}^{n-1}k\,2^k=n2^n-0-\sum_{k=0}^{n-1}2^{k+1}=n2^n-(2^{n+1}-2)=(n-2)2^n+2 $$
である。$n=4$ で左辺 $0+2+8+24=34$、右辺 $2\cdot16+2=34$ である。高校では「$S-2S$ をつくる」方法でこの和を求めるが、部分和分はそれを一般の $f,g$ に広げたものである。$2^x$ は $\Delta2^x=2^x$ を満たすので、差分の世界で指数関数 $e^x$（$\frac{d}{dx}e^x=e^x$）の役割を果たす。
例　調和数 $H_k:=1+\frac12+\cdots+\frac1k$（$H_0=0$）は $\Delta H_k=\frac1{k+1}=k^{(-1)}$ を満たし、差分の世界の $\log$ に当たる。$f(k)=H_k$、$g(k)=k$ として部分和分を使うと
$$ \sum_{k=0}^{n-1}H_k=nH_n-\sum_{k=0}^{n-1}(k+1)\cdot\frac1{k+1}=nH_n-n $$
となる。これは積分 $\int_1^x\log t\,dt=x\log x-x+1$ の差分版である。$n=3$ で左辺 $0+1+\frac32=\frac52$、右辺 $3\cdot\frac{11}6-3=\frac52$ である。
部分和分は解析学では Abel の級数変形法 とも呼ばれ、Dirichlet の判定法（交代級数の収束判定はその特別な場合）などの証明に使われる（Abelの級数変形法）。
積分の側で部分積分のどちらを微分するかの選び方は 部分積分の使い方 で扱う。

反例と注意

整数値多項式　thm-psd-newton からは次もわかる。多項式 $f$ がすべての整数 $n\ge0$ で整数値をとるなら、$(\Delta^kf)(0)$ はすべて整数なので、$f(x)=\sum_kc_k\binom xk$（$c_k$ は整数）と書ける（両辺は $0$ 以上の整数で一致し、無限個の点で一致する多項式は等しい）。係数そのものは整数とは限らない：$\binom x2=\frac{x^2-x}2$ は整数値をとるが係数は $\pm\frac12$ である。べき和の公式で分数の係数と整数の値が両立するのは、このためである。

数学オリンピックの問題から

多項式の外挿（アメリカ数学オリンピック（1975 年）第 3 問）

アメリカ数学オリンピック（1975 年）第 3 問は、次の内容の問題である（ここでは自分の言葉で述べる）：$n$ 次の多項式 $P(x)$ が $k=0,1,\dots,n$ について $P(k)=\frac k{k+1}$ を満たすとき、$P(n+1)$ を求めよ。
答は $P(n+1)=\dfrac{n+1+(-1)^{n+1}}{n+2}$ である（$n$ が奇数なら $1$、偶数なら $\frac n{n+2}$）。
高校数学で解く　$Q(x):=(x+1)P(x)-x$ は $n+1$ 次以下の多項式で、$x=0,1,\dots,n$ で $0$ になる。よって $Q(x)=c\,x(x-1)\cdots(x-n)$ と書ける。$x=-1$ を代入すると $Q(-1)=1$、右辺は $c(-1)^{n+1}(n+1)!$ なので $c=\frac{(-1)^{n+1}}{(n+1)!}$ である。$x=n+1$ を代入すると $(n+2)P(n+1)-(n+1)=c\,(n+1)!=(-1)^{n+1}$ となり、答を得る。
大学数学で見ると　$P$ は $n$ 次多項式なので $\Delta^{n+1}P=0$ である。thm-psd-newton の証明と同じく $\Delta^{n+1}=(E-I)^{n+1}=\sum_{k}\binom{n+1}k(-1)^{n+1-k}E^k$ と展開して $x=0$ での値を見ると、
$$ P(n+1)=\sum_{k=0}^n(-1)^{n-k}\binom{n+1}kP(k) $$
という 外挿公式 が、どんな $n$ 次以下の多項式でも成り立つ。$P(k)=1-\frac1{k+1}$ を代入し、$\frac1{k+1}\binom{n+1}k=\frac1{n+2}\binom{n+2}{k+1}$ と、二項係数の交代和 $\sum_{j=0}^N(-1)^j\binom Nj=0$（$N\ge1$）を使うと、
$$ \sum_{k=0}^n(-1)^{n-k}\binom{n+1}k=1,\qquad \sum_{k=0}^n(-1)^{n-k}\binom{n+1}k\frac1{k+1}=\frac{1+(-1)^n}{n+2} $$
となり、$P(n+1)=1-\frac{1+(-1)^n}{n+2}$ で同じ答が出る。
高校の解き方は「$n+1$ 個の根をもつ多項式を因数分解する」発想で、この問題の値 $\frac k{k+1}$ に合わせた工夫が要る。大学の見方では、値が何であっても、$n$ 次多項式の $n+2$ 個の連続した値は $(n+1)$ 階の差分が $0$ という 1 本の 1 次式で結ばれている、という一般的な事実に帰着する。問題の値に依存するのは、最後の二項係数の和の計算だけである。

さらに先へ

• Euler–Maclaurin の和公式：Bernoulli 数を使うと、和 $\sum_{k=a}^{b-1}f(k)$ を積分 $\int_a^bf(x)\,dx$ と端点での導関数の値で表す公式が得られる。$f$ が多項式なら項が有限で終わり、thm-psd-faulhaber に戻る（証明しない。GKP94 §9.5）。
• ゼータ関数の値：$\sum_{k\ge1}k^{-2m}$ は $\pi^{2m}$ と $B_{2m}$ で書ける（Basel問題 はその $m=1$）。解析接続した Riemann ゼータ関数では $\zeta(-m)=-\frac{B_{m+1}}{m+1}$（$m\ge1$）となり、べき和の公式と同じ数が負の整数点に現れる（証明しない）。
• 第 1 種 Stirling 数：逆向きに $x^{(k)}$ を $x^j$ の 1 次結合で書く係数で、その絶対値は $k$ 個の元の置換をサイクルの個数で分類した数である（GKP94 §6.1）。

関連項目

• 前提: 数列, 階差数列, 二項係数, 数学的帰納法
• 前に読む: 二項定理と組合せの恒等式
• 次に読む: 和と積分の対応表, 積分と和の類似
• 関連（高校数学）: 部分積分の使い方, 場合の数の数え方の体系, Newtonの恒等式（高校数学）
• 発展: Euler-Maclaurinの和公式, Basel問題, Riemannゼータ関数, 線形漸化式, 下降階乗冪, Stirling数, Bernoulli数
• 比較: 微積分学の基本定理, 部分積分, Abelの級数変形法