ベルヌーイのべき和公式（遊びの数論39）

他のメモへのリンク集。リンク集を飛ばして、このページの前書きへ。本文の目次へ。21、22などの数字は、メモの番号です。

---

このページでは、「ベルヌーイ数を使ったべき和公式」について、二つの初等的証明を紹介します。一つは、有名教科書にあるきちんとした証明。もう一つは、さほど知られてないものの、もっと分かりやすいかもしれない証明。必要な「二項係数の操作」についても、一通りまとめてみました。

他の話題として、無限の和 1 + 1/4 + 1/9 + 1/16 + 1/25 + ··· の値を問う「バーゼル問題」を取り上げ、オーストリアの Hofbauer によって2002年に公開されたアプローチの一部を検討します。バーゼル問題の初等的解法としては、ロシアの Yaglom によるものがエレガントで、ポピュラーですが（別のページで紹介）、 Hofbauer の方法は似ているようで少し違い、別の面白さ・発展性を秘めています。

書き始めたきっかけは、「3月14日の円周率の日にちなんで」という、たわいもないこと。「円周率の偶数乗」の形式をベルヌーイ数の「チート的」計算に使ったら面白いかも…という、伏線的な意味もあります。

---

• 目次。約6の項目があります。2025などの数字は、メモの日付です。
• 2025-03-14　「円周率の2乗」の謎　987ノテッペンカラトビウツレ
• 2025-03-16　1 + 1/2² + 1/3² + 1/4² + … = π²/6 の簡単な証明　バーゼル問題
• 2025-03-22　ベルヌーイのべき和公式: 一応の証明　タイとチリ
• 2025-03-23　ベルヌーイの公式の証明（Knuth 版）　0⁰ = 1
• 2025-03-31　二項係数・超入門　三つの基本と簡単な応用例
• 2025-04-02　二項係数・超入門の補足　抽出と吸収
• 目次の終わり。このページの最初の項目が続きます。

---

2025-03-14　「円周率の2乗」の謎　987ノテッペンカラトビウツレ

#遊びの数論　#ベルヌーイ数の分母　#ζ(2)

π = 3.1415… を2乗すると、
　　3.1415… × 3.1415… = 9.8696…
その 6 分の 1 は π²/6 = 1.6449…。一方、
　　1/1² + 1/2² + 1/3² + 1/4² + ··· = 1/1 + 1/4 + 1/9 + 1/16 + ···
という足し算（平方数の逆数の和）をどんどん続けると、 1/1000² くらまで足した辺りで、和は約 1.644 になり、さらにどんどん足すと、和は π²/6 に近づいていく。 1, 4, 9, 16, ··· の逆数のような「普通の分数」の和が、「円周率の2乗」という奇妙な数と関係している。

1/1 + 1/4 + 1/9 + 1/16 + ··· という足し算を無限に続けた場合、無限個の正の数を足していくのだから、足せば足すほど合計は少しずつ大きくなって、究極的には無限大になるのでは？　もっともな疑問だ！

確かにこのような無限の和は、無限大になることもある。例えば、
　　1/2 + 1/2 + 1/2 + 1/2 + ···
は 1/2 を無限個足すのだから、足せば足すほど和は 0.5 ずつ増えて、際限なくでかくなるのは、火を見るよりも明らか。

もっとも、「無限個の数を足すから」といって、和が無限大になるとは限らない。例えば:
　　1/10 + 1/10² + 1/10³ + 1/10⁴ + ···
　　 = 1/10 + 1/100 + 1/1000 + 1/10000 + ··· = 0.1 + 0.01 + 0.001 + 0.0001 + ··· = 0.1111…
この無限和は 0.1111… という有限の値で、無限大にはならない。ちなみに 0.1111… ってのは 1/9 だ（本題と関係ないが）。

無限個の数の和は、無限大になることも、ならないこともある。

「同じ大きさの数」や「だんだん大きくなる数」を無限個足せば、もちろん結果は無限に大きくなる。でも「だんだん小さくなる数」を足し合わせる場合、上記 0.1111… の例のように、和は無限大にならないかもしれない。では、次の例は、どうだろう？
　　H = 1/1 + 1/2 + 1/3 + 1/4 + ···

足される分数がだんだん小さくなって、先の方の項は 1/1000 とか 1/1000000 とかのすご～く小さい数なんで、「もしかして合算しても無限大にはならないのでは？」って気もする。とはいうものの、「無限個の項」を足すんだから、結果が無限大になったとしても不思議はないし。どっちなんでしょ？

実は、和 H は無限大になる。理由は意外と単純:
　　H = (1/1) + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 + ··· + 1/15) + ···

上のように分けて考えると、一つ目の ( ) 内の 1 個の分数（値は 1）は、もちろん 1/2 より大きいし、二つ目の ( ) 内の 2 個の分数は、どちらも 1/4 より大きい。三つ目の ( ) 内の 4 個の分数は、どれも 1/8 より大きい。四つ目の ( ) 内の 8 個の分数は、どれも 1/16 より大きい。以下同様なので、 H は、
　　(1/2) + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + (1/16 + 1/16 + ··· + 1/16) + ···
より大きい。ってことは、
　　(1/2) + (2/4) + (4/8) + (8/16) + ··· = 1/2 + 1/2 + 1/2 + 1/2 + ···
より大きい。この和は、 0.5 を無限個足し続けることに当たり、足せば足すほどいくらでも大きくなるのだから、それよりさらに大きい H もまた、無限にでかくなるっ！

〔補足〕　実際、 H の最初の1項、次の2項、そのまた次の4項···をそれぞれ足し合わせると、
　　1/1, 1/2 + 1/3 = 5/6, 1/4 + 1/5 + 1/6 + 1/7 = 319/420, ··· 
となって、どの和も 0.5 より大きい。 0.5 より大きくなる十分条件として、次には8項、さらには16項・32項・64項・128項などと、大量の項を動員する必要があるけど、なにしろ項数は無限。1024項だろうが、4096項だろうが、どんなに項をいっぱい使っても、項のストックは無限にある！

てなわけで、「項がだんだん小さくなる」場合でも、無限の足し算の結果は無限大になり得る。「無限の足し算」ってのは、微妙なもの。でまぁ、本題の「円周率の2乗」と関係のある和、
　　f(n) = 1/(1⋅1) + 1/(2⋅2) + 1/(3⋅3) + 1/(4⋅4) + ··· + 1/(n⋅n)
をはどうなのか。 f(n) は n 個の分数の和だが、その n が限りなく大きくなったとき、和は無限大になるのか、ならないのか？！

とりあえず、項の個数 n が有限とすると、f(n) の右辺の…
　　1項目は 1 に等しい
　　2項目 1/(2⋅2) = 1/4 は 1/(1⋅2) = 1/2 より小さい
　　3項目 1/(3⋅3) = 1/9 は 1/(2⋅3) = 1/6 より小さい
　　4項目 1/(4⋅4) = 1/16 は 1/(3⋅4) = 1/12 より小さい
　　　︙
　　n 項目 1/(n⋅n) は 1/((n−1)n) より小さい
［なぜなら分子が 1 の分数は、分母が大きいほど値が小さい］

だから、次の不等式が成り立つ。
　　f(n) = 1 + 1/(2⋅2) + 1/(3⋅3) + 1/(4⋅4) + ··· + 1/(n⋅n) < 1 + (1/(1⋅2)) + (1/(2⋅3)) + (1/(3⋅4)) + ··· (1/((n−1)n))

ところが、
　　1/(1⋅2) = (2 − 1)/(1⋅2) = 2/2 − 1/2 = 1 − 1/2
　　1/(2⋅3) = (3 − 2)/(2⋅3) = 3/6 − 2/6 = 1/2 − 1/3
　　1/(3⋅4) = (4 − 3)/(3⋅4) = 4/12 − 3/12 = 1/3 − 1/4
　　　︙
　　1/((n−1)n) = (n − (n−1))/((n−1)n) = n/((n−1)n) − (n−1)/((n−1)n) = 1/(n−1) − 1/n
なので、これらを上の不等式の右辺各項に順に代入すると:
　　f(n) < 1 + (1/(1⋅2)) + (1/(2⋅3)) + (1/(3⋅4)) + ··· (1/((n−1)n))
　　 = 1 + (1 − 1/2) + (1/2 − 1/3) + (1/3 − 1/4) + ··· + (1/(n−1) − 1/n)　　☆
　　∴　f(n) < 1 + 1 − 1/n = 2 − 1/n < 2　　☆☆

〔注〕　例えば n = 6 なら ☆ は 1 + 1 − 1/2 + 1/2 − 1/3 + 1/3 − 1/4 + 1/4 − 1/5 + 1/5 − 1/6 なので、最初の2項と最後の1項以外の途中の項は、 − と + によって打ち消し合い 1 + 1 − 1/6 だけが残る。 n の値が何であっても、同様に途中の項が消えて ☆☆ の通り。

f(n) の n が限りなく大きくなった場合が、問題の無限和、
　　x = 1 + 1/2² + 1/3² + 1/4² + ···
なんだけど、☆☆ の制約があるので、 n が（1 以上の）何であっても f(n) は決して 2 を超えることはない。つまり x は 2 以下の数である！

他方、 x の各項は正なので、項をいっぱい足せば足すほど和が少しずつ大きくなることは言うまでもない（究極的には 2 を超えられないけれど）。特に、最初の 4 項の和を考えると、
　　1 + 1/4 + 1/9 + 1/25
　　 = 900/900 + 225/900 + 100/900 + 36/900 = 1261/900 = 1.401111…
なので、 x が 1.4 と 2 の間の数であることは確実。

「1.4 と 2 の間」というだけでは、この無限和が謎の分数 π²/6 = 1.644934… に等しいことの証明には程遠い。それでも「平方数の逆数を無限に足すと、円周率の2乗÷6に等しくなる」という現象のムードをちょっぴり味わえる。コンピューターを使って数値計算すると、この無限和を 100 項目まで足した部分和は:
　　1 + 1/2² + 1/3² + ··· + 1/100² = 1.634983…
さらに足してみると:
　　1 + 1/2² + 1/3² + ··· + 1/1000² = 1.643934…
　　1 + 1/2² + 1/3² + ··· + 1/10000² = 1.644834…

1万項も足して、ようやく小数3桁程度の一致。なんとも収束が遅い！

この無限和の値が 1.64 台であること。そして円周率の2乗に関係ある（らしい）こと。それが何の役に立つのかはともかく、なんとも不思議な事実だ。

〔注〕　これは数学上では有名問題であり、約300年前の1740年ごろ、既に Euler によって解決され、その後、いろいろな証明が考えられている。単に好奇の対象というだけでなく、 Bernoulli 数の理論とも関係しているし、複数の重大な未解決問題とも関連している。次回のメモで、この無限和をきちんと扱う。

円周率の2乗って、どんな値だろうか？

14² = 196 と 15² = 225 に留意すると、
　　314² = (300 + 14)² = 90000 + 2⋅300⋅14 + 196 = 90000 + 8400 + 196 = 98596
　　315² = (300 + 15)² = 90000 + 2⋅300⋅15 + 225 = 90000 + 9000 + 225 = 99225
なので A = 9.8596 と B = 9.9225 の間になることは比較的容易に暗算できる。 A は過小、 B は過大だが、 1:5 くらいの割合で、前者の方が、誤差が小さい――というのも π = 3.1415… を 3.14 で近似した場合の誤差（約0.0015）と比べ、 3.15 で近似した場合の誤差（約0.0085）は、ざっと 5 倍大きい。大ざっぱに A を 9.86、 B を 9.92 と見て、両者の差 0.06 を 1:5 で比例配分すると、前者に 0.01 を足した 9.87 がまずまずの近似値となるだろう。これは 9→8→7 という数字の並びなので印象に残るけど、真の値は 9.8696… なので、小数第2位は本当は 7 ではない（それでも 9.87 は 9.8696… の優秀な近似値だ）。

従って π²/6 の大ざっぱな近似値は 9.87/6 だ。暗算では 6 で割る代わりに、いったん 3 で割ってから半分にすると、いくぶん省力的（987 は 8+7 = 15 が 3 の倍数なので 3 で割り切れる）:
　　987/3 = 329　→　半分にして　160 + 4.5 = 164.5
こうして得られる近似値 1.645 は真の値 1.6449… よりわずかに大きいが、大きさの目安としては役立つだろう。

〔付記〕　π² ≈ 9.87 が 10 に近いのは、 √10 = 3.16227766（水色夫婦泣き泣き村々）と π = 3.14159265（産医師異国に婿）がまあまあ近いから。つまり 3.16² ≈ 10 なので 3.14² は 10 より少しだけ小さい。

---

2025-03-16　1 + 1/2² + 1/3² + 1/4² + … = π²/6 の簡単な証明　バーゼル問題

#遊びの数論　#ζ(2)

平方数 1², 2², 3², 4², ··· の逆数の無限和、つまり 1/1 + 1/4 + 1/9 + 1/16 + ··· が π²/6 になることは、幽玄な感じがする。一体なぜこの和は、「円周率の2乗 ÷ 6」という奇妙きてれつな値になるのか？

証明法はいろいろあるが（1999年の [4] は14種を収録）、概して難しい。けれど、初等的な証明も知られている。オーストリアの Hofbauer による簡潔な証明（2002年）を紹介したい。

必要な予備知識は sin, cos などについての、最小限の事柄（弧度法、加法定理など）。総和記号を少しだけ使う。微積分は不要。

ヤコブ兄さんの疑問

円周率は「円周と直径の比」という明快な意味を持つ。一方、「円周率の2乗」というのは（素朴な直観としては）意味不明な概念だ。でも幾つかの領域では、「円周率の n 乗」が重要な役割を果たす。 1 + 1/4 + 1/9 + 1/16 + 1/25 + ··· は、歴史上その最初の発見例だったに違いない。

この無限和がどんな値になるのか？と最初に疑問を持ったのは、イタリアの Mengoli だという。一般的には、スイスの地名を関して Basel problem とか problème de Bâle と呼ばれることが多い。

なぜ「バーゼル問題」と呼ばれるのか？

バーゼルで出版された Jakob (Jacob) Bernoulli の遺作 [2] が語源らしい。この本の中で Bernoulli はこの和を求めることの難しさに言及し、こう書き残した。「われわれが今まで答えを得られないでいるこの件を解明し、知らせてくださる方がいらっしゃれば、大変ありがたく存じます」と。要するに「バーゼル問題」とは、バーゼルで出題された問題（バーゼルの人が「誰かこれ分かる？」と尋ねた問題）の略だろう。

