述語論理 ⑥

Def.

Prop & Proof

数学的帰納法で示す。

1. 【基底】
   $n=1$のとき、
   $$ 1=\frac{1\cdot(1+1)}{2} $$
   より成り立つ。
   $ $
2. 【帰納法の仮定】
   任意の $k\ge 1$ を取り、
   $$ 1+2+\cdots+k=\frac{k(k+1)}{2} $$
   が成り立つと仮定する。
   $ $
3. 【帰納法の推論】
   このとき
   $$ \begin{align} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{k(k+1)+2(k+1)}{2}\\ &=\frac{(k+1)(k+2)}{2}\\ &=\frac{(k+1)((k+1)+1)}{2} \end{align} $$
   より、$n=k+1$でも成り立つ。
   $ $
4. 【帰結】
   以上より、任意の$n\in\mathbb{N}$について主張が成り立つ。
   $$ \Box$$

数学的帰納法により示す。

1. 【基底】
   $n=1$のとき、$2^1=2\ge 1+1=2$より成り立つ。
   $ $
2. 【帰納法の仮定】
   任意の $k\ge 1$ を取り、
   $$ 2^k\ge k+1 $$
   が成り立つと仮定する。
   $ $
3. 【帰納法の推論】
   このとき
   $$ 2^{k+1}=2\cdot 2^k $$
   であるから、帰納法の仮定 $2^k\ge k+1$ を用いると
   $$ 2^{k+1}=2\cdot 2^k \ge 2(k+1)\cdots① $$
   が従う。ここで
   $$ 2(k+1)-(k+2)=k\cdots➁ $$
   である事と $k\in\mathbb{N}$ であり $k\ge 1$ であるから、特に
   $$ k\ge 0\cdots➂ $$
   となる。したがって、➁と➂から
   $$ 2(k+1)-(k+2)\ge 0 $$
   より、
   $$ 2(k+1)\ge k+2\cdots④ $$
   が成り立つ。以上より、①と④から
   $$ 2^{k+1}\ge (k+1)+1 $$
   が従う。
   $ $
4. 【帰結】
   以上により、数学的帰納法から任意の$n\in\mathbb{N}$について
   $$ 2^n\ge n+1 $$
   が成り立つ。
   $$ \Box$$