数学的帰納法

ステップ1（$n=1$のとき）

$(\ast)$の左辺は、$n=1$のとき $1$ だけの和なので、

$(\text{左辺}) = 1$

$(\ast)$の右辺は、$n=1$を代入して、

$(\text{右辺}) = \frac{1\times(1+1)}{2} = \frac{2}{2}=1$

左辺と右辺が一致するので、$n=1$のとき $(\ast)$ は成り立ちます。

ステップ2（$n=k$のとき成り立つと仮定して、$n=k+1$のときを示す）

$n=k$（$k$は自然数）のとき $(\ast)$ が成り立つと仮定します。つまり、

$1+2+3+\cdots+k = \frac{k(k+1)}{2} \quad \cdots (\text{仮定})$

が成り立っているとします。この仮定のもとで、$n=k+1$のとき、つまり

$1+2+3+\cdots+k+(k+1) = \frac{(k+1)(k+2)}{2}$

が成り立つことを示したいです。左辺を考えます。左辺は「$1$から$k$までの和」に、さらに $(k+1)$ を足したものです。$1$から$k$までの和は、帰納法の仮定によって $\dfrac{k(k+1)}{2}$ だと分かっているので、それを使って置き換えます。

$1+2+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1)$

右辺を1つの分数にまとめるため、$(k+1)$ を $\dfrac{2(k+1)}{2}$ と書き直します。

$\frac{k(k+1)}{2}+(k+1) = \frac{k(k+1)}{2}+\frac{2(k+1)}{2} = \frac{k(k+1)+2(k+1)}{2}$

分子で $(k+1)$ が共通因数なので、くくり出します。

$k(k+1)+2(k+1) = (k+1)(k+2)$

したがって、

$1+2+\cdots+k+(k+1) = \frac{(k+1)(k+2)}{2}$

これは、示したかった「$n=k+1$のときの式」とまったく同じ形です。したがって、$n=k$のとき$(\ast)$が成り立つならば、$n=k+1$のときも$(\ast)$が成り立つことが示せました。

結論

ステップ1とステップ2が両方示せたので、数学的帰納法により、すべての自然数$n$について $(\ast)$、すなわち $1+2+\cdots+n=\dfrac{n(n+1)}{2}$ が成り立ちます。

ステップ1（$n=1$のとき）

$n=1$のとき、$4^1-1=4-1=3$ です。$3$は$3$で割り切れるので、$n=1$のとき命題は成り立ちます。

ステップ2（$n=k$のとき成り立つと仮定して、$n=k+1$のときを示す）

$n=k$（$k$は自然数）のとき、$4^k-1$ が $3$ で割り切れると仮定します。「$3$で割り切れる」ということは、ある整数 $m$ を使って、

$4^k - 1 = 3m \quad \cdots (\text{仮定})$

と書けるということです。この仮定のもとで、$n=k+1$のとき、つまり $4^{k+1}-1$ も $3$ で割り切れることを示したいです。

まず、仮定を使いやすくするために、$4^k = 3m+1$ と書き直しておきます（$(\text{仮定})$の両辺に$1$を足しただけです）。

$4^{k+1}-1$ を計算します。指数法則 $4^{k+1}=4\times4^k$ を使います。

$4^{k+1}-1 = 4\times4^k - 1$

ここに $4^k=3m+1$ を代入します。

$4^{k+1}-1 = 4(3m+1)-1$

かっこを展開します。

$4^{k+1}-1 = 12m+4-1 = 12m+3$

右辺を $3$ でくくります。

$4^{k+1}-1 = 3(4m+1)$

$4m+1$ は整数なので、$4^{k+1}-1$ は $3\times(\text{整数})$ の形になっています。つまり、$4^{k+1}-1$ は $3$ で割り切れます。

したがって、$n=k$のとき命題が成り立つならば、$n=k+1$のときも命題が成り立つことが示せました。

結論

ステップ1とステップ2が両方示せたので、数学的帰納法により、すべての自然数$n$について $4^n-1$ は $3$ で割り切れます。

この問題では、$n=1$ からではなく $n=5$ から証明をスタートする点に注意しましょう（実際、$n=1,2,3,4$ では $(\ast\ast)$ は成り立ちません。たとえば $n=4$ では $2^4=16$、$4^2=16$ で $16>16$ は成り立ちません）。

ステップ1（$n=5$のとき）

$n=5$のとき、左辺は $2^5=32$、右辺は $5^2=25$ です。

$32 > 25$

は正しいので、$n=5$のとき $(\ast\ast)$ は成り立ちます。

ステップ2（$n=k$（$k\geq5$）のとき成り立つと仮定して、$n=k+1$のときを示す）

$k\geq5$ であるとき、$2^k>k^2$ が成り立つと仮定します。この仮定のもとで、$2^{k+1}>(k+1)^2$ が成り立つことを示したいです。

まず、左辺の $2^{k+1}$ を、指数法則 $2^{k+1}=2\times2^k$ を使って書き直します。帰納法の仮定 $2^k>k^2$ の両辺を $2$倍すると、

$2\times2^k > 2\times k^2$

つまり、

$2^{k+1} > 2k^2 \quad \cdots ①$

が成り立ちます。したがって、あとは $2k^2 \geq (k+1)^2$ が言えれば、①と合わせて $2^{k+1}>2k^2\geq(k+1)^2$、つまり $2^{k+1}>(k+1)^2$ が示せます。そこで、$2k^2-(k+1)^2$ を計算してみます。

$(k+1)^2$ を展開します。

$(k+1)^2 = k^2+2k+1$

したがって、

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

この $k^2-2k-1$ が、$k\geq5$ のとき常に正の数（つまり$0$より大きい）であることを示します。$k^2-2k-1$ を、$k(k-2)-1$ と変形します。

$k^2-2k-1 = k(k-2)-1$

$k\geq5$ のとき、$k\geq5$ かつ $k-2\geq3$ なので、

$k(k-2) \geq 5\times3 = 15$

したがって、

$k^2-2k-1 = k(k-2)-1 \geq 15-1=14 > 0$

これで、$k\geq5$ のとき $2k^2-(k+1)^2=k^2-2k-1>0$、つまり $2k^2>(k+1)^2$ であることが示せました。これと①を合わせると、

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

したがって、$2^{k+1}>(k+1)^2$ が成り立ちます。つまり、$n=k$のとき$(\ast\ast)$が成り立つならば、$n=k+1$のときも$(\ast\ast)$が成り立つことが示せました。

結論

ステップ1とステップ2が両方示せたので、数学的帰納法により、$5$以上のすべての自然数$n$について $2^n>n^2$ が成り立ちます。

$n=1$のとき両辺とも $1$ で成立。$n=k$で成立すると仮定し、両辺に $(k+1)^2$ を足して右辺を通分・因数分解すると $\dfrac{(k+1)(k+2)(2k+3)}{6}$ となり、$n=k+1$の場合の式と一致する。よってすべての自然数で成立。

$n=1$のとき $5-1=4$ で成立。$5^k-1=4m$ と仮定すると、$5^{k+1}-1=5\times5^k-1=5(4m+1)-1=20m+4=4(5m+1)$ となり $4$で割り切れる。よってすべての自然数で成立。

$n=1$のとき $3\geq3$ で成立。$3^k\geq2k+1$ と仮定すると、$3^{k+1}=3\times3^k\geq3(2k+1)=6k+3$。$6k+3\geq2(k+1)+1=2k+3$ は $4k\geq0$ より常に成立するので、$3^{k+1}\geq2(k+1)+1$ が言える。よってすべての自然数で成立。