求めたい無限和を x とする:
　　1/1² + 1/2² + 1/3² + 1/4² + 1/5² + 1/6² + 1/7² + 1/8² + ··· = x　　①
①の両辺を 2² つまり 4 で割ると（以下、左辺については最初の 4 項だけ記す）:
　　1/(1²⋅2²) + 1/(2²⋅2²) + 1/(3²⋅2²) + 1/(4²⋅2²) + ··· = x/4

3²⋅2² = 3⋅3⋅2⋅2 = (3⋅2)⋅(3⋅2) = (3⋅2)² = 6² のような関係を使って、上の式を整理すると:
　　1/2² + 1/4² + 1/6² + 1/8² + ··· = x/4　　②
①から②を引くと:
　　1/1² + 1/3² + 1/5² + 1/7² + ··· = 3x/4　　③

②を①と見比べると、次のことが分かる。もし①の（奇数番目の項を無視して）偶数番目の項だけを足し合わせると、その和は②で、①の和 x から見て 1/4 の大きさだ。一方、③を参照すると、もし①の（偶数番目の項を無視して）奇数番目の項だけを足すなら、その和は x の 3/4 だ。

だから x = π²/6 を証明する代わりに、偶数番目の項の和が π²/24 であることを示しても同じことだし（1/6 の 1/4 は 1/24）、あるいは、奇数番目の項の和が π²/8 であることを示してもいい（1/6 の 3/4 は 1/8）。この考察に基づき、以下では Basel 問題を直接解く代わりに、
　　1/1² + 1/3² + 1/5² + 1/7² + ··· = π²/8 = 1.2337005501…
を示すことにする。この無限和は、それ自体としても美しい！

〔追記〕　別証明を掲載。 Hofbauer による下記の証明は、やや技巧的で小難しいけれど、複素数も二項定理も方程式論も必要ないという点において、最もシンプルだと思われる。別証明は美しく、応用性も高く、総和記号を使わずに自然に表現可能だが、より多くの予備知識を必要とする（視野を広げる機会と考えれば、それも悪くない）。二つの証明は、本質的には同系統。

半円の4等分・8等分など

