調和級数（数学）

数学において、調和級数とは、すべての正の単位分数を合計することによって形成される無限級数です。 $${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n}}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots .}$$

級数の最初の項を合計すると、およそ になります。ここで、は自然対数、はオイラー・マスケローニ定数です。対数は任意の大きな値を持つため、調和級数には有限の極限がありません。これは発散級数です。その発散は、無限級数の収束に関するコーシー凝縮テストの前身を使用して、14世紀にニコル・オレームによって証明されました。収束の積分テストに従って、和を積分と比較することによって発散することも証明できます。 ${\displaystyle n}$${\displaystyle \ln n+\gamma }$${\displaystyle \ln }$${\displaystyle \gamma \approx 0.577}$

調和級数とその部分和の応用としては、素数が無限に存在するというオイラーの証明、完全な範囲の応答を提供するのに何回のランダム試行が必要であるかというクーポン収集者の問題の分析、ランダム グラフの連結成分、ブロックの積み重ねをテーブルの端からどれだけはみ出させることができるかというブロック積み重ね問題、クイックソートアルゴリズムの平均ケースの分析などがあります。

倍音列という名前は、音楽の倍音または倍音の概念に由来しています。振動する弦の倍音の波長は、弦の基本波長の、、などです。^{[1] [2]} 倍音列の最初の項に続く各項は、隣接する項の調和平均であるため、項は調和数列を形成します。調和平均や調和数列というフレーズも同様に音楽に由来しています。^[2] 音楽以外では、倍音列は建築家にも一定の人気がありました。これは特にバロック時代に顕著で、建築家はそれをフロアプランや立面図の比率を確立したり、教会や宮殿の内外の建築ディテール間の調和関係を確立するために使用しました。^[3]${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle {\tfrac {1}{3}}}$ ${\displaystyle {\tfrac {1}{4}}}$

調和級数の発散は、1350年にニコラ・オレームによって初めて証明されました。^{[2] [4]オレームの研究と、同時期に}リチャード・スウィンズヘッドが行った別の級数に関する研究は、数学において等比級数以外の無限級数が初めて登場したことを示しています。 ^[5]しかし、この業績は忘れ去られました。^[6]追加の証明は、17世紀にピエトロ・メンゴリ^{[2] [7]と}ヤコブ・ベルヌーイによって出版されました。^{[8] [9] [10]}ベルヌーイは、この証明を発見したのは弟のヨハン・ベルヌーイであることを認め、 ^[10]後にヨハン・ベルヌーイの全集に収められました。^[11]

調和級数の部分和は調和数と名付けられ、1968年にドナルド・クヌースによって通常の表記法が与えられた。^[12]${\displaystyle H_{n}}$

調和級数は、 項がすべて正の単位分数である無限級数です。これは発散級数です。つまり、級数の項が級数の部分和に含まれるにつれて、これらの部分和の値は有限の限界を超えて任意に大きくなります。これは発散級数であるため、数値に評価できるものとしてではなく、単位分数を組み合わせた抽象的な数式である形式的な和として解釈する必要があります。調和級数の発散の証明は数多くあり、SJ Kifowit と TA Stamps による 2006 年の論文で概説されています。^[13] 最もよく知られている 2 つの証明^{[1] [13]}を以下に挙げます。 $${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n}}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots }$$

