数学的帰納法(指数と2乗の不等式)

方針

解答

⓪ 発想 — どう考え始めるか。 「$n\ge 5$ のすべてで $2^n>n^2$」という主張は、数学的帰納法の出番。

カギは $n=k$ の仮定 $2^k>k^2$ を、$n=k+1$ の $2^{k+1}>(k+1{)}^2$ につなぐこと。

$2^{k+1}=2\cdot 2^k$ に仮定を使えば $2^{k+1}>2k^2$ まで進める。あとは $2k^2\ge (k+1{)}^2$ が言えれば、間に挟んで目標に届く。

だから「$2k^2$ と $(k+1{)}^2$ の大小」という補助の不等式を先に用意しておく。

① 出発点。 $n=5$ のとき $2^5=32$、$5^2=25$ で $32>25$。成立。

② 仮定と橋渡しの準備。 $n=k$($k\ge 5$)で $2^k>k^2$ が成り立つと仮定する。まず補助的に、$k\ge 3$ のとき $2k^2\ge (k+1{)}^2$ を示す。差をとると

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

$k\ge 3$ なら $(k-1{)}^2\ge 4>2$ なので $2k^2-(k+1{)}^2>0$、すなわち $2k^2>(k+1{)}^2$。

③ $n=k+1$ を導く。 仮定より $2^{k+1}=2\cdot 2^k>2\cdot k^2=2k^2$。さらに②($k\ge 5\ge 3$)より $2k^2>(k+1{)}^2$。よって

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

$n=k+1$ でも成立。

④ 結論。 (i)(ii) より、$n\ge 5$ のすべての自然数 $n$ で $2^n>n^2$。(証明終)

まとめ:指数 vs 多項式の不等式は帰納法で、$2^{k+1}=2\cdot 2^k$ に仮定を使い、$2k^2$ を経由して $(k+1{)}^2$ に橋渡し。$2k^2>(k+1{)}^2$($k\ge 3$)を補助的に示すのが要。$n=4$ では $16=16$ と等号で、$n\ge 5$ が条件になっている。

発展 — 一歩先へ。 指数関数は、どんな多項式もいずれ追い抜く。$2^n$ と $n^2$ の場合、$n=2$ で $4=4$、$n=4$ で $16=16$ と $2$ 度並び、$n\ge 5$ で $2^n$ が勝ち続ける。

境界の $n=4$ で等号になるからこそ、条件が $n\ge 5$ になっている。$n=3$ では $8<9$ とまだ多項式が勝つ点にも注意。

一般に $a>1$ なら $\frac{a^n}{n^k}\to \infty$。対数をとると $n\log a-k\log n\to \infty$ からも分かる。指数の伸びは多項式より一段速い。

別解

別解 — 比 $\frac{2^n}{n^2}$ が増えることを示す(得意な人向けの視点)。 補助不等式を毎回作る代わりに、比の増減で一気に片づける。

$r_n=\frac{2^n}{n^2}$ とおくと

$$\frac{r_{n+1}}{r_n}=\frac{2^{n+1}}{(n+1{)}^2}\cdot \frac{n^2}{2^n}=\frac{2}{{\left(1+\frac{1}{n}\right)}^2}.$$

$n\ge 3$ なら $1+\frac{1}{n}\le \frac{4}{3}$ で ${\left(1+\frac{1}{n}\right)}^2\le \frac{16}{9}<2$。よって $\frac{r_{n+1}}{r_n}>1$、つまり $r_n$ は $n\ge 3$ で増え続ける。

出発点は $r_5=\frac{32}{25}>1$。増加数列だから $n\ge 5$ では $r_n\ge r_5>1$、すなわち $2^n>n^2$。

帰納法の橋渡しと本質は同じで、${\left(1+\frac{1}{n}\right)}^2<2$ は $2k^2>(k+1{)}^2$ と同じ主張。比の単調性で見ると、なぜ一度勝てば勝ち続けるのかが直感的につかめる。