不等式を数学的帰納法で示す｜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\ge 1$ で $2^n>n$ を示す。

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

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

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

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

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

例：2 の n 乗と n の 2 乗

$n\ge 5$ で $2^n>n^2$ を示します。

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

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

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

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

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

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

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

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

ベルヌーイの不等式

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

$$(1+x{)}^n\ge 1+nx$$

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

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

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

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

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

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

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

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

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

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

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

$n=1$ のとき $\sqrt{2}<2$。

$n=k$ で $a_k<2$ を仮定する。

$$a_{k+1}=\sqrt{2+a_k}<\sqrt{2+2}=2$$

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

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

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

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

$b_n=\frac{1}{n+1}+\frac{1}{n+2}+\cdots +\frac{1}{2n}$ について、$b_n\ge \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 つ増える。

$$\begin{array}{rl}{b}_{n+1}-b_n& =\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}\\ & =\frac{1}{2n+1}-\frac{1}{2n+2}\\ & >0\end{array}$$

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

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

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

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

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

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

$$\frac{A+B}{2}\ge \sqrt{AB}\ge \sqrt{G_1{G}_2}$$

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

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

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

出典