発散を証明する一つの方法は、調和級数を別の発散級数と比較することである。ここで、各分母は次に大きい2のべき乗に置き換えられる。 等しい項をグループ化すると、2番目の級数が発散することが示される（収束級数のすべてのグループ化は収束のみであるため）。調和級数の各項 は2番目の級数の対応する項以上であり（そして項はすべて正である）、2番目の級数が発散するため、（比較テストにより）調和級数も発散することが導かれる。同じ議論は、すべての正の整数に対して、 であることをより強く証明する。これは、 1350年頃にニコル・オレーム によって与えられた最初の証明である。 ^[13]コーシー凝縮テストはこの議論の一般化である。^[14]$${\displaystyle {\begin{alignedat}{8}1&+{\frac {1}{2}}&&+{\frac {1}{3}}&&+{\frac {1}{4}}&&+{\frac {1}{5}}&&+{\frac {1}{6}}&&+{\frac {1}{7}}&&+{\frac {1}{8}}&&+{\frac {1}{9}}&&+\cdots \\[5pt]{}\geq 1&+{\frac {1}{2}}&&+{\frac {1}{\color {red}{\mathbf {4} }}}&&+{\frac {1}{4}}&&+{\frac {1}{\color {red}{\mathbf {8} }}}&&+{\frac {1}{\color {red}{\mathbf {8} }}}&&+{\frac {1}{\color {red}{\mathbf {8} }}}&&+{\frac {1}{8}}&&+{\frac {1}{\color {red}{\mathbf {16} }}}&&+\cdots \\[5pt]\end{alignedat}}}$$$${\displaystyle {\begin{aligned}&1+\left({\frac {1}{2}}\right)+\left({\frac {1}{4}}+{\frac {1}{4}}\right)+\left({\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}\right)+\left({\frac {1}{16}}+\cdots +{\frac {1}{16}}\right)+\cdots \\[5pt]{}={}&1+{\frac {1}{2}}+{\frac {1}{2}}+{\frac {1}{2}}+{\frac {1}{2}}+\cdots .\end{aligned}}}$$ ${\displaystyle k}$ $${\displaystyle \sum _{n=1}^{2^{k}}{\frac {1}{n}}\geq 1+{\frac {k}{2}}}$$

調和級数が発散することは、その和を仮積分と比較することによって証明することができる。具体的には、右の図に示す長方形の配置について考えてみよう。各長方形は幅が 1 単位、高さが 単位なので、調和級数が収束するなら、長方形の総面積は調和級数の和になる。曲線は長方形の上限より完全に下にあるので、曲線の下の面積（長方形で覆われる 1 から無限大の範囲）は長方形の和の面積よりも小さくなる。しかし、曲線の下の面積は発散仮積分によって与えられる。 この積分は収束しないので、和も収束しない。^[13]${\displaystyle {\tfrac {1}{n}}}$${\displaystyle y={\tfrac {1}{x}}}$${\displaystyle x}$$${\displaystyle \int _{1}^{\infty }{\frac {1}{x}}\,dx=\infty .}$$

右の図では、各長方形を 1 単位ずつ左にずらすと、曲線の上ではなく下に境界がある長方形の列が生成されます。これは、調和級数の部分和が積分と異なる量であり、その量は最初の長方形の単位面積によって上下に制限されることを示しています。 この議論を一般化すると、（調和級数のように）の 単調減少正関数の値の任意の無限和は、対応する積分の値から制限された距離内にある部分和を持ちます。したがって、同じ関数の同じ範囲での積分が収束する場合に限り、和は収束します。この同値性を使用して、より簡単な積分に置き換えて和の収束を確認する場合、それは収束の積分テストとして知られています。^[15]$${\displaystyle \int _{1}^{N+1}{\frac {1}{x}}\,dx<\sum _{i=1}^{N}{\frac {1}{i}}<\int _{1}^{N}{\frac {1}{x}}\,dx+1.}$$${\displaystyle n}$

調和級数の最初の項を加えると部分和が生成され、これは調和数と呼ばれ、次のように表記される。^[12]${\displaystyle n}$${\displaystyle H_{n}}$ $${\displaystyle H_{n}=\sum _{k=1}^{n}{\frac {1}{k}}.}$$

これらの数値は、積分テストからわかるように、対数的に非常にゆっくりと増加します。 ^[15]より正確には、オイラー・マクローリンの公式により、 ここで はオイラー・マスケローニ定数であり、無限大に近づくにつれて 0 に近づきます。^[16]$${\displaystyle H_{n}=\ln n+\gamma +{\frac {1}{2n}}-\varepsilon _{n}}$$${\displaystyle \gamma \approx 0.5772}$${\displaystyle 0\leq \varepsilon _{n}\leq 1/8n^{2}}$${\displaystyle n}$

