不等式を数学的帰納法で示す｜2 の n 乗と n の 2 乗の逆転はどこか

$2^{n}$ と $n^{2}$ に $n = 1$ から順に入れると、 $2$ と $1$ 、 $4$ と $4$ 、 $8$ と $9$ 、 $16$ と $16$ 、 $32$ と $25$ と並びます。大小が 2 度いれかわり、 $n = 5$ から先は $2^{n}$ が離していく。

$2^{n} > n^{2}$ を帰納法で示すなら、出発点は $n = 5$ 。命題が成り立ちはじめる場所を探すのが最初の仕事です。

等式なら左辺を変形して右辺にたどり着けば終わります。不等式では、仮定から進んだ先が目標にわずかに届かないことがある。どれだけ余りを残して進むかが、そのつど問題になります。

例：2 の n 乗と n

先に易しい形で進め方を見ます。 $n \geq 1$ で $2^{n} > n$ を示す。

$n = 1$ のとき $2 > 1$ 。

$n = k$ で $2^{k} > k$ を仮定し、両辺を $2$ 倍する。

$2^{k + 1} = 2 \cdot 2^{k} > 2 k = k + k \geq k + 1$

最後の $\geq$ は $k \geq 1$ から来ています。仮定を使って $2 k$ まで下げ、そこから $k + 1$ へ落とす。2 段階に分かれる。

仮定だけでは $k + 1$ に届かず、 $k \geq 1$ という別の条件を足して届かせました。この足し方が不等式の帰納法の中心にあります。

例：2 の n 乗と n の 2 乗

$n \geq 5$ で $2^{n} > n^{2}$ を示します。

$n = 5$ のとき $32 > 25$ 。

$n = k (k \geq 5)$ で $2^{k} > k^{2}$ を仮定し、両辺を $2$ 倍する。

$2^{k + 1} = 2 \cdot 2^{k} > 2 k^{2}$

あとは $2 k^{2} \geq (k + 1)^{2}$ を示せば $(k + 1)^{2}$ まで届きます。差をとって形を整える。

$2 k^{2} - (k + 1)^{2} = k^{2} - 2 k - 1 = (k - 1)^{2} - 2$

$k \geq 5$ なら $(k - 1)^{2} \geq 16$ となるため、この差は正。

$2^{k + 1} > 2 k^{2} \geq (k + 1)^{2}$

途中で「あと何を示せば届くか」を書き出すと、目標との距離が見えます。答案でも、その 1 行を残しておくと筋が読みとりやすくなる。

ベルヌーイの不等式

$x \geq - 1$ と $n \geq 1$ のもとで、次が成り立ちます。ヤコブ・ベルヌーイが 1689 年の無限級数についての論考で使い、名前がついたものです^[1]。

$(1 + x)^{n} \geq 1 + n x$

左辺は $n$ 乗、右辺は 1 次式。伸び方がまるで違うのに、左が下回ることはありません。

例：ベルヌーイの不等式の証明

$n = 1$ のとき $(1 + x)^{1} = 1 + x$ で、等号が成り立ちます。

$n = k$ で $(1 + x)^{k} \geq 1 + k x$ を仮定し、両辺に $1 + x$ をかける。ここで $x \geq - 1$ より $1 + x \geq 0$ となるため、不等号の向きは変わりません。

$(1 + x)^{k + 1} \geq (1 + k x) (1 + x) = 1 + (k + 1) x + k x^{2}$

$k x^{2} \geq 0$ だから、この項を捨てても不等号は保たれる。

$(1 + x)^{k + 1} \geq 1 + (k + 1) x$

$x \geq - 1$ という条件が効いたのは、両辺に $1 + x$ をかけた場所です。負の数をかければ向きが変わるため、符号の確認がそこに入ります。

余った $k x^{2}$ を捨てて目標の形にそろえる。不等式では、こうして余りを切り落とす操作がくり返し現れます。

ベルヌーイの不等式の証明で、 $x \geq - 1$ という条件はどこで使いますか。

出発点の確認
仮定の両辺に $1 + x$ をかけるとき
$k x^{2} \geq 0$ を使うとき
使わない

__RESULT__

負の数をかけると不等号の向きが変わります。 $1 + x \geq 0$ だから、向きを変えずにかけられます。

例：入れ子になった平方根

$a_{1} = 2$ 、 $a_{n + 1} = 2 + a_{n}$ で定まる数列について、すべての $n$ で $a_{n} < 2$ を示します。

$n = 1$ のとき $2 < 2$ 。