y を任意の角度（ただし 90° = π/2 の倍数以外）とする。すると sin y も cos y も 0 ではない。このとき、
　　1/sin² y + 1/cos² y
という分数の足し算を、通分して計算すると、
　　1/sin² y + 1/cos² y = (cos² y + sin² y/(sin² y cos² y) = 1/(sin² y cos² y)　　《あ》
となる。三角関数の基本性質として cos² y + sin² y = 1 だからだ。

さて cos y は sin (y + π/2) に等しいので^†、《あ》をこう書くこともできる:
　　1/(sin² y cos² y) = 1/sin² y + 1/[sin² (y + π/2)]　　《い》

†　加法定理から sin (y + π/2) = sin y cos (π/2) + cos y sin (π/2) = sin y × 0 + cos y × 1 = cos y。

ところで、倍角の公式^‡ sin 2y = 2 sin y cos y の両辺を平方すると:
　　sin² 2y = (2 sin y cos y)² = 4 sin² y cos² y　　《う》

‡　加法定理から sin 2y = sin (y + y) = sin y cos y + cos y sin y = 2 sin y cos y。

《う》の両辺は等しいのだから、もちろん両辺の逆数も等しい。つまり:
　　1/(sin² 2y) = (1/4)⋅1/(sin² y cos² y)
《い》を代入すると:
　　1/(sin² 2y) = (1/4){1/sin² y + 1/[sin² (y + π/2)]}　　《え》

簡潔化のため、 sin θ の逆数 1/sin θ を csc θ と書くことにする（読み方は cosecant、略して cosec）。 1/(sin² θ) = (1/sin θ)² は csc² θ となる。《え》は、次のように整理される。

補助命題　csc² 2y = (1/4)[csc² y + csc² (y + π/2)]

要するに、与えられた角度の csc²（つまり sin の逆数の平方）は、
　　「半分の角度の csc²」と「半分の角度に 90° を足した角度の csc²」の和
の 1/4 倍に等しい。

補助命題において、 2y = π/2 とすると y = π/4 なんで:
　　csc² (π/2) = (1/4)[csc² (π/4) + csc² (π/4 + π/2)] = (1/4)[csc² (π/4) + csc² (3π/4)]
ところで sin (π/2) は 1 だから、その逆数の平方 csc² (π/2) も 1 に等しい。よって、上記の式は次のように要約される。
　　(1/4){csc² (π/4) + csc² (3π/4)} = 1　　《お》

〔検証〕　sin (π/4) も sin (3π/4) も √2/2 なので、その逆数の平方は 4/2 つまり 2。これが csc² (π/4) であり、 csc² (3π/4) の値でもある。確かに (1/4)(2 + 2) = 1 となって、等式《お》が成立。

次に補助命題で 2y = π/4 とすると:
　　csc² (π/4) = (1/4)[csc² (π/8) + csc² (π/8 + π/2)] = (1/4)[csc² (π/8) + csc² (5π/8)]　　《か》
同様に 2y = 3π/4 とすると:
　　csc² (3π/4) = (1/4)[csc² (3π/8) + csc² (3π/8 + π/2)] = (1/4)[csc² (3π/8) + csc² (7π/8)]　　《き》

《か》《き》を《お》に代入しよう。結果は、次の4項（四つの csc² を足し合わせて 1/4² 倍したもの）から成る:
　　(1/4){(1/4)[csc² (π/8) + csc² (5π/8)] + (1/4)[csc² (3π/8) + csc² (7π/8)]}
　　 = (1/4²){csc² (π/8) + csc² (3π/8) + csc² (5π/8) + csc² (7π/8)} = 1　　《く》

〔参考〕　証明には関係ないけど、《く》を数値的に考えてみると面白い。 sin² θ = (1 − cos 2θ)/2 なので^†、 θ = π/8, 2θ = π/4 とすると、
　　sin² (π/8) = (1 − (√2)/2)/2 = (2 − √2)/4
となって^‡、その逆数から csc² (π/8) = 4/(2 − √2)。 csc² (7π/8) も同じ値。一方、 θ = 3π/8, 2θ = 3π/4 とすると、
　　sin² (3π/8) = (1 − (−(√2)/2))/2 = (2 + √2)/4
となって、その逆数から csc² (3π/8) = 4/(2 + √2)。 csc² (5π/8) も同じ値。従って《く》の { } 内は、
　　4/(2 − √2) + 4/(2 + √2) + 4/(2 + √2) + 4/(2 − √2)
だ。通分すると分母は (2 − √2)(2 + √2) = 2² − 2 = 2。分子には 8 が四つ、 ±8√2 が二つずつ現れ、結局 = (8 × 4)/2 = 16 となる。分母が無理数だらけのゴチャゴチャした和が、きっかり整数 16 になるカタルシス！　《く》の左辺先頭には係数 1/16 があるので、確かに《く》の値は 1 に等しい。

†　cos 2θ = cos² θ − sin² θ = (1 − sin² θ) − sin² θ = 1 − 2 sin² θ なので、
　　2 sin² θ = 1 − cos 2θ
となり、両辺を 2 で割ると sin² θ = (1 − cos 2θ)/2。

‡　右辺では cos 2θ = cos (π/4) = (√2)/2 を使った。少し後では、同様に cos (3π/4) = −(√2)/2 を使う。

こうして生じた { } 内の4項についても、今度は csc² (π/8) を csc² (π/16) + csc² (9π/16) に分割できること、 csc² (3π/8) を csc² (3π/16) + csc² (11π/16) に分割できること、等々は明らかだろう（もちろん分割結果は、全体として再び 1/4 倍される）。つまり、次の8項が生じる:
　　(1/4³){csc² (π/16) + csc² (3π/16) + ··· + csc² (15π/16)} = 1　　《け》

このような「分割」は、何度でも好きなだけ反復できる。《お》を1回目の分割、《く》を2回目の分割、《け》を3回目の分割···と呼ぶと、一般に a 回目の分割結果は、次の形の 2^a 項（その個数の csc² の和）だ:
　　(1/4^a){csc² (π/2^a+1) + csc² (3π/2^a+1) + ··· + csc² ((2^a+1 − 1)π/2^a+1)} = 1　　《こ》

単位円の上半分の半円について、中心角 45° ずつ4等分した場合が《お》、 22.5° ずつ8等分した場合が《く》、 11.25° ずつ16等分した場合が《け》。それぞれ「半円周上の奇数番目の点」（偏角 0° の点を「0番」とする）に対応する sin の逆数の2乗和は、 4, 4² = 16, 4³ = 64, ··· に等しい。《こ》によれば、半円の 2^a+1 等分について、同様の関係が一般的に成り立つ。 sin というのは、もちろん、その円周上の点の縦座標であり、言い換えれば「正弦」の長さ。

なかなかすてきな現象だ！

〔注〕　ここで「分割の回数 a を限りなく大きくすると、どうなるか？」を正確に分析できれば、 Basel 問題を解決できる。けれど、正面から行くと、少々面倒な技術的問題が絡んでくる。今回は正面から取り組まず、比較的分かりやすい「からめ手」を使うことにしたい。

π² を含む分数を挟み撃ち

角度 θ が 0° 以上 90° 未満のとき、つまり
　　条件　0 ≤ θ < π/2　　《さ》
が満たされるとき、
　　sin θ ≤ θ ≤ tan θ
が成り立つ――扇形の面積の求め方を既知とするなら、この不等式は直観的に明らか。ここで大小を比較されている三つの値は、どれも負ではない。それぞれの逆数を考えると（θ ≠ 0 とする）、
　　csc θ ≥ 1/θ ≥ 1/tan θ
となる^†。負でない数を平方しても、大小関係は変わらないので:
　　csc² θ ≥ (1/θ)² ≥ (1/tan θ)²
　　つまり^‡　csc² θ ≥ (1/θ)² ≥ csc² θ − 1　　《し》

†　数が大きいほど、逆数は小さい。 2 < 3 に対する 1/2 > 1/3 のように。

‡　(1/tan θ)² は csc² θ − 1 に等しい。というのも、基本性質 sin θ/cos θ = tan θ の逆数を考えると:
　　cos θ/sin θ = 1/tan θ　　★
ところが cos² θ + sin² θ = 1 の両辺を sin² θ で割ると、
　　cos² θ/sin² θ + 1 = 1/sin² θ　つまり　(cos θ/sin θ)² + 1 = csc² θ
となる。この最後の式の左辺に ★ を代入すると:
　　(1/tan θ)² + 1 = csc² θ　つまり　(1/tan θ)² = csc² θ − 1

今、 N を一定の正の偶数（例えば 10）として、 N/2 種類の角度
　　θ = (1π)/(2N), (3π)/(2N), (5π)/(2N), ···, ((N−1)π)/(2N)
を考えると、どの θ の値も条件《さ》を満たすので、《し》から、次の関係が成り立つ。
　　csc² (1π)/(2N) ≥ ((2N)/(1π))² ≥ csc² (1π)/(2N) − 1
　　csc² (3π)/(2N) ≥ ((2N)/(3π))² ≥ csc² (3π)/(2N) − 1
　　csc² (5π)/(2N) ≥ ((2N)/(5π))² ≥ csc² (5π)/(2N) − 1
　　　　···
　　csc² ((N−1)π)/(2N) ≥ [(2N)/((N−1)π)]² ≥ csc² ((N−1)π)/(2N) − 1

これらの N/2 個の不等式を縦に足し合わせると（より大きいもの同士の和は、より小さいもの同士の和より大きいので）、
　　csc² (1π)/(2N) + csc² (3π)/(2N) + ···
　　 ≥ ((2N)/(1π))² + ((2N)/(3π))² + ···
　　 ≥ csc² (1π)/(2N) − 1 + csc² (3π)/(2N) − 1 + ···
のようになるのだが、この表記ではゴチャゴチャして見通しが悪い。そこで総和記号を使って、下記の《す》のように整理しておく。ただし、
　　項によって変わる奇数　1, 3, 5, ··· , N−1
については 2k−1 と表現して、 k = 1, 2, 3, ···, N/2 としている。
　　∑{k=1 to N/2} csc² ((2k−1)π)/(2N) ≥ ∑{k=1 to N/2} [(2N)/((2k−1)π)]² ≥ {∑{k=1 to N/2} csc² ((2k−1)π)/(2N)} − N/2　　《す》

〔注〕　《す》は、上で書きかけたゴチャゴチャした長い不等式と、全く同じ意味。総和記号によって足し算される最後の項（第 N/2 項）では k = N/2 であり、そのとき (2k−1) は (2(N/2)−1) つまり (N−1) になる。《す》の右端にある −N/2 は、もともとの（N/2 個の）不等式の右端にあった −1 をまとめたもの。

以下では、 N が 8, 16, 32 などの場合、つまり N = 2^a の形の場合を考えよう（a: 正の整数）。すると、不等式《す》の左端の総和は、
　　∑{k=1 to N/2} csc² ((2k−1)π)/(2N) = ∑{k=1 to N/2} csc² ((2k−1)π)/(2^a+1)　　《せ》
となる（N に 2^a を代入して、 2⋅2^a の代わりに 2^a+1 と書いただけ）。

バーゼル問題の解決

話を戻して、《こ》を再掲:
　　(1/4^a){csc² (π/2^a+1) + csc² (3π/2^a+1) + ··· + csc² ((2^a+1 − 1)π/2^a+1)} = 1
これについても総和記号を使って整理し N = 2^a とすると（上の { } 内は、ちょうど 2^a 項ある。これについては後述）、左辺は、次のように《せ》とよく似た形になる:
　　(1/4^a)∑{k=1 to N} csc² ((2k−1)π)/(2^a+1) = 1　　《そ》
《そ》が N = 2^a 項の和であることについて。《そ》の分子の係数には、
　　1, 3, 5, ···, 2N−1
の N = 2^a 種類があって、それらを一括して 2k−1 と表すなら、 k は 1, 2, 3, ···, N の範囲を動く。 N/2 項しかない《せ》と比べると、項の数が 2 倍だ。その点を別にすれば《そ》は《せ》の総和記号と比べ 1/4^a 倍の違いしかなく、うまく《そ》の値と不等式《す》を結び付けることができるかも…。項数が同じでないと扱いにくので、何とかして《せ》の総和の項数を2倍に増やすか、さもなければ《そ》の総和の項数を半分に減らしたい。

実は、形を崩さずに《そ》の項数を半減させる簡単な方法があるっ！　例えば、 e = 2, N = 2^a = 4 のときの
　　(1/4²){csc² (π/8) + csc² (3π/8) + csc² (5π/8) + csc² (7π/8)}
において、 π/8 の sin と 7π/8 の sin は等しいので、それらの逆数の平方 csc² も等しい。 3π/8 と 5π/8 についても同様。だから、後半の項を無視して前半の項だけ足して、値を 2 倍しておけば、半分の項数でも結果は同じ:
　　 = (2/4²){csc² (π/8) + csc² (3π/8)}
また例えば、 e = 3, N = 2^a = 8 のときの
　　(1/4³){csc² (π/16) + csc² (3π/16) + ··· + csc² (13π/16) + csc² (15π/16)}
において、左端と右端の csc² は等しく、左から二つ目・右から二つ目の csc² も等しく、左から三つ目・右から三つ目の csc² も等しく、以下同様なので:
　　 = (2/4³){csc² (π/16) + csc² (3π/16) + csc² (5π/16) + csc² (7π/16)}

より一般的に、《そ》において、k = 1 から N まで足す代わりに、前半の k = 1 から N/2 まで足して値を 2 倍すれば、同じ値が得られる:
　　(1/4^a)∑{k=1 to N} csc² ((2k−1)π)/(2^a+1) = (2/4^a)∑{k=1 to N/2} csc² ((2k−1)π)/(2^a+1) = 1　　《た》

さっそく不等式《す》の各辺を 2/4^a 倍して、《た》と全く同じ式を含むようにしてみる。 N = 2^a, 2N = 2^a+1 なんで、こうなる:
　　(2/4^a)∑{k=1 to N/2} csc² ((2k−1)π)/(2^a+1) ≥ (2/4^a)∑{k=1 to N/2} [(2^a+1)/((2k−1)π)]² ≥ {(2/4^a)∑{k=1 to N/2} csc² ((2k−1)π)/(2^a+1)} − (2/4^a)⋅2^a/2　　《ち》

《ち》の左辺は、《た》によって 1 に等しい。《ち》の右辺は、同じ《た》（1 に等しい）から 1/2^a = 1/N を引いたもの。一方、《ち》の真ん中の部分は、次のように整理される^†（総和記号内の共通因数を外にくくり出して約分）:
　　(2/4^a)∑{k=1 to N/2} (4^a+1)/((2k−1)²π²) = (2/4^a)⋅(4^a+1/π²)∑{k=1 to N/2} (1/(2k−1)²) = (8/π²)∑{k=1 to N/2} (1/(2k−1)²)

†　分数の 2 乗では、分子・分母がそれぞれ 2 乗される。 2^a+1 の 2 乗は 4^a+1 に等しい。形式的には:
　　(2^a+1)² = 2^2a+2 = 2^2(a+1) = (2²)^a+1 = 4^a+1
具体的に、次のように考えてもいいかもしれない。
　　2^a+1 = [2 × 2 × ·· ·  × 2]　　← a+1 個の「2」の積
を 2 乗すると:
　　(2^a+1)² = [2 × 2 × ·· ·  × 2]²
　　 = [2 × 2 × ·· ·  × 2] × [2 × 2 × ·· ·  × 2]　　← (a+1)×2 個の「2」の積
　　 = (2 × 2) × (2 × 2) × ·· ·  × (2 × 2)　　← (a+1) ペアの「2」の積
ペアの数は、個々の「2」の数の半分。そして各ペアの積は 2 × 2 = 4 なので:
　　 = 4 × 4 × ·· ·  × 4　　← (a+1) 個の「4」の積
　　 = 4^a+1

以上の観察をまとめると、不等式《ち》は、こうなる:
　　1 ≥ (8/π²)∑{k=1 to N/2} [(1/(2k−1)²)] ≥ 1 − 1/N　　《つ》

一つ目の不等号の制約により、《つ》の真ん中の部分は 1 を超えることができない。一方、 N が 16, 32, 64, 128, ··· と増大するとき、《つ》の右辺は 1 − 0 = 1 に向かう（なぜなら、そのとき 1/N は 0 に向かう）。従って、 N が ∞ に向かうとき、《つ》の真ん中の部分は（上には高さ 1 の固い「天井」があり、下からは、限りなく高さ 1 に近づく「床」が上昇してくるため）、挟まれてしまって、いやおうなく自分も 1 に向かうしかない。要するに:
　　N → ∞ のとき　(8/π²)∑{k=1 to N/2} [(1/(2k−1)²)] → 1
つまり極限においては、
　　(8/π²)[1/1² + 1/3² + 1/5² + ···] = 1
が成立。上記の式の両辺を π²/8 倍すれば、懸案の極限値が確定する:
　　1/1² + 1/3² + 1/5² + ··· = π²/8
これが示されるべきことだった。∎

この証明法は [1] に基づく。原論文では、 1/(sin² □) の □ が再び分数を含むような「入れ子の分数」が、繰り返し使われている。便宜上、それを csc² □ と記した（意味は同じ）。総和記号との関連では、表現の簡潔化のため、原論文の (2k + 1), k = 0, 1, …, N−1 などの代わりに (2k − 1), k = 1, 2, …, N を使った。

このメモには、原著にない「ごまかし」があることを告白しておく。《さ》で不等号が「等しいか、またはより大きい」なのは θ = 0 の可能性があるからだが、逆数を考えるとき θ ≠ 0 と仮定しているので、《し》では、「等しいか、またはより小さい」を「等しくなく、より小さい」に限定できる（つまり「以下」を「未満」に強化できる）。「X が 1 未満」なら、もちろん「X は 1 以下」なんで、うそをついてるわけじゃないけどね…

厳しく 1 > X > 1−ε の形にせず、緩く 1 ≥ X ≥ 1−ε と記したのは、「X が 1 未満だったら、どこまでいっても X = 1 には、なれないのでは？」という問題をうやむやにするため。実は X < 1 でも、極限値は X = 1 になり得る。例えば、
　　1 + 1/4 + 1/9 + 1/16 + 1/25 + ··· = π²/6
というのは、「左辺の和をどんどん足していくと、右辺にどんどん近づく」（左辺と右辺の誤差を、幾らでも小さくできる）という意味に過ぎず、「どんどん近づく」ということは、必ずしも「どこかでぴったり一致する」という意味ではない。「左辺は右辺未満だけど、左辺の極限値は右辺に等しい」ということだって、あり得る。
　　0.999999…
が 1 未満でありながら、極限値は 1 に等しい――というのは、その好例だろう。だが収束についての厳密な扱いは、簡単ではない。今回は、これでよしとしておく。

[References]
[1] Josef Hofbauer (2002), “A Simple Proof of 1 + 1/2² + 1/3² + ⋯ = π²/6 and Related Identities”
https://homepage.univie.ac.at/josef.hofbauer/piq6.htm
https://homepage.univie.ac.at/josef.hofbauer/02amm.pdf
[2] Jacob Bernoulli (1713), Ars Conjectandi, page 254
https://archive.org/details/jacobibernoulli00bern/page/254/mode/1up
[3] William Dunham (1999), Euler: The Master of Us All, Chapter 3
https://archive.org/details/euler-the-master-of-us-all-dunham/page/39/mode/1up
[4] Robin Chapman (1999, 2003), “Evaluating ζ(2)”
https://empslocal.ex.ac.uk/people/staff/rjchapma/etc/zeta2.pdf
[5] T. J. l’A. Bromwich (1908), An introduction to the theory of infinite series (1st ed.)
https://archive.org/details/introductiontoth00bromuoft/page/187/mode/1up

〔追記〕　Hofbauer [1] において Chapman [4] は「6.」として参照されている。 Hofbauer は、そのうち「証明9番・10番」に触発された（「証明9番」と本質的に同じ内容を別のメモに記した）。 Chapman は「証明9番」を Apostol によるものとしているが、背後には複雑な再発見の歴史がある。 Hofbauer 自身が明記しているように、 Hofbauer 版の証明の基本となるアイデアは既に1908年の [5] に記されている。

---

2025-03-22　ベルヌーイのべき和公式: 一応の証明　タイとチリ

#遊びの数論　#べき和　#ベルヌーイ数の分母　#ベルヌーイの公式

Bernoulli の公式によると、 1 から n までの整数の m 乗和 S_m(n) = 1^m + 2^m + ··· + n^m は、
　　[1/(m+1)]∑{k=0 to m} (m+1 C k) B_k n^m+1−k　　
に等しい。ちょっと難しそうな公式だが、なるべく平明に一応の証明を記したい。

「2乗和・3乗和・4乗和」等の公式をばらばらに考える代わりに、それらを含めた「m 乗和」を統一的に一望できるような理論的基盤が得られれば、大きな収穫だろう。知識の整理・俯瞰（ふかん）にも役立つ。 Bernoulli 数は「m 乗和の計算ツール」というだけではなく、その懐は広く深い。例えば、
　　無限の和　1/1 + 1/4 + 1/9 + 1/16 + ···
が π²/6 に等しいことは玄妙だが、この不思議な和に現れる分数 1/6 も、実は Bernoulli 数 B₂ だ。

最初から全部書くと要点がぼやけるので、総和記号 ∑ の意味と二項係数については、今回は説明を省く。

S_m(n) は、「1 から n までの n 個の整数を、それぞれ m 乗して足した和」。例えば m = 2 なら、
　　S₂(n) = 1² + 2² + ··· + n²
だし、 m = 1 なら、単に
　　S₁(n) = 1 + 2 + ··· + n
だ。 S₁(n) や S₂(n) あるいは S₃(n) くらいまでの具体的な計算法は、多くの方にとって常識の範囲だろう。

Bernoulli の公式は、そうした個別的な「○乗和の公式」より抽象レベルが高く、任意の（0 以上の）整数 m についての「m 乗和の一般公式」だ。その右辺に現れる二項係数は普通に計算できるとして、問題は Bernoulli 数と呼ばれる B_k の値。

具体例として、 m = 4 の場合（4乗和）の Bernoulli 形式 は、次のようになる。
　　S₄(n) = (1/5)∑{k=0 to 4} (5 C k) B_k n^5−k
　　 = (1/5)[(5 C 0) B₀ n⁵⁻⁰ + (5 C 1) B₁ n⁵⁻¹ + (5 C 2) B₂ n⁵⁻² + (5 C 3) B₃ n⁵⁻³ + (5 C 4) B₄ n⁵⁻⁴]
　　 = (1/5)[(5 C 0) B₀ n⁵ + (5 C 1) B₁ n⁴ + (5 C 2) B₂ n³ + (5 C 3) B₃ n² + (5 C 4) B₄ n¹]
　　 = (1/5)[1⋅1n⁵ + 5⋅(1/2)n⁴ + 10⋅(1/6)n³ + 10⋅0n² + 5⋅−1/30n]　　ア

ここで (5 C 0) = 1, (5 C 1) = 5, (5 C 2) = 10 などは分数じゃなく、二項係数。そして、
　　B₀ = 1, B₁ = 1/2, B₂ = 1/6, B₃ = 0, B₄ = −1/30　　イ
が、うわさの Bernoulli 数（の最初の五つ。詳細については後述）。アを整理すると:
　　ア = (1/5)(n⁵ + (5/2)n⁴ + (5/3)n³ − (1/6)n) = (1/5)n⁵ + (1/2)n⁴ + (1/3)n³ − (1/30)n　　ウ

これが Bernoulli 形式の S₄(n) の実体だ。参考までに、因数分解された形に変換すると、
　　ウ = (n/30)(6n⁴ + 15n³ + 10n² − 1) = (1/30)n²(n + 1)²(3n² + 3n − 1)　　エ
となり、一般的な「4乗和の公式」と一致する。

おおむね機械的な単純計算だが、イの値は、一体どこから、どうやって出てくるのか？

定義1　B₀ = 1 とする。1 以上の任意の整数 u について、 u 番の Bernoulli 数 B_u は、次の式によって間接的に定義される。
　　∑{k=0 to u} ((u + 1) C k) B_k = u + 1

〔注〕　総和記号によるこの定義は実は u = 0 に対しても有効で、 B₀ = 1 という結果を与えてくれる。しかしここでは、 u = 0 の場合と u ≥ 1 の場合を別々に考えることにする（後述の定義2・定義3との関係では、それが必要なので）。

まず u = 1 のとき u + 1 = 2 なんで、上の式はこうなる。
　　∑{k=0 to 1} (2 C k) B_k = 2　つまり　(2 C 0) B₀ + (2 C 1) B₁ = 2
B₀ = 1 なので、これは 1⋅1 + 2⋅B₁ = 2 を意味する。従って:
　　1 + 2B₁ = 2　つまり^†　B₁ = 1/2

†　B₁ は、 +1/2 と定義される場合と −1/2 と定義される場合がある（定義1からは +1/2 になる）。B₁ = −1/2 とする定義は、 B₁ = +1/2 とする定義と非互換だが、両者の違いは B₁ の符号だけで、 B₁ 以外の Bernoulli 数（つまり B₀ = 1, B₂ = 1/6, B₃ = 0, etc.）は、共通の値となる。このメモでは B₁ = +1/2 を採用する。

次に u = 2 のとき:
　　∑{k=0 to 2} (3 C k) B_k = 3　つまり　(3 C 0) B₀ + (3 C 1) B₁ + (3 C 2) B₂ = 3
B₀ = 1, B₁ = 1/2 なので（上述）、これは 1⋅1 + 3⋅1/2 + 3⋅B₂ = 3 を意味する。従って:
　　1 + 3/2 + 3B₂ = 3　つまり　3B₂ = 1/2
　　∴　B₂ = 1/6

一方 u = 3 のとき:
　　∑{k=0 to 3} (4 C k) B_k = 4　つまり　(4 C 0) B₀ + (4 C 1) B₁ + (4 C 2) B₂ + (4 C 3) B₃ = 4
B₀ = 1, B₁ = 1/2, B₂ = 1/6 なので（上述）、これは 1⋅1 + 4⋅1/2 + 6⋅1/6 + 4⋅B₃ = 4 を意味する。従って:
　　1 + 2 + 1 + 4B₃ = 4　つまり　4 + 4B₃ = 4
　　∴　B₃ = 0

最後に u = 4 のとき:
　　∑{k=0 to 4} (5 C k) B_k = 5　つまり　(5 C 0) B₀ + (5 C 1) B₁ + (5 C 2) B₂ + (5 C 3) B₃ + (5 C 4) B₄ = 5
上掲の B₀, B₁, B₂, B₃ の値から、これは 1⋅1 + 5⋅1/2 + 10⋅1/6 + 10⋅0 + 5⋅B₄ = 5 を含意。従って:
　　1 + 5/2 + 10/6 + 5B₄ = 5　つまり　31/6 + 5B₄ = 5
　　∴　5B₄ = −1/6　要するに　B₄ = −1/30

結局、イの Bernoulli 数の値は、上記「定義1」から求めることができる――少なくとも理論的には。ここで最も重要な本題は、「このように定義された B₀, B₁, B₂, ··· を使うと、なぜ m 乗和 S_m(n) の正しい公式が得られるのか」。その議論の準備を兼ねて、まず幾つかの基本事実を記しておきたい。

先ほど定義1から B₄ を確定したときに使った等式、
　　(5 C 0) B₀ + (5 C 1) B₁ + (5 C 2) B₂ + (5 C 3) B₃ + (5 C 4) B₄ = 5
　　つまり　1 + 5B₁ + 10B₂ + 10B₃ + 5B₄ = 5　‥‥①
の右辺の係数は、5乗の展開の二項係数 1, 5, 10, 10, 5, 1 から最後の「1」を除去したものだ（定義1の性質上、 B₄ に限らず、一般に B_u の計算では、 u+1 乗の二項係数が現れる）。便宜上、二項展開の表記を流用して、次のように書くことも可能。
　　(1 + B)⁵ − B⁵ = 1 + 5B¹ + 10B² + 10B³ + 5B⁴ = 5　‥‥②

①と②は全く同じ意味。ただし②の B¹, B², B³ などは1乗・2乗・3乗ではなく、単に B₁, B₂, B₃ の便宜上の記法。同様の便宜上の記法を使うと、定義1の代わりに、次の式から B_u を求めることができる:
　　(1 + B)^u+1 − B^u+1 = (B + 1)^u+1 − B^u+1 = u + 1
あるいは、同じことだが、次の式から B_u−1 を求めることができる:
　　(B + 1)^u − B^u = u

いずれにしても、この方法では、例えば B₁₀ を求めるために B₀, B₁, ···, B₉ の値が全部必要になる。一般に、定義1では u 番の Bernoulli 数が、 0 番から u−1 番の Bernoulli 数を使って間接表現される。実用上の観点からは、 B₁₀ なら B₁₀ を直接、独立して（B₉ 以下と無関係に）求められた方が便利なのだが…。次の事実を利用すると、多少見通しが良くなる。

Bernoulli 数の基本事実
　 (i)　B₃ 以降の「奇数」番の Bernoulli 数は、どれも 0。 B₃ = B₅ = B₇ = ··· = 0 は、真面目に定義から計算するまでもない。
　(ii)　B₄ 以降の「4 の倍数」番の Bernoulli 数は負の分数（例: B₄ = −1/30）。それ以外の「偶数」番の Bernoulli は正の分数（例: B₂ = 1/6）。

実は、定義1の代わりに、次の定義2を使って Bernoulli 数を定めても、全く同じ結果になる。

定義2（定義1と互換性あり）　B₀ = 1 とする。 1 以上の任意の整数 u について、 u 番の Bernoulli 数 B_u は、次の式によって間接的に定義される。
　　∑{k=0 to u} (−1)^k((u + 1) C k) B_k = 0

定義1と比べると、総和記号の内側に (−1)^k が追加され、ややこしくなったように見える。半面、右辺は = 0 で、定義1の = u + 1 よりシンプル。 k が偶数のとき因子 (−1)^k は 1 に等しいので、値が 1 倍されるだけで、この因子は無いのと同じ。一方、 k が奇数のときには (−1)^k = −1 は符号を反転させる働きを持つが、 k が 3 以上の奇数のとき B_k = 0 なので、 −1 倍されようがされまいが、どのみち結果は 0 で、やはりこの因子の影響はない。

唯一 k = 1 の場合にだけ、 ∑ 内は次のようになり、 (−1)^k は結果（総和記号による和）に影響を及ぼす:
　　k = 1　⇒　(−1)^k((u + 1) C k) B_k = (−1)¹((u + 1) C 1) B₁
　　 = −(u + 1)⋅1/2 = −(u + 1)/2

(−1)^k がない定義1では、 k = 1 のときの ∑ 内は、上記と同様の計算（ただし符号がマイナスにならない）から (u + 1)/2 になる。よって定義1の右辺と比べると、定義2の右辺は、
　　(u + 1)/2 − −(u + 1)/2 = u + 1
だけ小さい。それを反映して、定義1の左辺 u + 1 と比べ、定義2の左辺 0 も、 u + 1 だけ小さい。

要するに、定義2の式は定義1の式の両辺から u + 1 を引いたもので、どちらの定義も、実質、全く同じ式に基づく（定義の結果も、完全に同じ）。ところで、定義2の式は u = 0 の場合には有効ではない。無理やり u = 0 を入れると、定義2の式は、
　　∑{k=0 to 0} (−1)^k((0 + 1) C k) B_k = (−1)⁰(1 C 0) B₀ = 1⋅1⋅B₀ = 0
となり、そのことから B₀ = 0 となってしまうが、それでは都合が悪い。定義1で明記したように B₀ = 1 と約束しておくと、都合がいい（そうすることで、ベルヌーイの公式は、総和記号内の一つの項に要約される）。よって、一つの式で u = 0 の場合も同時に扱いたければ、次のように表現する必要がある。

定義3（定義1・定義2と互換性あり）　0 以上の任意の整数 u について、次の式によって間接的に B_u が定まる。
　　∑{k=0 to u} (−1)^k((u + 1) C k) B_k = 0 or 1
　ただし、右辺の値 0 or 1 は、 u = 0 の場合にのみ 1 になり、 u ≥ 1 なら 0 になる。

これによって u = 0 の場合には、
　　∑{k=0 to 0} (−1)^k((0 + 1) C k) B_k = (−1)⁰(1 C 0) B₀ = 1⋅1⋅B₀ = 1
　　∴　B₀ = 1
となり、全て丸く収まる。

〔注〕　定義3の「0 or 1」の「or 1」は、表面的には、単に u = 0 というエッジケース（定義域の境界上で生じる例外）を処理するための「テクニカルな規約」だ。こんな技巧的な定義より、定義2のように B₀ = 1 と直接約束した方が、シンプルで分かりやすいかもしれない。しかしながら、「定義3の形の和は、ほとんど常に = 0 になり、 u = 0 の場合に限って = 1 になる」という性質が、以下の議論の要となる（Kronecker の δ と似ている）。

任意の正の整数 m について、 Bernoulli の公式――すなわち S_m(n) = 1^m + 2^m + ··· + n^m が、
　　[1/(m+1)]∑{k=0 to m} (m+1 C k) B_k n^m+1−k　　
に等しいこと――を証明したい（ちなみに、直接計算によると、この公式は m = 0 の場合にも成り立つ）。

手始めに、具体例として m = 4 の場合。上記公式の具体的な形は、こうなる:
　　S₄(n) = (1/5)∑{k=0 to 4} (5 C k) B_k n^5−k　　オ
簡潔化のため ∑{k=0 to 4} (5 C k) B_k y^5−k の形の総和を単に F(y) と記すと、オは下記の意味を持つ。
　　S₄(n) = 1⁴ + 2⁴ + ··· + (n−1)⁴ + n⁴ = (1/5)F(n)　　キ

一方、 1⁴ から n⁴ までの n 個の4乗数の和を、
　　「1⁴ から (n−1)⁴ までの n−1 個の4乗数の和」　プラス　n⁴
と考えて、キと同様の略記法を使うと:
　　S₄(n) = [1⁴ + 2⁴ + ··· + (n−1)⁴] + n⁴　つまり
　　S₄(n) = S₄(n−1) + n⁴ = (1/5)F(n−1) + n⁴　　ク

キの右辺とクの右辺は、値が等しいはず（どちらも = S₄(n) なので）。従って:
　　(1/5)F(n) = (1/5)F(n−1) + n⁴　つまり　(1/5)F(n) − (1/5)F(n−1) = n⁴
両辺を 5 倍して:
　　F(n) − F(n−1) = 5n⁴　　ケ

ケを証明できれば、「Bernoulli の公式によって4乗和 S₄(n) を正しく計算できること」が、示される。というのも、 Bernoulli の公式によれば、
　　S₄(y) = (1/5)∑{k=0 to 4} (5 C k) B_k y^5−k
　　略して　S₄(y) = (1/5)F(y)
だ（オ参照）。ケは F(n) が F(n−1) より 5n⁴ 大きいことを含意するが、それは
　　「Bernoulli の公式によって計算すると、 S₄(n) は S₄(n−1) より n⁴ 大きい」
という意味（なぜなら S₄(y) は F(y) の5分の1）。
　　S₄(n−1) = 1⁴ + 2⁴ + ··· + (n−1)⁴
と比べて、
　　S₄(n−1) = 1⁴ + 2⁴ + ··· + (n−1)⁴ + n⁴
がちょうど n⁴ だけ大きいってことは、理屈としては当然そうなるはずだが、もしケが成り立つなら、「Bernoulli の公式では、確かにそうなってる！」ということが分かる。――もっとも、それだけでは、まだ公式が本当に正しいとは言い切れない。もしも土台となる S₄(n−1) が正しい値とずれてたら、いくら S₄(n) がそれより n⁴ 大きいとしても、それも正しい値とずれている。

ところが S₄(1) = 1⁴ = 1 なので、 n = 1 の場合、オはこうなる:
　　1 = (1/5)[1⋅B₀⋅1⁵ + 5⋅B₁⋅1⁴ + 10⋅B₂⋅1³ + 10⋅B₃⋅1² + 5⋅B₄⋅1¹]
　　両辺を 5 倍して　5 = B₀ + 5B₁ + 10B₂ + 10B₃ + 5B₄
この最後の等式は B₄ の定義そのもの（定義1参照）。つまり n = 1 のときにオが正しいことは、 Bernoulli 数の定義から保証されている！　では、もし Bernoulli の公式では S₄(n) が S₄(n−1) より n⁴ 大きいとすれば、どうなるか？
　　S₄(1) = 1⁴ = 1
が正しいからには、 n = 2 とすると、
　　S₄(2) = S₄(1) + 2⁴ = 1 + 16 = 17
も正しい値になり、さらにそのことから、
　　S₄(3) = S₄(2) + 3⁴ = 17 + 81 = 98
もまた、正しい値になる。以下同様。要するに、帰納法によって、任意の n に対して公式の正しさが証明される――もしケが証明されれば。

さて、ケを証明するには、
　　F の定義　F(y) = ∑{k=0 to 4} (5 C k) B_k y^5−k
に基づき、ケの左辺 F(n) − F(n−1) を計算して、ケの左辺がケの右辺 5n⁴ に等しいことを示せばいい。

結構複雑そうだが、できるだろうか？

まぁ、とりあえず、ケの左辺の意味をそのまんま書いてみると:
　　F(n) − F(n−1) = ∑{k=0 to 4} (5 C k) B_k n^5−k − ∑{k=0 to 4} (5 C k) B_k (n−1)^5−k
二つの総和記号の中身について、 k が同じ値（例: k = 0 なら 0）のとき、 n^5−k ないし (n−1)^5−k の前につく (5 C k) B_k は一定の等しい値なので、それでくくると、二つの総和記号を一つの総和記号にまとめることができる。
　　F(n) − F(n−1) = ∑{k=0 to 4} (5 C k) B_k [n^5−k − (n−1)^5−k]　　コ

(x ± y)^N − x^N や x^N − (x ± y)^N のような形は、展開して整理すると少し簡単になる。コには、この形が含まれているので、
　　二項定理　(x + y)^N = ∑{ℓ=0 to N}(N C ℓ) x^ℓ y^N−ℓ
を使い (n−1)^5−k を展開してみる。この場合 大文字のN = 5−k, x = 小文字のn, y = −1 なんで、
　　(n − 1)^5−k = ∑{ℓ=0 to 5−k}(5−k C ℓ)n^ℓ(−1)^5−k−ℓ　　サ
となるが、サの ∑ の末尾の項（ℓ = 5−k のとき）、つまり 1⋅n^5−k(−1)⁰ = n^5−k は、コの [ ] 内で引き算されるとき、そこにもともとある n^5−k と打ち消し合う。どうせ打ち消し合うので、最初から消しておこう: [ ] 内の引き算については、もともとある n^5−k を消滅させて 0 に置き換え、代わりにサについては、 ℓ = 5−k の一つ手前の ℓ = 5−k−1 = 4−k までの総和を使えばいい。すなわち:
　　コ = ∑{k=0 to 4} (5 C k) B_k [0 − ∑{ℓ=0 to 4−k}(5−k C ℓ)n^ℓ(−1)^5−k−ℓ]

[ ] 内の ∑ の各項は（0 から引き算されるので）符号が反転する。符号を反転させるには、右端の (−1) の指数が偶数なら奇数に変え、奇数なら偶数に変える必要がある。整数の偶奇を入れ替えるには、値を 1 増やすか減らせばいい―― 5−k−ℓ を 1 ずらして 4−k−ℓ にすればいいだろう。
　　コ = ∑{k=0 to 4} (5 C k) B_k [∑{ℓ=0 to 4−k}(5−k C ℓ)n^ℓ(−1)^4−k−ℓ]　　シ

k = 0 のとき、シの [ ] 内は ℓ = 0, 1, 2, 3, 4 に対する 5 項の和だ（k = 0 なら 4−k = 4 なので）。同様に k = 1 のとき [ ] 内は 4 項の和。 k = 2, 3, 4 のとき、 [ ] 内は、それぞれ 3, 2, 1 項の和。要するに、シの二重の総和をベタに書くと、次のような構造になってる:
　　　X₀(Y₀₀ + Y₀₁ + Y₀₂ + Y₀₃ + Y₀₄)
　　 + X₁(Y₁₀ + Y₁₁ + Y₁₂ + Y₁₃)
　　 + X₂(Y₂₀ + Y₂₁ + Y₂₂)
　　 + X₃(Y₃₀ + Y₃₁)
　　 + X₄(Y₄₀)
　　 = X₀Y₀₀ + X₀Y₀₁ + ···  + X₄Y₄₀

〔注〕　ここで X_k は (5 C k) B_k の略、 Y_k,ℓ は (5−k C ℓ)n^ℓ(−1)^4−k−ℓ の略。問題は「項をどういう順序で足し合わせるか」。

足し算の順序は自由なので、上記 X_kY_k,ℓ の形の15項（k は 0 から 4 の範囲を動き、 ℓ は 0 から 4−k の範囲を動く）を、どういう順序で足しても構わない。見方を変えると、
　　k+ℓ が 4 以下であるような、負でない整数 k, ℓ の組み合わせ
が過不足なく全種類あれば、足し算の順序はどうでもいい。特に、 X_k⋅Y_k,ℓ の代わりに Y_k,ℓ⋅X_k を考えて、「ℓ が 0 から 4 の範囲を動き、 k が 0 から 4−ℓ の範囲を動く」としても、結果は同じ和になる。実際、上記15項の和を「縦に」読んで「横に」並べると:
　　 = Y₀₀X₀ + Y₁₀X₁ + Y₂₀X₂ + Y₃₀X₃ + Y₄₀X₄
　　 + Y₀₁X₀ + Y₁₁X₁ + Y₂₁X₂ + Y₃₁X₃
　　 + Y₀₂X₀ + Y₁₂X₁ + Y₂₂X₂
　　 + Y₀₃X₀ + Y₁₃X₁
　　 + Y₀₄X₀

〔補足〕　Y_k,ℓ の k と X_k の k は一致するので、 Y_k,ℓ の k, ℓ を決めれば、自動的に X_k も決まる。負でない整数 k, ℓ の選択法として、「まず k を変化させ、次に k+ℓ ≤ 4 の範囲で ℓ を変化させる」「まず ℓ を変化させ、次に k+ℓ ≤ 4 の範囲で k を変化させる」の、どちらでも、トータルでは同じこと。従って、便宜上 G(k, ℓ) = Y_k,ℓ⋅X_k と表記するなら:
　　∑{k=0 to 4} ∑{ℓ=0 to 4−k} G(k, ℓ) = ∑{ℓ=0 to 4} ∑{k=0 to 4−ℓ} G(k, ℓ)

後の処理に都合がいいように、シの足し算・掛け算の順序を次のように変更しておく。
　　シ = ∑{ℓ=0 to 4} ∑{k=0 to 4−ℓ} (−1)^4−k−ℓ⋅n^ℓ⋅(5 C k)⋅(5−k C ℓ)B_k　　ス

「5人から k 人を選び、残りの 5−k 人から ℓ 人を選ぶ」「5人から ℓ 人を選び、残りの 5−ℓ 人から k 人を選ぶ」は、どちらも選択肢が同数なので^†:
　　 = ∑{ℓ=0 to 4} ∑{k=0 to 4−ℓ} (−1)^4−k−ℓ⋅n^ℓ⋅(5 C ℓ)⋅(5−ℓ C k)B_k
　　 = ∑{ℓ=0 to 4} ∑{k=0 to 4−ℓ} (−1)^4−k−ℓ⋅n^ℓ⋅(5 C ℓ)⋅((4−ℓ)+1 C k)B_k　　セ

†　これは (5 C k)⋅(5−k C ℓ) = (5 C ℓ)⋅(5−ℓ C k) の直観的説明。例えば社員が五人だけの小さな会社があって、仕事の都合で二人がタイに出張、一人がチリに出張するとしよう。このとき、先にタイに行く二人を選んで、残りの三人からチリに行く一人を選んでも、あるいは先にチリに行く一人を選んで残りの四人からタイに行く二人を選んでも、「五人から二人と一人を（重複なく）選ぶ」という結果に変わりなく、出張メンバーの選び方のパターン数は一定。即物的に階乗表現を使えば、次の通り:
　　(5!)/(k! (5−k)!) × ((5−k)!)/(ℓ! (5−k−ℓ)!) = (5!)/(ℓ! (5−ℓ)!) × ((5−ℓ)!)/(k! (5−ℓ−k)!)
左辺では (5−k)! が約分され、右辺では (5−ℓ)! が約分されるので、両辺は等しい。

注目すべきこととして、セの二つ目の総和記号 ∑{k=0 to 4−ℓ} と、セの右端にある ((4−ℓ)+1 C k)B_k を組み合わせたものは、 4−ℓ 番目の Bernoulli 数の定義…
　　∑{k=0 to 4−ℓ} (−1)^k((4−ℓ)+1 C k)B_k = 0 or 1　　ソ
…と、ほとんど同じ（定義3で u = 4−ℓ とした場合）。ソの右辺は、 4−ℓ = 0 の場合のみ 1 で、それ以外では 0 になる（定義3参照）。従って、ソを利用すると、セに含まれる項のほとんどは = 0 になって消滅し、消滅しないわずかな項（4−ℓ = 0 の場合）も、ソの値が = 1 なので、ずいぶん簡単になりそう。

実際にソを利用するためには、セの右の方に (−1)^k という因子（ソにあって、現在のセにはない）を追加する必要がある。さいわい、セにはもともと因子 (−1)^4−k−ℓ があるので、それを
　　(−1)^4−k−ℓ = (−1)^4−ℓ × (−1)^−k = (−1)^4−ℓ × ((−1)⁻¹)^k = (−1)^4−ℓ × (−1)^k
と二つに分け、 (−1)^k だけをセの右の方に移動すればいい（−1 の −1 乗、つまり 1/(−1) は、 −1 自身に等しい）。結果は:
　　セ = ∑{ℓ=0 to 4} ∑{k=0 to 4−ℓ} (−1)^4−ℓ⋅n^ℓ⋅(5 C ℓ)⋅(−1)^k((4−ℓ)+1 C k)B_k

この外側の ∑ について、 ℓ が 0 から 4 の一つの値に固定されている間、内側の ∑ の各項が持つ共通因子 (−1)^4−ℓ⋅n^ℓ⋅(5 C ℓ) は定数。その定数を内側の ∑ からくくり出すと:
　　セ = ∑{ℓ=0 to 4} [(−1)^4−ℓ⋅n^ℓ⋅(5 C ℓ) × ∑{k=0 to 4−ℓ} (−1)^k((4−ℓ)+1 C k)B_k]
この [ ] 内の × の後ろの部分は、 4−ℓ = 0 の場合（つまり ℓ = 4 のとき）に限って、値 1 を持ち、それ以外の場合には値が 0 になるのだから、外側の ∑ で ℓ が 0 から 4 まで変化するとき、 ℓ = 0, 1, 2, 3 のときの各項は、結局、セの和に関係しない（なぜなら、そのとき [ ] 内は × 0 の影響でゼロ）。 ℓ = 4 だけが、セの値に関係する。そこで ℓ = 4 の場合だけを考えると:
　　セ = (−1)⁴⁻⁴⋅n⁴⋅(5 C 4) × 1 = 5n⁴
結論として、ケの左辺はケの右辺に等しい。これが証明されるべき事柄だった！

以上は m = 4 の場合の Bernoulli の公式の証明だが、任意の m についても、全く同様に証明可能（m = 4 の場合の証明の「4」を m に読み替えて、「5」を m+1 に読み替えればいい）。すなわち、オに当たる式、
　　S_m(n) = 1/(m + 1)∑{k=0 to m} (m+1 C k) B_k n^m+1−k
において、総和記号の部分を F(n) と略すとして、キ・ク・ケと同様に進めて、
　　F(n) − F(n−1) = (m + 1)n^m　　タ
を確かめればいい。今、タの左辺について、
　　F(n) − F(n−1) = ∑{k=0 to m} (m+1 C k) B_k [n^m+1−k − (n−1)^m+1−k]
と書いて（コ参照）、二項定理を適用すると（サ・シ参照）:
　　 = ∑{k=0 to m} (m+1 C k) B_k [∑{ℓ=0 to m+1−k}(m+1−k C ℓ)n^ℓ(−1)^m−k−ℓ]

足し算の順序を入れ替え（ス・セ参照）、定義3を使うと（ソ参照）:
　　 = ∑{ℓ=0 to m} ∑{k=0 to m−ℓ} (−1)^m−k−ℓ⋅n^ℓ⋅(m+1 C ℓ)⋅((m−ℓ)+1 C k)B_k
　　 = ∑{ℓ=0 to m} ∑{k=0 to m−ℓ} (−1)^m−ℓ⋅n^ℓ⋅(m+1 C ℓ)⋅(−1)^k((m−ℓ)+1 C k)B_k
　　 = ∑{ℓ=0 to m} [(−1)^m−ℓ⋅n^ℓ⋅(m+1 C ℓ) × ∑{k=0 to m−ℓ} (−1)^k((m−ℓ)+1 C k)B_k]
　　 = (−1)^m−m⋅n^m⋅(m+1 C m) = (m + 1)n^m
となり、タの右辺と一致。なぜなら、上記 [ ] 内の × の後ろの部分は、 ℓ = m の場合（つまり m−ℓ = 0 の場合）には 1 に等しいが、それ以外の場合には消滅する（定義3参照）。∎

S_m(n) の m についての帰納法を使う証明が一般的でしょうが、上記では任意の一つの m を固定して、その m に対して、 n についての帰納法を使うのです。なかなか巧妙で面白いアイデアだと思われますが、いかがでしょう。

もっとも、この方法では、帰納法のベースとなるはずの S_m(0) = 1 という事実が、自明ではないようです。最初の m 乗数 1^m が = 1 であること自体は明白でも、多項式 S_m(x) が x = 1 に対し 1 を返すという根拠は何か。定義1と定義3が同等であることを認めるなら「定義より明らか」。けれど、二つの定義の同値性は B₃ = B₅ = ··· = 0 に依存しているように思われます。これらの数が 0 であることは、自明とはいえないでしょう。

この簡潔な証明に一定の価値があることは確かですが、より厳密な証明を次回に紹介します。

〔参考文献〕　Maxime Bourrigan (2014), « Sommes des puissances »
https://web.archive.org/web/20241111071141/http://cm2.ens.fr/content/sommes-des-puissances-3028
https://web.archive.org/web/20240227155716/https://cm2.ens.fr/sites/default/files/summae_potestatum.pdf
注意: この参考文献には、変数名の誤字が多い。

---

2025-03-23　ベルヌーイの公式の証明（Knuth 版）　0⁰ = 1

#遊びの数論　#べき和　#ベルヌーイ数の分母　#ベルヌーイの公式

前回、べき和公式の一応の証明を紹介した（フランスの Bourrigan による）。比較的平明でとっつきやすい内容だが、厳密性の点では、多少の疑問も残る。参考として、 Knuth による本格派の証明を転載しておく。

このバージョンは、明晰（めいせき）で一分の隙もない。 0⁰ = 1 を当たり前のように使うとこなど、いかにも Knuth っぽく、面白くもある。 Concrete Mathematics という有名な市販の教科書の一部なのだが、現在、この部分はウェブ上で自由に読める^†。このアクセス性も良い。

半面、 Knuth なのでかなり行間が広く、難易度も高め。二項係数の扱いに慣れてる必要がある。このメモでは、くどいくらいに説明を追加してあるけど、それでも前回のバージョンよりはムズい。二項係数の操作をゼロから記すと大変なので、便宜上、「野球部のスタメンと控えの選手」みたいな例え話で、お茶を濁しておいた（笑）。

† https://www-cs-faculty.stanford.edu/~knuth/gkp34.pdf

具体例などについては前回記したので、今回は証明のみ。

記号 S_e(n) によって、 1^e + 2^e + ··· + n^e = ∑{k=1 to n} k^e を表すことにする（n: 正の整数）。このとき:
　　S_m+1(n) = 1^m+1 + 2^m+1 + ··· + n^m+1
　　S_m+1(n+1) = 1^m+1 + 2^m+1 + ··· + n^m+1 + (n+1)^m+1

後者 S_m+1(n+1) は S_m+1(n) + (n+1)^m+1 に等しいが、
　　∑{k=1 to n+1} k^m+1　あるいは　∑{k=0 to n} (k+1)^m+1
とも表現可能。従って:
　　S_m+1(n) + (n+1)^m+1 = ∑{k=0 to n} (k+1)^m+1
二項定理で (k+1)^m+1 を展開すると:
　　 = ∑{k=0 to n} ∑{j=0 to m+1} (m+1 C j) k^j⋅1^m+1−j = ∑{k=0 to n} ∑{j=0 to m+1} (m+1 C j) k^j
　　 = ∑{j=0 to m+1} (m+1 C j) ∑{k=0 to n} k^j = ∑{j=0 to m+1} (m+1 C j) [∑{k=0 to 0} k^j + ∑{k=1 to n} k^j]
　　 = ∑{j=0 to m+1} (m+1 C j) [0^j + S_j(n)]
　　 = ∑{j=0 to m+1} (m+1 C j) 0^j + ∑{j=0 to m+1} (m+1 C j) S_j(n)
　　 = ∑{j=0 to m+1} (m+1 C j) 0^j + [∑{j=0 to m} (m+1 C j) S_j(n) + ∑{j=m+1 to m+1} (m+1 C j) S_j(n)]　　‥‥①

①右辺について。一つ目の ∑ の各項は、 j ≥ 1 に対しては 0^j = 0 なのでゼロだが、 j = 0 に対しては、
　　(m+1 C 0) 0⁰ = 1⋅0⁰ = 1⋅1 = 1
なので^†、全体として 1 に等しい。三つ目の ∑ は、
　　(m+1 C m+1) S_m+1(n) = 1⋅S_m+1(n) = S_m+1(n)
に等しい。以上をまとめると:
　　S_m+1(n) + (n+1)^m+1 = ① = 1 + ∑{j=0 to m} (m+1 C j) S_j(n) + S_m+1(n)
両辺から S_m+1(n) を引いて、右辺の 1 を移項すると:
　　(n + 1)^m+1 − 1 = ∑{j=0 to m} (m+1 C j) S_j(n)　　‥‥②

†　少なくとも二項定理に関する限り、 0⁰ = 1 と考える必要がある。実際、
　　3² = (3 + 0)² = 1⋅3²⋅0⁰ + 2⋅3¹⋅0¹ + 1⋅3⁰⋅0² = 9⋅0⁰ + 0 + 0
が = 9 になるためには、 0⁰ = 1 でなければならない。

われわれは、 0 以上 m 未満の任意の整数 j に関して、
　　ベルヌーイの公式　σ_j(n) = [1/(j + 1)]∑{u=0 to j} (j+1 C u) B_u n^j+1−u　　‥‥③
が正しいこと――つまり σ_j(n) = S_j(n) であること――を仮定し、その仮定の下で、 j = m に対しても公式が正しいこと――つまり σ_m(n) = S_m(n) であること――を示したい。ここでベルヌーイ数 B_u は、
　　∑{ℓ=0 to u} ((u + 1) C ℓ) B_ℓ = u + 1　　‥‥④
によって、 u = 0, 1, 2, ··· に対して、再帰的に定義されるものとする（前回の定義1参照。 B₁ = +1/2）。

仮定により j = 0, 1, ···, m−1 に対しては S_j(n) = σ_j(n) だが、 j = m について同様の等式が成り立つことは、まだ証明されていない。そこで S_m(n) と σ_m(n) のずれを Δ = S_m(n) − σ_m(n) で表し、
　　S_m(n) = σ_m(n) + Δ
としよう。ずれ Δ が = 0 であることが示されれば、証明の目的が成就される。仮定により、②の右辺は、
　　∑{j=0 to m−1} (m+1 C j) S_j(n) + ∑{j=m to m} (m+1 C j) S_j(n)
　　 = [∑{j=0 to m−1} (m+1 C j) σ_j(n)] + (m+1 C m) S_m(n)
　　 = [∑{j=0 to m−1} (m+1 C j) σ_j(n)] + (m+1 C m)[σ_m(n) + Δ]
　　 = [∑{j=0 to m−1} (m+1 C j) σ_j(n)] + (m+1 C m) σ_m(n) + (m+1 C m)Δ
　　 = [∑{j=0 to m} (m+1 C j) σ_j(n)] + (m+1 C m)Δ
に等しい。要するに②は、こうなる:
　　(n + 1)^m+1 − 1 = [∑{j=0 to m} (m+1 C j) σ_j(n)] + (m+1)Δ
　　∴　(n + 1)^m+1 − 1 − (m+1)Δ = ∑{j=0 to m} (m+1 C j) σ_j(n)　　‥‥⑤

⑤の右辺について。 σ_j(n) に③を代入し、文字 u の代わりに k を使うと:
　　⑤ = ∑{j=0 to m} (m+1 C j) [1/(j + 1)]∑{k=0 to j} (j+1 C k) B_k n^j+1−k
∑ X_j(Y₀ + Y₁ + ···  + Y_j) の形を展開して生じる ∑∑ X_jY_k の各項は、どういう順序で足してもよく（前回のシ以下参照）、各項の各因子はどういう順序で掛けてもいい。例えば、次のようにしてもいい:
　　 = ∑{j=0 to m} ∑{k=0 to j} [1/(j + 1)] (m+1 C j) (j+1 C k) B_k n^j+1−k

外側の ∑ が設定する j の値（内側の ∑ から見ると定数）について、内側の ∑ の k が 0, 1, ··· , j の範囲を動くとき、 j−k は同じ範囲を（逆順で）過不足なく動く。だから上記 ∑∑ 内の k を j−k に置き換えても、トータルでは同じ和になる（内側の足し算の順序が逆になるだけ。 k を含まない因子には影響なし）:
　　 = ∑{j=0 to m} ∑{k=0 to j} [1/(j + 1)] (m+1 C j) (j+1 C j−k) B_j−k n^{j+1−(j−k)}　　‥‥⑥

さて (j+1 C j−k) は (j+1 C (j+1)−(j−k)) = (j+1 C k+1) に等しく、それは (j + 1)/(k + 1)(j C k) に等しいので、それを⑥に代入すると j + 1 は約分され、こうなる:
　　⑥ = ∑{j=0 to m} ∑{k=0 to j} [1/(k + 1)] (m+1 C j) (j C k) B_j−k n^k+1

「m+1 人の野球部員から j 人の試合出場者を選び、その j 人の中から k 人のスタメンを選ぶ」ことは、「m+1 人の部員から k 人のスタメンを選び、残りの m+1−k 人の中から、（スタメンではないがベンチ入りする）控えの選手 j−k 人を選ぶ」のと同じことだから、 (m+1 C j) (j C k) は (m+1 C k) (m+1−k C j−k) に等しい。この関係を上記の式に代入すると:
　　⑥ = ∑{j=0 to m} ∑{k=0 to j} [1/(k + 1)] (m+1 C k) (m+1−k C j−k) B_j−k n^k+1

総和記号の順序を入れ替えよう。 k は最大で m に等しくなるが（j = m のとき）、 k の上限は j であり、 k は j を超えられない。言い換えると j は常に k 以上。⑥では「j が 0 から m までを動き、その j の値に応じて k は 0 から j までを動く」となっているが、「k が 0 から m までを動き、その k の値に応じて j は k から m までを動く」と言い換えても、結果は同じ:
　　 = ∑{k=0 to m} ∑{j=k to m} [1/(k + 1)] (m+1 C k) (m−k+1 C j−k) B_j−k n^k+1
j の値に依存しない因子（j を含まず、従って j が変わっても値が変わらないもの）を内側の ∑ からくくり出すと:
　　 = ∑{k=0 to m} [[n^k+1/(k + 1)] (m+1 C k) ∑{j=k to m} (m−k+1 C j−k) B_j−k]

内側の ∑ において j−k を ℓ とすると、 j = k のとき ℓ = 0 で、 j = m のとき ℓ = m−k だ。つまり、 j が k から m まで動く代わりに、 ℓ が 0 から m−k まで動いても、同じこと。二項係数の上側インデックス、つまり j−k とペアになっている m−k+1 は、この変数置換の影響を受けない（なぜなら、内側の ∑ 内では k の値は一定）:
　　 = ∑{k=0 to m} [[n^k+1/(k + 1)] (m+1 C k) ∑{ℓ=0 to m−k} (m−k+1 C ℓ) B_ℓ]
この内側の ∑ は、ベルヌーイ数の定義④において u = m−k としたものだから、 u + 1 = m − k + 1 に等しい:
　　 = ∑{k=0 to m} [[n^k+1/(k + 1)] (m+1 C k)(m − k + 1)]
二項係数 (m+1 C k) は (m C k) の (m + 1)/(m − k + 1) 倍なので（説明）、上の式は次のように整理される:
　　 = ∑{k=0 to m} [[n^k+1/(k + 1)] (m C k)⋅(m + 1)/(m − k + 1)⋅(m − k + 1)]
　　 = ∑{k=0 to m} [[m + 1/(k + 1)] (m C k)⋅n^k+1] = ∑{k=0 to m} (m+1 C k+1) n^k+1

⑤の右辺を変形してきたらこうなったのだから、上記の最後の式は、⑤の左辺と等しい。すなわち:
　　(n + 1)^m+1 − 1 − (m + 1)Δ = ∑{k=0 to m} (m+1 C k+1) n^k+1　　‥‥⑦
ところが（二項定理を使うと）、
　　(n + 1)^m+1 = ∑{j=0 to m+1} (m+1 C j) n^j⋅1^m+1−j = ∑{j=0 to m+1} (m+1 C j) n^j　　‥‥⑧
だ。そして⑧右辺の ∑ において、 j = 0 のときの項 (m+1 C 0) n⁰ = 1⋅n⁰ は 1 に等しい（n: 正の整数）。従って、もし j の初期値を j = 0 でなく j = 1 にして、 j = 0 のときの項を ∑ の足し算から除外するなら、全体の和は、ちょうど 1 小さくなる。つまり次の等式（⑧の両辺から 1 を引いたものに当たる）が成り立つ:
　　(n + 1)^m+1 − 1 = ∑{j=1 to m+1} (m+1 C j) n^j
ここで k = j−1 つまり j = k+1 と置くと、 j が 1 から m+1 まで動くとき、 k は 0 から m まで動く。要するに:
　　(n + 1)^m+1 − 1 = ∑{k=0 to m} (m+1 C k+1) n^k+1　　‥‥⑨

⑨の右辺は⑦の右辺と同じなので、⑦の右辺を⑨の左辺で置き換えてもいい。結果は:
　　(n + 1)^m+1 − 1 − (m + 1)Δ = (n + 1)^m+1 − 1
　　∴　(m + 1)Δ = 0

この最後の式から、 m + 1 と Δ の少なくとも一方は = 0。だが仮定により m は 0 以上なので、 m + 1 が 0 に等しい可能性はない。 Δ = 0 と結論される。すなわち、 j = m の場合のベルヌーイの公式 σ_m(n) と、本当の m 乗和の値 S_m(n) を比較すると、両者の差はゼロ―― σ_m(n) は、正しい値とぴったり一致。

結局、「指数 j が 0 以上 m 未満ならベルヌーイの公式は正しい」と仮定した場合、実は j = m のときにもベルヌーイの公式は正しい。 m = 0 のときベルヌーイの公式が正しいことは自明なので、帰納法により、 0 以上のどんな指数についても、ベルヌーイの公式は正しい。∎

---

2025-03-31　二項係数・超入門　三つの基本と簡単な応用例

#遊びの数論　#ベルヌーイの公式

ベルヌーイの公式関連で、やたらと出てくる (n C k) みたいな記号。とりあえず必要なことだけ、ここでまとめておきたい。今回は、特に予備知識は必要なし。

• 超入門　_nC_k が分かる方は飛ばしてネ
• 三つの基本、その1　「階乗表現」
• 三つの基本、その2　「二項定理」
• 三つの基本、その3　「対称性」
• 簡単な応用例　「予選・本選の法則」
• 軽くひねった応用例　「タイ・チリの法則」

超入門　_nC_k が分かる方は飛ばしてネ

問題　3種類の軽食（パパイア、ピザ、プリン）を一人の客に出すとして、どーゆー順番で出すのがいいか？

どういう順序で出すにせよ、まずは三つのうちどれか一つを出すのだから、最初に出すやつの選択肢は三つある。で、どれを最初に出したとしても、次に残りの二つのどっちかを出すのだから、二つの選択肢がある。最後に出すやつは、選択肢が一つしかない（三つのうち、まだ出してないのは一つだけなので）。
　　パパイアを最初に出す場合　　　パ→ピ→プ　か　パ→プ→ピ
　　ピザを最初に出す場合　　　　　ピ→パ→プ　か　ピ→プ→パ
　　プリンを最初に出す場合　　　　プ→パ→ビ　か　プ→ピ→パ

合計6通りの可能性がある――この「6通り」という数が 3 × 2 × 1 ってことは明らかだろう。なにしろ選択肢が最初に三つあって、次に二つあって、最後に一つなんだから、トータルではそれらの積になる、と。

でもって、今度はあなたが客の立場だとして、何を食べたいか自分で選べるとしよう！　さらにメニューに「ペパーミントティー」と「ポテトサラダ」が加わって、アイテムが五つあるとする。条件は、ちょうど三つのアイテムを一つずつ順々に注文すること、同じアイテムは一度しか選べないこと。この場合、食事の選択肢は、注文の順序も考慮するなら、 5 × 4 × 3 = 60 だ（最初にパピプペポの五つのどれでも選べて、次にまだ選んでない四つのどれかを選べて、最後にまだ選んでない三つのどれかを選べるので）。「順序も考慮」というのは、例えば、
　　ポテトサラダ→ピザ→プリン　と　ポテトサラダ→プリン→ピザ　と　ピザ→ポテトサラダ→プリン　など
は、（食べる内容は同じだけど）頼む順番が違うので「別の選択」と考える、ってこと。まぁ、そういう考え方もあるよね。

だけど別の考え方もあるぞ。順序は考慮しないで、
　　「ポテトサラダ→ピザ→プリン」も「ピザ→ポテトサラダ→プリン」も要するに選ぶ三つは同じじゃん！
という見方だ。そのように「選ぶ順序の違いを区別しない場合、もし五つのアイテムから三つを選ぶとしたら、選択肢は何パターンあるのか？」というのが、
　　二項係数　(5 C 3)
であり、
　　= (5 × 4 × 3)/(3 × 2 × 1) = 10
と計算される。この計算の根拠は、「五つのアイテムから三つを順に選ぶのが 5 × 4 × 3 パターンある」ということ、そして、「特定の三つのアイテムを注文するとして、注文の順序のバリエーションは 3 × 2 × 1 パターンある」ということ（最初の「パパイア、ピザ、プリン」の三つだけの例を参照）。順序を考慮するなら、注文の仕方は 5 × 4 × 3 = 60。だけど、同じ三つを頼む場合でも、その三つを注文する順序のバリエーションが 3 × 2 × 1 = 6 ある。つまり「順序を区別する場合」は「順序を区別しない場合」に比べて、パターンが 6 倍になってる。逆に言えば「順序を区別しない場合」には、パターンが 1/6 になる、と。

同様に、選ぶ順序の違いは考えないとすると、例えば10個の物から4個を選ぶパターンの数は、こうなる:
　　(10 × 9 × 8 × 7)/(4 × 3 × 2 × 1)
見かけは分数（計算も分数）だが、「選択肢の数」なんで、値（分母を分子で割った結果）はもちろん整数だ。その整数を、記号 (10 C 4) で表す。同じ意味で、記号 ₁₀C₄ が使われることもある。どちらも読み方は「10 choose 4」つまり「10選ぶ4」。

ま～、だいたいそんなことで、一応「超入門」。よく分かんなくても「習うより慣れよ！」ってなわけで、このまま行っちゃうよ…？

三つの基本、その1　「階乗表現」

対外試合があるとして、20人の野球部員から9人のスタメンを選ぶとしたら、その選択肢は「20選ぶ9」つまり (20 C 9) であり、
　　A = (20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12)/(9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1)
に等しい（単に「9人を選ぶ」って話。打順や守備のポジションの設定までは考えてない）。理論的には単純だが（前述の「軽食パピプペポ」と同じ考え方）、このような「分子・分母が長々とした分数」は、書くのも読むのも、面倒で不便。そこで、便利な省略記法として、
　　9 × 8 × ··· × 1　あるいは
　　値は同じだが　1 × 2 × ··· × 9
を 9! で表す（読み方は「9の階乗」）。この感嘆符 ! は、別にびっくりしてるわけでなく、単なる数学記号。んで、一般に、記号 N! で、
　　1 × 2 × ··· × N　　（ここで N は正の整数）
を表す。これで上記 A の分母は 9! のたった2文字で済む。けど、分子はどうしましょ？
　　20! = 20 × 19 × ··· × 1
と似てるが、欲しいのは「20 から 1 までの 20 個の数の積」ではなく、「20 から 12 までの 9 個の数の積」だ。つまり 20! だと、
　　20 × 19 × ··· × 12
まではちょうどいいんだけど、その後ろに続く × 11 × 10 × ··· × 1 の部分が、余計なんだよね。で、ちょっと考えれば、解決法は簡単――余計な因子で割り算すれば、余計な因子は約分されて消滅し、欲しい因子だけが残る、と。つまり A の分子 20 × 19 × ··· × 12 は、
　　(20 × 19 × ··· × 1)/(11 × 10 × ··· × 1)　要するに　20!/11!
と表現可能。結局、
　　A = 分子 ÷ 分母 = 20!/11! ÷ 9! = 20!/(9! × 11!)
となる。より一般的に:

二項係数の階乗表現
　　(n C k) = [n(n−1)(n−2)···(n−k+1)]/k! = n!/[k! (n−k)!]

一つ目の分子 n(n−1)(n−2)···(n−k+1) は、「n から始めて、 1 ずつ小さくなる k 個の整数」を掛け合わせる、という意味。最後に +1 があることに注意。もしも、
　　n−1, n−2, ··· , n−k
だったら、それは明らかに k 個の整数だが、
　　n−0, n−1, n−2, ··· , n−k
だったら、 n−0 つまり n が加わるので k+1 個の数になってしまう。 n から降下を始めて k 個の数で止まるためには、終点は n−k でなく n−k+1 だ。具体例として、20人の野球部から9人のスタメンを選ぶ長い分数（上記）の分子で、分子の最後の因子は 20−9 = 11 ではなく 20−9+1 = 12 だった。
　　20 から 20−9=11 まで
だと 10 個の数があるが、欲しいのは 9 個の数なので、
　　20 から 20−9+1=12 まで
ということに。このような数を n^_k や、それに似た記号で表すこともある。このメモでは n^↓k という表記を使うことにする。例えば:

20 の 9 乗

20⁹ = 20 × 20 × ··· × 20

「20」を「9個」掛ける

20 の「下降 9 乗」

20^↓9 = 20 × 19 × ··· × 12

「20」から始めて「下降する9個の整数」を掛ける

n^↓k は n(n−1)(n−2)··· (n−k) ではなく n(n−1)(n−2)··· (n−k+1) だ、ということに重ねて注意しておく。

まとめ・要点　(10 C 4) のような記号は、「10個のアイテムから4個のアイテムを選ぶ場合の選択肢の数」と解釈可能。
　必要に応じて (10 C 4) を「10 choose 4」または「10選ぶ4」などと読む。このような形の一つ一つの数を二項係数という。
　具体的な数値は 10^↓4/4! という分数として計算可能。
　　(10 C 4) = (10 × 9 × 8 × 7)/(4 × 3 × 2 × 1) = 210
　階乗だけを使って 10!/[4! (10−4)!] として計算することもできる（階乗表現）。階乗表現は分子が大きくなり、具体的な計算には必ずしも向いていない。でも、理論的な扱いでは役立つことも多い。二項係数「n 選ぶ k」の n を上側インデックス、 k を下側インデックスと呼ぶ。

具体的な（小さい）二項係数の値は、いろんな場面で使われる。例えば、恒等式 (x + y)³ = x³ + 3x²y + 3xy² + y³ に現れる二つの係数「3」も、実は二項係数の例。その訳は…

三つの基本、その2　「二項定理」

その2は、微妙にムズいかも。あまり気にせず、てきとーに斜め読みの方向で。

(x + y)ⁿ の形の展開（二項展開）の例:
　　(x + y)² = 1x²y⁰ + 2x¹y¹ + 1x⁰y² = x² + 2xy + y²
　　(x + y)³ = 1x³y⁰ + 3x²y¹ + 3x¹y² + 1x⁰y³ = x³ + 3x²y + 3xy² + y³
　　(x + y)⁴ = 1x⁴y⁰ + 4x³y¹ + 6x²y² + 4x¹y³ + 1x⁰y⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

これらの展開式は、一つ一つ個別に証明することもできるけど、現れる係数 1, 2, 1 や 1, 3, 3, 1 や 1, 4, 6, 4, 1 の一つ一つは、どれも二項係数。そもそも「二項係数」という用語は、「二項の式（例えば x + y）の累乗」の展開に現れる係数、という意味。これらの数が「n選ぶk」の形になってる理由は…

例えば、
　　(x + y)⁵ = (x + y)(x + y)(x + y)(x + y)(x + y)
の右辺を展開すると、
　　(x or y) × (x or y) × (x or y) × (x or y) × (x or y)
の 2⁵ = 32 項が生じる。 32 項のどれも x or y をちょうど五つ、掛け算したもの。
　　x^△y^□
と書けば △ + □ = 5 だ。では、その 32 項のうち、例えば「x が二つで y が三つ」の積は何個あるか。その答えは、下記のアイウエオの5カ所のうち、「ちょうど3カ所で y を選ぶ（残りの2カ所では x を選ぶ）方法」がいくつあるか？と一致する。

ア	イ	ウ	エ	オ
(x or y)	(x or y)	(x or y)	(x or y)	(x or y)

「アイウエオの五つのうち、どれか三つを選んでその場所で y を使う」ということは、「パピプペポ（パパイヤ・ピザ・プリン・ペパーミント・ポテト）の五つのメニューのうち、どれか三つを好きに選ぶ」のと、同じパターンの話だ。どっちの選択肢も、
　　二項係数　(5 C 3) = (5 × 4 × 3)/(3 × 2 × 1) = 10
に等しいっ！

よって (x + y)⁵ を展開して同類項を束ねると、 y が三つある x²y³ の係数は 10 だ。他の係数についても、同様に（アイウエオの五つの場所のうち □ カ所で y を使う選択肢の数を）考えると:
　　(x + y)⁵ = (5 C 0)x⁵y⁰ + (5 C 1)x⁴y¹ + (5 C 2)x³y² + (5 C 3)x²y³ + (5 C 4)x¹y⁴ + (5 C 5)x⁰y⁵
　　 = 1⋅x⁵y⁰ + 5⋅x⁴y¹ + 10⋅x³y² + 10⋅x²y³ + 5⋅x¹y⁴ + 1⋅x⁵y⁰
　　 = x⁵ + 5x⁴y + 10x³y² + 10x²y³ + 5xy⁴ + x⁵

より一般的に、
　　(x + y)ⁿ = (n C 0)xⁿy⁰ + (n C 1)xⁿ⁻¹y¹ + (n C 2)xⁿ⁻²y² + ··· + (n C n)xⁿ⁻ⁿyⁿ
というのは、次の形の n+1 項の和だ（ただし □ = 0, 1, 2, ···, n）:
　　(n C □)x^n−□y^□

この □ の部分を何らかの一つの文字、例えば k で表すことにして…。 k = 0 から k = n まで、 k の値を変化させながら
　　(n C k)x^n−ky^k　　← □ を k と書いた
の形の項（計 n+1 項）を足し合わせることを、
　　∑{k=0 to n} (n C k)x^n−ky^k
で表す。 (x + y)ⁿ は (y + x)ⁿ と同じことなんで、そうしたければ変数名「x」と「y」を入れ替えても結果は同じ。もし x と y を入れ替えると x^n−ky^k は y^n−kx^k に――つまり x^ky^n−k に――なる。

二項定理と二項係数
　　(x + y)ⁿ = ∑{k=0 to n} (n C k)x^n−ky^k = ∑{k=0 to n} (n C k)x^ky^n−k
　　ここで　(n C k) = n^↓k/k! = n!/[k! (n−k)!]

ポイントは、「この方法を使って (x + y)⁵ の展開公式を導きましょう」とか「それを暗記しましょう」といった、個別的なことではない。そうではなくて、「何乗の展開であっても、具体的な展開結果はさておき、抽象的には同じこの形になるんだよ」ってこと。二項定理の核心は――「2乗の展開」「3乗の展開」のような個々の計算とは別次元の話として――「具体的に n の値を特定できない場合でも、一般論的に n 乗の展開を処理できる」ってこと。

ちょっと抽象的で難しい…ように思えるかもしれない。でも、抽象的ってことは、具体的な泥くさい計算は必要ないってことでもある。具体的な問題――例えば n = 12 のときの (x + y)¹² を展開すること――は、面倒くさい。他方において、「具体的には面倒だけど、二項定理で処理できるんだよ」という原理を理解することは、別に難しくない。ここで重要なのは、
　　(x + y)¹²
の係数をスラスラ書けるような「個別的」なスキルではなく、 (x + y)^○ の指数 ○ が 12 だろうが 20 だろうが m だろうが j+k+ℓ だろうが、総和記号を使ってみんなまとめて面倒見てやるぜ、という「柔軟で、度量の広～い考え方」なのだッ！

〔補足〕　とはいうものの、二項定理の抽象性は、慣れないうちは難しく感じられるかも…。「ばかばかしいけど分かりやすい（？）説明」という別のメモもあるので、上記の説明ではよく分からん！という方は参考にしてください。

三つの基本、その3　「対称性」

基本公式 (x + y)² = 1x² + 2xy + 1y² をあえて二項定理を使って書くと、
　　(x + y)² = (2 C 0)x² + (2 C 1)xy + (2 C 2)y²
となる。これが成り立つためには、 x² の係数 1 との比較から、
　　(2 C 0) = 2!/[0! (2−0)!] = (2 × 1)/(0! × 2 × 1) = 1
でなければならず、 0! = 1 と考える必要がある。さらに、同じ係数は、
　　2^↓0/0! = 2^↓0/1 = 2^↓0
でもあるので、ある数の「下降 0 乗」は、「普通の 0 乗」同様、やはり = 1 と考える必要がある。

〔補足〕　0 乗が 1 ってことは、次のように考えると、別に不思議でもない。例えば、
　　a⁵ ÷ a² = (a × a × a × a × a)/(a × a) = a × a × a = a³
ってことに異論はないだろう。同様に考えると、一般に、
　　a^m ÷ aⁿ = a^m−n
となる（指数法則の一種）。で、例えばもし m = 4, n = 4 なら、
　　a⁴ ÷ a⁴ = a⁴⁻⁴ = a⁰
となるが、これは (a × a × a × a)/(a × a × a × a) = 1 に等しいはず。足し算においては + 0 は「何も足さない」のと同じことだが（和は変わらない）、掛け算においては × 0 は「何も掛けない」のと同じではない（もともとの積が既に 0 である場合を除き、 0 倍すれば値が変わってしまう）。掛け算の世界で、「足し算の世界の 0」に相当する因子は 1 だ（1 を幾つ掛けても、積は増えも減りもしない）。つまり掛け算の世界では 1 は「無いのと同じ因子」。そう考えると「0 個の数の積は 1」というのは、そう不自然でもない。だって「何も掛けない」ってことは「積が変わらない」ってことで、それは「1倍」と同じじゃん。同様に、 2! は 2 個の整数の積、 1! は 1 個の整数の積、 0! は 0 個の整数の積なんで、 0! = 1 となる。

二項定理との関連では (2 C 0) = 1 という事実そのものに、着目しておきたい。一般に「n 個から 0 個を選ぶ選択肢の数」は 1 だ。なぜかというと…

話が変わるようだが、例えば「3人の応募者から1人の合格者を選ぶ」としたら「誰を合格させるか？」という選択肢はもちろん 3 だけど、「3人の応募者から2人の合格者を選ぶ」場合でも、選択肢は同じ 3 になる。「3人の応募者から1人の不合格者を選ぶ」のと同じことだから、どちらも「3選ぶ1」なのだ。一般に「n 個のうち k 個を選んで採用する」のは「n 個のうち n−k 個を選んで不採用にする」のと同じなので、次の重要な関係が成り立つ。

二項係数の対称性　n, k が 0 以上の整数で、 n が k 以上のとき:
　　(n C k) = (n C n−k)
　　意味　「n 個から k 個（の合格）を選ぶ」イコール「n 個から n−k 個（の不合格）を選ぶ」

この考え方を応用すると、次の通り。「3人の応募者から3人の合格者を選ぶ」のは、もちろん1通りの選び方しかない（全員を選ぶ）。「3人の応募者から3人の不合格者を選ぶ」場合も、1通りの選び方しかない（全員を不合格にすることを選ぶ）。「3人の応募者から0人の合格者を選ぶ」のは後者と同じなので、やはり1通りの選び方しかない。同様に考えると、一般にこうなる:

考えるまでもない二項係数　n が 0 以上の整数のとき:
　　(n C 0) = 1　　(n C n) = 1

これらの係数は 1 なので、二項係数の処理では事実上、この形の係数は存在しないかのように無視される（1 倍というのは何もしないのと同じだから）。値がどちらも = 1 なのは、対称性の例でもある。ところで (0 C 0) も = 1 だ。実際、定義から:
　　(0 C 0) = (0!)/[0! (0−0)!] = 1/(1⋅1) = 1

ついでにもう一つ:

当たり前の主張　n が 1 以上の整数のとき:
　　(n C 1) = n　　(n C n−1) = n

前者は「n 個から 1 個だけ選ぶ選択肢は n 通り」という当たり前のこと。後者は「n 個から n−1 個だけ選ぶ選択肢も n 通り」。対称性により、前者と前者の選択肢の数は同じ。

簡単な応用例　「予選・本選の法則」

予選・本選　n 個の応募作品から y 個の予選通過作品を選び、その y 個の作品から、最終選考で k 個の入選作を選ぶ。
　　予選の選択肢の数「n選ぶy」　(n C y)
　　本選の選択肢の数「y選ぶk」　(y C k)
　　トータルでの選考結果の可能パターン数　(n C y)(y C k)

この選考結果は、次の選び方でも同じこと。結局、 n 個の応募作品のうち k 個が入選作となる（その k 個はもちろん予選通過の y 個にも含まれている）。「応募したけど入選しなかった残りの n−k 作品」の中には、「最終選考では落ちたが予選は通過したやつ」が y−k 個ある。予選通過作品は合計 y 個で、そのうち k 個は入選作なので、予選だけ通って本選で落ちた作品の数は y−k というわけ。
　　応募作品中の入選作品の選択肢「n選ぶk」　(n C k)
　　非入選作品中の予選通過作品の選択肢「n−k 選ぶ y−k」　(n−k C y−k)
　　トータルでの選考結果の可能パターン数　(n C k)(n−k C y−k)

〔補足〕　最終選考で入選となった k 個の作品は、もちろん予選を通過してるので、入選作 k 個に関しては「予選の結果」は必ず「通過」。そこに選択の余地はない。一方、入選以外の n−k 作品のそれぞれについては、「予選通過・予選落ち」の選択が起きる。そして、非入選 n−k 作品のうち、ちょうど y−k 個だけが予選を通過する。なぜなら、予選通過作品は合計 y 個で、そのうち k 個は入選作品なので、残りの「予選通過枠」は y−k 個。

どちらの選び方でも、「予選・本選を含めた選択パターンの総数」は同じなので、次の関係が成り立つ。

「予選・本選の法則」　(n C y)(y C k) = (n C k)(n−k C y−k)　　‥‥❶

❶右辺の第一因子 (n C k) は、いわば左辺 (n C y)(y C k) の y が「約分」された形だ。もちろん二項係数は「ただの分数」ではないので、分数みたいに単純に「約分」はできず、結論から言うと、第二因子 (n−k C y−k) が追加される。この第二因子の上下のインデックスは、左辺の「上が残る二項係数」（上側インデックス n が残り、下側インデックス m が約分される）の上下のインデックスのそれぞれから、「下が残る二項係数」の下側インデックス k を引き算したものに等しい。

❶の右辺のように書き換えても、形の上で、左辺が簡単になるわけではない（むしろ二項係数がややこしくなってる）。でも、左辺では両方の二項係数が y を含んでいるのに対し、右辺では一つの二項係数だけが y を含んでいる。その結果として、もし y が変数なら、「変数が一カ所だけ」の右辺の方が扱いやすい可能性が高い。

〔実践例〕　Knuth 版の途中計算の「m+1 人の野球部員のうち j 人が試合に出て、そのうちスタメンは k 人」という例え話のやつ:
　　(m+1 C j)(j C k) = (m+1 C k)(m+1−k C j−k)
右辺第一因子では、左辺の j が「約分」され、第二因子では m+1 と j から、それぞれ k が引き算されている。すぐ後で j を変数とする ∑ を扱うこともあって、このように j を一カ所にまとめるのが好手となる。

法則の内容自体は、「予選・本選」という直観的説明だけでも十分に納得がいくだろうけど、二項係数の操作に慣れるための肩慣らしも兼ねて、階乗表現（三つの基本、その1）を使って、法則を直接証明してみたい。
　　❶左辺 = (n C y)(y C k) = (n!)/(y! (n−y)!) × (y!)/(k! (y−k)!)　　‥‥❷
❷の分数の掛け算では、確かに文字通り y! が約分される。しかし、❷の左端の二項係数の積を「約分」して、
　　(n C k) = (n!)/(k! (n−k)!)　　‥‥❸
を作るとすると、その分母の因子 (n−k)! は、❷の分数の積に含まれていない。それを打開する自然なアイデアは、❷の分数を（約分して y! を消してから） (n−k)!/(n−k)! 倍（つまり 1 倍）して、分子・分母に (n−k)! を追加してやることだろう:
　　❷ = (n!)/((n−y)!) × (1)/(k! (y−k)!) × (n−k)!/(n−k)!
❸の形を作るように、上記の分子・分母を並び替え、二つの分数の積に整理:
　　❷ = (n!)/[k! (n−k)!] × ((n−k)!)/[(y−k)! (n−y)!]
(n−k) − (y−k) = n − k − y + k = n−y という関係に留意すると:
　　❷ = (n!)/[k! (n−k)!] × ((n−k)!)/[(y−k)! ((n−k) − (y−k))!]
この最後の積のうち、第一の分数は (n C k) の階乗表現だし（❸参照）、第二の分数は (n−k C y−k) の階乗表現なんで、結局この積は❶の右辺に等しい。「予選・本選の法則」が証明された！

「予選・本選の法則」は一見、無味乾燥な公式のようだが、実はこれが「三項定理」という楽しい冒険コースとつながっている。けど、今回は入門編なんで、この先の探検はまたの機会に…

軽くひねった応用例　「タイ・チリの法則」

タイとチリへ出張　社員が n 人の会社。仕事の都合で k 人がタイへ出張し、同時に別の ℓ 人がチリへ出張する。

n 人のうち k 人がタイへ行く選択肢「n選ぶk」　(n C k)

タイ行き以外の n−k 人のうちの ℓ 人がチリへ行く選択肢「n−k 選ぶ ℓ」　(n−k C ℓ)

トータルでの出張メンバーの選び方のパターン数　(n C k)(n−k C ℓ)

タイ行きの k 人を先に決める代わりに、チリ行きの ℓ 人を先に決めても、トータルの選択肢は増えも減りもしない。「n 人から k 人と ℓ 人を重複なく選ぶ」という本質は同じだから。

n 人のうち ℓ 人がチリへ行く選択肢「n選ぶℓ」　(ℓ C n)

チリ行き以外の n−ℓ 人のうちの k 人がタイへ行く選択肢「n−ℓ 選ぶ k」　(n−ℓ C k)

トータルでの出張メンバーの選び方のパターン数　(n C ℓ)(n−ℓ C k)

どちらの考え方でもパターン数は同じなので、次の関係が成り立つ。

「タイ・チリの法則」　(n C k)(n−k C ℓ) = (n C ℓ)(n−ℓ C k)　　‥‥❹

「予選・本選」と同じような話だが…。成り立つこと自体は、直観的に明らかだろう。もちろん階乗表現を使って、機械的に証明することもできる。ここでは、ちょっとひねって、「予選・本選の法則」と「対称性」のコンボで❹を証明してみる。

二項係数の対称性（三つの基本、その3）から (n C k) = (n C n−k) なので、❹の左辺は、こうなる:
　　(n C k)(n−k C ℓ) = (n C n−k)(n−k C ℓ)

この右辺は、 n−k を「約分」して「予選・本選の法則」を発動できる形だ！
　　 = (n C ℓ)(n−ℓ C n−k−ℓ)　　‥‥❺

❺の右側の二項係数に、再び対称性を適用すると:
　　(n−ℓ C n−k−ℓ) = (n−ℓ C (n−ℓ)−(n−k−ℓ)) = (n−ℓ C k)　　‥‥❻
❻は❹の右辺なので、これで「❹の左辺 = ❹の右辺」が証明された。

❻の二つ目の等号は、下側インデックスの単純計算。一つ目の等号は、微妙にゴチャゴチャしてるけど、❻の左端の二項係数について、上側インデックス n−ℓ を a、下側インデックス n−k−ℓ を b とでも置いてみよう。すると、
　　(a C b) = (a C a−b)
という基本操作に過ぎない。念のためその意味を復習すると、「a 人中 b 人を合格にすること」と「a 人中 a−b 人を不合格にすること」は同じ意味、と。あるいは逆に、❻に対称性を適用すると、
　　❻ = (n−ℓ C (n−ℓ)−k)
となって、確かに❺の右側の因子と一致するっ！

二項係数については、研究すべき事柄・面白い性質が多い。このメモの内容はそのほんの一部だけど、ベルヌーイのべき和公式の証明（その1、その2）で使う処理は、おおまかカバー。抜けてる点は、次回に。

---

2025-04-02　二項係数・超入門の補足　抽出と吸収

#遊びの数論　#ベルヌーイの公式

「超入門」に一つ書き忘れてたことがあるので、以下で追加。
　　(10 × 9 × 8 × 7)/(4 × 3 × 2 × 1) = 10/4 × (9 × 8 × 7)/(3 × 2 × 1)
のような当たり前の等式が、二項係数の変形では基本技となる。

「抽出」

二項係数の定義から、上記の等式は、
　　(10 C 4) = 10/4 × (9 C 3)
という関係だ。実際、
　　(10 C 4) = (10^↓4)/(4!) = (10 × 9 × 8 × 7)/(4 × 3 × 2 × 1)
という数は、
　　(9 C 3) = (9^↓3)/(3!) = (9 × 8 × 7)/(3 × 2 × 1)
の 10/4 倍。

一般に、
　　(n C k) = (n^↓k)/(k!) = (n(n−1)(n−2)··· (n−k+1))/(k(k−1)(k−2)··· 1)　ア
という数は、
　　(n−1 C k−1) = ((n−1)^↓(k−1))/((k−1)!) = ((n−1)(n−2)··· (n−k+1))/((k−1)(k−2)··· 1)　イ
の n/k 倍に等しい。なぜならば…

アの分母は 1 から k までの整数の積、イの分母は 1 から k−1 までの整数の積なので、前者は後者の k 倍。一方、アの分子は、
　　n から始めて 1 ずつ小さくなる k 個の整数の積
だが、イの分子は、
　　n−1 から始めて 1 ずつ小さくなる k−1 個の整数の積
なので、前者は後者のちょうど n 倍に当たる。

アの分子は k 個の数の積
n ×	(n−1) ×	(n−2) ×	··· ×	(n−k+1)
	(n−1) ×	(n−2) ×	··· ×	(n−k+1)
	イの分子は k−1 個の数の積

n から n−k+1 までの整数は合計 k 個なんで、その k 個の整数の先頭の 1 個を除去して、
　　n−1 から n−k+1 までの整数
を考えると、そこにあるのは合計 k−1 個の整数。で、それら k−1 個の整数の積が、イの分子 (n−1)^↓(k−1) だ。

〔注〕　一般に a^↓b は、始点 a から終点 a − b + 1 までの（1 ずつ小さくなる）数の積。アの分子では、単に a = n, b = k と文字を変更するだけだが、イの分子では a = n−1, b = k−1 というやや複雑な関係になっている。この下りの始点が n−1 であることは明白。終点は、
　　a − b + 1 = (n−1) − (k−1) + 1 = n − 1 − k + 1 + 1 = n − k + 1
となって、アの分子の終点と一致する。イメージとしては、「長い階段の、とある段 a から10段下の場所」は、「一つ下の段 a−1 から見たら9段下」――「10段下」「9段下」を任意の「b 段下」「b−1 段下」に置き換えることができる。

結論として、二項係数 (n C k) は、同じ形の分数 (n/k) と、上下のインデックスを 1 ずつ減らした二項係数 (n−1 C k−1) の、積に等しい。言い換えると、 (n C k) から因子 (n/k) を分離させると、上下のインデックスが 1 ずつ小さくなる。

二項係数から同じ形の分数を抽出（上下のインデックスが 1 ずつ減少）
　　(n C k) = (n/k)(n−1 C k−1)
　　別の例　(n+1 C k+1) = (n+1)/(k+1) (n C k)

例えば、ベルヌーイの公式の証明の中の、
　　(j+1 C j−k) は (j+1 C (j+1)−(j−k)) = (j+1 C k+1) に等しく、それは (j + 1)/(k + 1)(j C k) に等しいので
という部分。最初の「に等しく」は、二項係数の対称性（三つの基本、その3）による。その後ろの「に等しい」は、上記の「分数抽出」。

「吸収」

「抽出」を逆向きに使えば、二項係数に掛け算されてる分数を「吸収」できる。分子・分母が、それぞれ上下のインデックスより 1 大きい場合だ。例えば、
　　(n+1)/(k+1) (n C k)
という積は、分数を二項係数に吸収させれば (n+1 C k+1) というシンプルな表現に一本化される。

ベルヌーイの公式の証明では、次の部分でこの基本技が使われている。
　　∑{k=0 to m} [[m + 1/(k + 1)] (m C k)⋅n^k+1] = ∑{k=0 to m} (m+1 C k+1) n^k+1

奥義「下側不動」

二項係数を扱ってるとき、「下側インデックスを変えずに上側インデックスを 1 ずらしたい」場合がある。仮に、
　　(m+1 C k)
が現れたとすると、上側インデックスに含まれる +1 がちょい邪魔。もしこの二項係数から、同じ形の分数を抽出するなら、上下が 1 ずつ減って、
　　(m C k−1)
を使う形になる。それだと、下側インデックスに含まれる −1 が邪魔。シンプルに (m C k) を使いたい。

例えば、
　　(11 C 4) = (11 × 10 × 9 × 8)/4!
と、
　　(10 C 4) = (10 × 9 × 8 × 7)/4!
を比較すると、どっちも分母は同じ。分子の積の始点・終点が、それぞれ 1 ずれてるだけ。後者を 11 倍して 7 で割れば、前者になる:
　　(11 C 4) = (11/7)(10 C 4)

つまり (11 C 4) が与えられたとして、その下側インデックスを一定に保ったまま上側インデックスを 1 小さくしたければ、インデックス変更の代償として (11/7) を掛け算してやればいい。

一般に、
　　(a C b) = (a(a−1)···(a−b+1))/b!
と、
　　(a−1 C b) = ((a−1)(a−2)··· (a−b))/b!
を比較すると、どっちも分母は同じ。分子の積の始点・終点が、それぞれ 1 ずれてるだけ。後者を a 倍して a−b で割れば、前者になる。すなわち:

下側不動（下側インデックスを保ったまま上側を 1 減らす）
　　(a C b) = a/(a−b)(a−1 C b)
インデックス調整の代償として、新しい二項係数にもともとの上側インデックス a を掛け、もともとの上下の差 a−b で割っている。

特に a = m+1, b = k とすると:
　　(m+1 C k) = m+1/(m+1−k)(m C k)

ベルヌーイの公式の証明の中で、
　　二項係数 (m+1 C k) は (m C k) の (m + 1)/(m − k + 1) 倍なので
という部分は、まさにこのインデックス調整。フォン・シュタウト＆クラウンセンの定理の証明の中で、
　　(m+1 C k)⋅(B_k)p^m−k/(m+1)
を
　　(m C k)⋅(B_k)p^m−k/(m+1−k)
に置き換えているのも、全く同じ「下側不動」調整に当たる（調整の結果、分数 m+1/(m+1−k) が掛け算され、その分子と、もともとあった分母の m+1 が約分されて消滅、 m+1−k が新しい分母となる）。

この変形法は、二項係数の定義から容易に導出可能だが（上記）、「分数抽出」の応用としても、次のように簡潔に証明可能^†。対称性から:
　　(a C b) = (a C a−b)
右辺の二項係数から、同じ形の分数を抽出すると:
　　= a/(a−b)(a−1 C a−b−1)
この下側インデックスは (a−1)−b に等しいので――そして上側インデックスは a−1 なので――、再び対称性を使って^‡、下側を b に戻すことができる:
　　= a/(a−b)(a−1 C b)

†　Concrete Mathematics (2nd ed.), p. 157.

‡　a−1 個のアイテムのうち、 b 個を宝箱に入れ、残りの (a−1)−b 個をごみ箱に捨てるとする。 a−1 個のアイテムから、「宝箱に入れる b 個を選択」する操作は、同じ a−1 個のアイテムから「ごみ箱に捨てる (a−1)−b 個を選択」する操作と同等。実際、宝箱に入れるアイテムを決めれば、自動的にごみ箱行きアイテムも決まるし、逆もまたしかり。

---

『遊びの数論40』へ続く。

---