を除いて調和数は整数ではない。^{[17] [18]}が整数でないことを証明する方法の 1 つは、 1 から までの範囲で2 の最大の累乗を考えることである。が1から までの数の最小公倍数である場合、は 、 分子 の 1 つだけが奇数で残りが偶数である、等しい分母を持つ分数の和として書き直すことができ、( のとき)自体が偶数である。したがって、結果は分子が奇数で分母が偶数である分数となり、これは整数にはならない。^[17]より一般的には、連続する整数の列には、他のすべての要素よりも 2 の累乗で割り切れる要素が 1 つだけあり、同じ議論から、2 つの調和数は整数だけ異なることはないことが分かる。^[18]${\displaystyle H_{1}=1}$${\displaystyle H_{n}}$ ${\displaystyle 2^{k}}$${\displaystyle n}$${\displaystyle M}$${\displaystyle n}$${\displaystyle H_{k}}$$${\displaystyle H_{n}=\sum _{i=1}^{n}{\tfrac {M/i}{M}}}$$${\displaystyle M/2^{k}}$${\displaystyle n>1}$ ${\displaystyle M}$

調和数は整数ではないという別の証明は、 の分母がより大きいかつより小さいか等しいすべての素数で割り切れる必要があることに着目し、この素数集合が空でないことを証明するためにベルトランの公理を使用する。同じ議論は、 、、およびを除いて、調和数は終端小数表現を持つことができないことをより強く示唆している。^[17]すべての素数は調和数の有限部分集合の分子のみを割り切れると推測されているが、これはまだ証明されていない。^[19]${\displaystyle H_{n}}$${\displaystyle n/2}$${\displaystyle n}$${\displaystyle H_{1}=1}$${\displaystyle H_{2}=1.5}$${\displaystyle H_{6}=2.45}$