$n = k$ で $a_{k} < 2$ を仮定する。

$a_{k + 1} = 2 + a_{k} < 2 + 2 = 2$

平方根は大小の向きを保つので、中身をくらべるだけで済みました。 $2$ という数は、 $x = 2 + x$ を解いて見つけたものです。

漸化式で定まる数列の評価では、この形がよく使える。上から押さえる数を先に見つけておくと、帰納の段階がそのまま通る。

命題を強めると通ることがある

仮定をそのまま使っても目標に届かないとき、証明したい命題をわざと強くする手があります。

$b_{n} = \frac{1}{n + 1} + \frac{1}{n + 2} + \dots + \frac{1}{2 n}$ について、 $b_{n} \geq \frac{1}{2}$ を示す場合です。

$b_{1} = \frac{1}{2}$ 、 $b_{2} = \frac{1}{3} + \frac{1}{4} = \frac{7}{12}$ 、 $b_{3} = \frac{1}{4} + \frac{1}{5} + \frac{1}{6} = \frac{37}{60}$ と、少しずつ増えています。

そこで「 $\frac{1}{2}$ 以上」ではなく「増えていく」を示す。差をとると、先頭が 1 つ抜けて末尾が 2 つ増える。

$b_{n + 1} - b_{n} = \frac{1}{2 n + 1} + \frac{1}{2 n + 2} - \frac{1}{n + 1} = \frac{1}{2 n + 1} - \frac{1}{2 n + 2} > 0$

$b_{1} = \frac{1}{2}$ で、そこから増えていくのだから、すべての $n$ で $b_{n} \geq \frac{1}{2}$ 。

$b_{n} \geq \frac{1}{2}$ を直接示そうとすると、仮定した $\frac{1}{2}$ から先へ進めません。「増えていく」という強い性質のほうが、かえって示しやすくなります。

補足：番号のとり方を変える

帰納法を回す番号は、 $n$ そのものでなくてもかまいません。 $n$ 個の正の数の相加平均が相乗平均以上であることを、 $n = 2^{m}$ の場合に $m$ について回した例があります^[2]。

$m = 1$ 、つまり $n = 2$ のときは、両辺を 2 乗して整理すると $(a - b)^{2} \geq 0$ に落ちる。

$n = 2^{m}$ で成り立つと仮定し、 $2^{m + 1}$ 個を前半と後半に $2^{m}$ 個ずつ分ける。前半の相加平均を $A$ 、相乗平均を $G_{1}$ 、後半をそれぞれ $B$ 、 $G_{2}$ とすると、仮定から $A \geq G_{1}$ 、 $B \geq G_{2}$ 。

$\frac{A + B}{2} \geq A B \geq G_{1} G_{2}$

右端は $2^{m + 1}$ 個全体の相乗平均です。よって $n = 2^{m + 1}$ でも成り立つ。

$2$ の累乗でない $n$ は、あとから別の議論で埋める。回す番号を選び直すと届く、という例です。

$2^{n} > n^{2}$ を帰納法で示すとき、出発点はどこにとりますか。

$n = 1$
$n = 3$
$n = 4$
$n = 5$

__RESULT__

$n = 3$ では $8 < 9$ 、 $n = 4$ では $16 = 16$ で、どちらも不等号が成り立ちません。 $n = 5$ の $32 > 25$ が最初に成り立つところです。

不等式の帰納法では、仮定から進んだ先と目標の差をどう埋めるかが決め手になります。追加の条件を足す、余った項を捨てる、示す命題を強くする、番号のとり方を変える。手は 1 つではありません。

出典

Jakob Bernoulli. Positiones arithmeticae de seriebus infinitis earumque summa finita. Basel, 1689. Universitätsbibliothek Basel の電子版.

Cauchy's proof of the inequality of arithmetic and geometric means. A.-L. Cauchy, Cours d'analyse, 1821, pp. 457-459 の対訳.

$2^n$ と $n^2$ は $n = 3$ で $8 < 9$ と逆転し、$n = 4$ で $16 = 16$ と並びます。だから出発点は $n = 5$。等式なら右辺にたどり着けば終わりますが、不等式では仮定から進んだ先が目標に届かないことがある。$k \ge 1$ という別の条件を足して押しこむ二段構え、ベルヌーイの不等式で $x \ge -1$ が効く場所、入れ子の平方根を上から押さえる形を順に見ます。$b_n \ge \dfrac{1}{2}$ のかわりに「増えていく」を示すと通る例まで。