計算機科学のブログ

帰納的定義と証明技法指数と平方、べき乗、不等式、帰納法

本の表紙

情報系のための離散数学
 楽天ブックス
Yahoo!ショッピング
au PAY マーケット

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、章末問題の問3.6の解答を求めてみる。

2^{5} = 32 > 25 = 5^{2}

また、

\begin{array}{l} 2^{n} = 2 \cdot 2^{n - 1} > 2 \cdot {(n - 1)}^{2} \\ = 2 (n^{2} - 2 n + 1) \\ = n^{2} + (n^{2} - 4 n + 2) \\ = n^{2} + ({(n - 2)}^{2} - 2) \\ > n^{2} + {(5 - 2)}^{2} - 2 \\ = n^{2} + 9 - 2 \\ = n^{2} + 7 \\ > n^{2} \end{array}

よって帰納法により、4より大きい自然数nに対して、

2^{n} > n^{2}

が成り立つ。

（証明終）

コード、入出力結果(Wolfram Language, Jupyter)

Show[
    ListLinePlot[Table[2^n, {n, 1, 5}], PlotStyle -> Green],
    ListLinePlot[Table[n^2, {n, 1, 5}], PlotStyle -> Blue]
]

Output