二ガンマ関数はガンマ関数の対数微分として定義されます 。ガンマ関数が階乗の連続補間を提供するのと同様に、二ガンマ関数は調和数の連続補間、つまり を意味します。^[20] この式は、定義を有理数インデックスの調和数に拡張するために使用できます。^[21] $${\displaystyle \psi (x)={\frac {d}{dx}}\ln {\big (}\Gamma (x){\big )}={\frac {\Gamma '(x)}{\Gamma (x)}}.}$$${\displaystyle \psi (n)=H_{n-1}-\gamma }$

多くのよく知られた数学の問題には、調和級数とその部分和を含む解法があります。

ジープ問題、あるいは砂漠横断問題は、アルクインによる9世紀の問題集『若者の命題』（ジープではなくラクダを使って定式化されている）に掲載されているが、解答は間違っている。^[22]問題は、燃料を満載した基地を出発し、燃料の一部を砂漠に運び、補給所に置いていった場合、ジープが砂漠のどこまで進んで戻ってくることができるかを問うものである。最適な解答は、出発点から の距離と互いの距離を置いて補給所を配置することである。ここで は、ジープが1回の燃料積載で移動できる距離の範囲である。基地からの往復ごとに、ジープは補給所を1つ追加し、途中で他の補給所で燃料を補給し、新しく配置した補給所にできるだけ多くの燃料を積み込みながら、以前の補給所と基地に戻るのに十分な燃料を残しておく。したがって、番目の旅行で到達する総距離は であり、 ここで は番目の調和数である。調和級数の発散は、十分な燃料があれば任意の長さの横断が可能であることを意味する。^[23]${\displaystyle n}$${\displaystyle {\tfrac {r}{2n}},{\tfrac {r}{2(n-1)}},{\tfrac {r}{2(n-2)}},\dots }$${\displaystyle r}$${\displaystyle n}$$${\displaystyle {\frac {r}{2n}}+{\frac {r}{2(n-1)}}+{\frac {r}{2(n-2)}}+\cdots ={\frac {r}{2}}H_{n},}$$${\displaystyle H_{n}}$${\displaystyle n}$

例えば、アルクインの問題では、ラクダは30マスの穀物を運ぶことができ、1マスを食べながら1レウカを移動することができます。ここで、レウカはおよそ2.3キロメートル（1.4マイル）に等しい距離の単位です。問題には、3回の往復に十分な90マスの穀物があります。砂漠横断問題の標準的な定式化では、1回目の旅行で基地から5レウカ、2回目の旅行で基地から12.5レウカに穀物貯蔵庫を置くことで、ラクダがレウカを移動して戻ってくることは可能です。しかし、アルクインは代わりに、最終的な帰路なしで30レウカの距離をどれだけの穀物を輸送できるかという少し異なる質問をし、砂漠でラクダが立ち往生するか、ラクダが帰路で消費する穀物の量を考慮していないかのどちらかになります。^[22]${\displaystyle r=30}$${\displaystyle n=3}$${\displaystyle {\tfrac {30}{2}}{\bigl (}{\tfrac {1}{3}}+{\tfrac {1}{2}}+{\tfrac {1}{1}})=27.5}$

ブロック積み上げ問題では、同じ長方形のブロックを 1 層に 1 つずつ積み上げ、できるだけテーブルの端から垂れ下がって落ちないようにする必要があります。一番上のブロックは、その長さの が次の下のブロックよりはみ出すように配置できます。このように配置する場合、次の下のブロックは、その長さの が次の下のブロックよりはみ出すように配置する必要があります。そうすることで、上の 2 つのブロックの重心が支えられ、倒れないようにできます。3 番目のブロックは、その長さの が次の下のブロックよりはみ出すように配置する必要があります。このようにして、ブロックをテーブルから の長さだけはみ出すように配置できます。ここで は番目の調和数です。^{[24] [25]}調和級数の発散は、ブロック スタックがテーブルからどれだけはみ出すことができるかに制限がないことを意味します。^[25] 1 層あたり 1 つのブロックのスタックでは、これより優れた解決策はありませんが、1 層あたり 2 つ以上のブロックのスタックを使用すると、はるかに大きなはみ出しを実現できます。^[26]${\displaystyle n}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle {\tfrac {1}{2}}\cdot {\tfrac {1}{2}}}$${\displaystyle {\tfrac {1}{2}}\cdot {\tfrac {1}{3}}}$${\displaystyle n}$${\displaystyle {\tfrac {1}{2}}H_{n}}$${\displaystyle H_{n}}$${\displaystyle n}$

1737 年、レオンハルト・オイラーは、形式的な和として、調和級数は各項が素数から得られるオイラー積に等しいことを観察しました。ここで、 は素数の集合を表します。左の等式は、積に分配法則を適用し、結果として得られる項を調和級数の項の素因数分解として認識することから得られ、右の等式は等比級数の標準公式を使用します。積は和と同様に発散しますが、収束する場合は、対数をとって次の式を得ることができます。ここで、各対数はそのテイラー級数 に置き換えられ、右側の定数は指数が 1 より大きい項の収束級数の評価です。これらの操作から、この等式の右側にある素数の逆数の和は発散するはずです。なぜなら、収束する場合は、これらの手順を逆にして調和級数も収束することを示すことができるからですが、実際には収束しません。直ちに導かれる帰結は、有限和は発散しないので、素数は無限に存在するということである。^[27]オイラーの研究は現代数学の基準からすると十分に厳密であるとは考えられていないが、極限と誤差の境界にもっと注意を払うことで厳密なものにすることができる。^[28]素数の逆数の部分和は項の数の二重対数に比例して増加するというオイラーの結論は、後の数学者によってメルテンスの定理の1つとして確認されており、^[29]素数定理の前身と見なすことができる。^[28]$${\displaystyle \sum _{i=1}^{\infty }{\frac {1}{i}}=\prod _{p\in \mathbb {P} }\left(1+{\frac {1}{p}}+{\frac {1}{p^{2}}}+\cdots \right)=\prod _{p\in \mathbb {P} }{\frac {1}{1-1/p}},}$$${\displaystyle \mathbb {P} }$$${\displaystyle \ln \prod _{p\in \mathbb {P} }{\frac {1}{1-1/p}}=\sum _{p\in \mathbb {P} }\ln {\frac {1}{1-1/p}}=\sum _{p\in \mathbb {P} }\left({\frac {1}{p}}+{\frac {1}{2p^{2}}}+{\frac {1}{3p^{3}}}+\cdots \right)=\sum _{p\in \mathbb {P} }{\frac {1}{p}}+K.}$$${\displaystyle K}$

調和級数と密接に関係する整数論における別の問題は、1 から までの数の平均約数個数に関するもので、約数関数の平均位数として形式化される。 調和級数の各項を の次のより小さい整数倍に丸める操作により、この平均は調和数とは小さな定数だけ異なるが、ピーター・グスタフ・ルジューン・ディリクレはより正確に、平均約数個数は（大文字の O 表記で表す）であることを示した。最終的な誤差項をより正確に制限することは、ディリクレの約数問題として知られる未解決の問題のままである。^[30]${\displaystyle n}$$${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}\left\lfloor {\frac {n}{i}}\right\rfloor \leq {\frac {1}{n}}\sum _{i=1}^{n}{\frac {n}{i}}=H_{n}.}$$${\displaystyle {\tfrac {1}{n}}}$${\displaystyle \ln n+2\gamma -1+O(1/{\sqrt {n}})}$

いくつかの一般的なゲームやレクリエーションでは、すべての可能な選択肢が選択されるまで、アイテムのセットからランダムに選択を繰り返す必要があります。これには、トレーディングカードの収集^{[31] [32]}や、一連のランニングイベントから時間の可能な60の秒数をすべて取得することを目的としたパークランビンゴの完了が含まれます。 ^[33]この問題のより深刻な応用には、製造された製品のすべてのバリエーションを品質管理のためにサンプリングすること、^[34]、およびランダムグラフの接続性が含まれます。^[35]この形式の状況では、合計で均等に発生する可能性のあるアイテムのうち、収集するアイテムが残っている場合、1回のランダム選択で新しいアイテムを収集する確率は であり、新しいアイテムが収集されるまでに必要なランダム選択の期待数はです。から1までのすべての値を合計すると、すべてのアイテムを収集するために必要なランダム選択の期待数の合計は であり、は番目の調和数であることがわかります。^[36]${\displaystyle k}$${\displaystyle n}$${\displaystyle k/n}$${\displaystyle n/k}$${\displaystyle k}$${\displaystyle n}$ ${\displaystyle nH_{n}}$${\displaystyle H_{n}}$${\displaystyle n}$

アイテムのセットをソートするためのクイックソートアルゴリズムは、調和数を使用して分析できます。このアルゴリズムは、1 つのアイテムを「ピボット」として選択し、それを他のすべてのアイテムと比較し、比較によってピボットの前とピボットの後になる 2 つのアイテムのサブセットを再帰的にソートすることによって機能します。平均ケースの複雑さ(すべての入力順列が等しく起こりうると仮定) またはランダムにピボットを選択した最悪のケースの入力の予想時間分析のいずれにおいても、すべてのアイテムがピボットとして選択される可能性は等しくなっています。このような場合、再帰全体を通じて 2 つのアイテムが互いに比較される確率を、最終的なソート順序でそれらを分離する他のアイテムの数の関数として計算できます。アイテムとが他のアイテムによって分離されている場合、アルゴリズムは、再帰の進行中に、その間にある他のアイテムを選択する前にピボットとしてまたはを選択する場合にのみ、とを比較します。これらの各アイテムが最初に選択される可能性は等しいため、これは確率 で発生します。アルゴリズムの総実行時間を制御する比較の総予想回数は、すべてのペアについてこれらの確率を合計することによって計算でき、^{[37]調和級数の発散は、このアプリケーションでは、クイックソートに使用される}ソートの比較モデルでは線形時間でソートできないという 事実に対応しています。^[38]${\displaystyle x}$${\displaystyle y}$${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle k}$${\displaystyle k+2}$${\displaystyle {\tfrac {2}{k+2}}}$ $${\displaystyle \sum _{i=2}^{n}\sum _{k=0}^{i-2}{\frac {2}{k+2}}=\sum _{i=1}^{n-1}2H_{i}=O(n\log n).}$$

この級数は 交代調和級数 として知られている。交代級数テストでは条件付き収束するが、絶対収束しない。その和は2の自然対数である。^[39]$${\displaystyle \sum _{n=1}^{\infty }{\frac {(-1)^{n+1}}{n}}=1-{\frac {1}{2}}+{\frac {1}{3}}-{\frac {1}{4}}+{\frac {1}{5}}-\cdots }$$

より正確には、級数の漸近展開は として始まります。 これは、等式とオイラー・マクローリンの公式から生じます。 $${\displaystyle {\frac {1}{1}}-{\frac {1}{2}}+\cdots +{\frac {1}{2n-1}}-{\frac {1}{2n}}=H_{2n}-H_{n}=\ln 2-{\frac {1}{4n}}+O(n^{-2}).}$$${\textstyle H_{n}=2\sum _{k=1}^{n}{\frac {1}{2k}}}$

奇数単位分数のみで符号を交互に使用すると、関連する数列、πのライプニッツの公式が得られる^[40] $${\displaystyle \sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}=1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots ={\frac {\pi }{4}}.}$$

