【標準】数学的帰納法と倍数であることの証明

ここでは、整数の性質を、数学的帰納法を用いて示す方法を見ていきます。

倍数であることを示す問題

例題
n が自然数であるとき、 $4^n+2$ が3の倍数であることを示しなさい。

この例題を、数学的帰納法を用いて示してみましょう。

【基本】数学的帰納法で見た通り、「 $n=1$ のときに成り立つこと」と「 $n=k$ のときに成り立てば、 $n=k+1$ のときにも成り立つこと」の2つを示せばいいのでしたね。

(i) $n=1$ のとき

このとき、 $4^1+2=6$ なので、たしかに3の倍数です。 $n=1$ のときは「 $4^n+2$ が3の倍数である」ことがわかります。

(ii) 「 $4^k+2$ が3の倍数である」と仮定します。このとき、「 $4^{k+1}+2$ が3の倍数である」ことを示します。

$4^{k+1}+2$ を調べたいのですが、そのために $4^k+2$ がどう使えるかを考えてみましょう。これは、 $4^{k+1}+2$ の $4^{k+1}$ の部分を $4^k\times 4$ と分ければよさそうですね。こうすれば、「 $4^k+2$ が3の倍数」という仮定を使えそうです。

$4^k+2$ が3の倍数であることから、次を満たす整数 m が存在します。\[ 4^k+2=3m \]このことから、
\begin{eqnarray}
4^{k+1}+2
&=&
4^k\times 4+2 \\[5pt] &=&
(3m-2)\times 4+2 \\[5pt] &=&
12m-6 \\[5pt] &=&
3(4m-2) \\[5pt] \end{eqnarray}となります。 $4m-2$ は整数なので、「 $4^{k+1}+2$ が3の倍数である」ことが示せました。上の式変形を見てもわかる通り、 $n=k$ のときに成り立つという仮定を使うために $4^{k+1}$ の部分を $4^k\times 4$ と分解していることがポイントになっていることがわかりますね。

以上より、(i)(ii)から、数学的帰納法より、すべての自然数 n に対して「 $4^n+2$ が3の倍数であること」が示せました。

このように、数学的帰納法を使えば、直接示さなくても(示せなくても)、2つのステップに分けて示すことができます。

例題を直接示す

先ほどの例題は、数学的帰納法を用いなくても、直接示すこともできます。以下のように変形します。

\begin{eqnarray}
4^n+2
&=&
(4^n-1)+3 \\[5pt] &=&
(4-1)(4^{n-1}+4^{n-2}+\cdots+1)+3 \\[5pt] &=&
3\{(4^{n-1}+4^{n-2}+\cdots+1)+1\} \\[5pt] \end{eqnarray}最後の式は、3×整数となっているので、 $4^n+2$ は3の倍数であることがわかります。この式変形ができれば、数学的帰納法を使わなくても、直接示すことができます。

上の証明では、 $4^n-1$ を、「初項が $1$ で、公比が $4$ の等比数列の、初項から第 n 項までの和」に3を掛けたものだ、ととらえているわけですね。なので、この和が3の倍数になることがわかり、それに3を足してもやはり3の倍数だから、 $4^n+2$ は3の倍数だ、ということがわかるわけです。

数学的帰納法による証明と比べると、ずいぶんと短くはなりますが、式変形などは難しいですね。数学的帰納法による証明が使える場合は、数学的帰納法を使ったほうが易しくなることが多いです。

おわりに

ここでは、数学的帰納法を使って、 $4^n+2$ が3の倍数になることを示しました。2つのステップで示す方法に慣れていきましょう。