リーマンゼータ関数は、実数に対して収束級数 によって 定義され 、 に対しては調和級数 となる。これは、を除くすべての複素数上の正則関数に解析接続によって拡張することができ、拡張された関数は単純な極を持つ。ゼータ関数の他の重要な値には、バーゼル問題の解、ロジャー・アペリによって無理数であることが証明されたアペリの定数、および、リーマン予想によって、関数がゼロになり得る負の整数以外の唯一の値であると推測された、実部を持つ複素数の「臨界線」 などがある。 ^[41]${\displaystyle x>1}$$${\displaystyle \zeta (x)=\sum _{n=1}^{\infty }{\frac {1}{n^{x}}}={\frac {1}{1^{x}}}+{\frac {1}{2^{x}}}+{\frac {1}{3^{x}}}+\cdots ,}$$${\displaystyle x=1}$ ${\displaystyle x=1}$${\displaystyle \zeta (2)=\pi ^{2}/6}$ ${\displaystyle \zeta (3)}$${\displaystyle {\tfrac {1}{2}}}$

ランダム調和級数 とは、 値が独立かつ同一に分布するランダム変数で、 2 つの値と を等しい確率で取る場合です。コルモゴロフの 3 級数定理または密接に関連したコルモゴロフ最大不等式を使用するとわかるように、これは確率 1 で収束します。級数の合計は、確率密度関数がからまでの値に対してに近く、より大きいかより小さい値に対してほぼゼロに減少するランダム変数です。これらの範囲の中間の値では、確率密度は0 ではないが非常に小さい値 に対して です。^{[42] [43]}$${\displaystyle \sum _{n=1}^{\infty }{\frac {s_{n}}{n}},}$$${\displaystyle s_{n}}$${\displaystyle +1}$${\displaystyle -1}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle {\tfrac {1}{4}}}$${\displaystyle -1}$${\displaystyle 1}$${\displaystyle 3}$${\displaystyle -3}$${\displaystyle \pm 2}$${\displaystyle {\tfrac {1}{8}}-\varepsilon }$${\displaystyle \varepsilon <10^{-42}}$

分母のどこかに数字9が現れる項をすべて取り除いた減数調和級数は、22.92067 66192 64150 34816 ...という値に収束することが示せます。^{[44]実際、任意の特定の数字列（任意の}基数）を含む項をすべて取り除くと、級数は収束します。^[45]

ウィキメディア・コモンズには、調和級数 (数学)に関連するメディアがあります。

• Weisstein、Eric W.「調和級数」。MathWorld。