【基本】数学的帰納法

ここでは、数学的帰納法を使った証明方法を見ていきます。すでに知っていることを、数学的帰納法を使って再度証明していきます。

【広告】

自然数の和をもう一度

【基本】和の公式(1からnまでの和)で見たように、自然数 n に対して、1から n までの和は\[ \frac{1}{2}n(n+1) \]で表すことができます。

なぜこれが成り立つかは、すでに上のリンク先で示しています(足す順番を逆にしたものと合わせる方法です)が、数学的帰納法を使った証明がどのようなものかを見るために、この公式をもう一度示してみます。

数学的帰納法とは、【導入】数学的帰納法でも紹介しましたが、次の2つを示す証明方法です。

  • $n=1$ のときに成り立つことを証明する
  • $n=k$ のときに成り立てば、 $n=k+1$ のときにも成り立つことを証明する

この2つを示すことで、1つ目の内容から $n=1$ のときに成り立つ、これと2つ目の内容から $n=2$ のときも成り立つ、さらにこれと2つ目の内容から $n=3$ のときも成り立つ、…というように次々と成り立つことがわかるので、すべての自然数で成り立つことが言える、という示し方なんですね。

それでは、実際にこの2つを示してみましょう。

【広告】

数学的帰納法のステップ1

数学的帰納法のステップ1は、「 $n=1$ のときに成り立つことを証明する」です。そのため、 $n=1$ のときに示す内容を考えましょう。

示したいことに $n=1$ を代入すると、次のようになります:「 $1$ から $1$ までの和は、 $\dfrac{1}{2}\cdot 1\cdot(1+1)$ で表すことができる」。これを示せば、ステップ1はOKです。

前半部分の「1から1までの和」というのは、もちろん1です。また、後半部分を計算すると
\begin{eqnarray}
\dfrac{1}{2}\cdot 1\cdot(1+1)
&=&
1
\end{eqnarray}となります。ということは、両方とも1なので、たしかに $n=1$ のときには成り立つことがわかります。

数学的帰納法のステップ2

数学的帰納法のステップ2は、「 $n=k$ のときに成り立てば、 $n=k+1$ のときにも成り立つことを証明する」です。

仮定は「 $n=k$ のときに成り立つ」ですね。具体的に書くと、「 $1$ から k までの和は、 $\dfrac{1}{2}k(k+1)$ で表すことができる」となります。

そして、結論、つまり、示したいことは「 $1$ から $k+1$ までの和は、 $\dfrac{1}{2}\cdot (k+1)\cdot\{(k+1)+1\}$ で表すことができる」となります。つまり、 $\dfrac{1}{2}(k+1)(k+2)$ で表すことができる、ということですね。これが示せれば、ステップ2が終了です。

結論に出てくる「 $1$ から $k+1$ までの和」に注目しましょう。仮定を利用すると、この和のうち、 $1$ から $k$ までの和は $\dfrac{1}{2}k(k+1)$ と書けるのでしたね。

このことから、「 $1$ から $k+1$ までの和」というのは、「 $\dfrac{1}{2}k(k+1)$ と $k+1$ の和」と言い換えることができます。仮定を使って、一部分を入れ替えただけです。

この式を計算すると
\begin{eqnarray}
& &
\dfrac{1}{2}k(k+1) +(k+1) \\[5pt] &=&
(k+1) \left(\dfrac{1}{2}k +1\right) \\[5pt] &=&
(k+1)\cdot \dfrac{k+2}{2} \\[5pt] &=&
\dfrac{1}{2}(k+1)(k+2) \\[5pt] \end{eqnarray}となります。よって、示したかったこと、「 $1$ から $k+1$ までの和は、 $\dfrac{1}{2}(k+1)(k+2)$ で表すことができる」が示せたわけです。

これでステップ2が完了です。

数学的帰納法のまとめ

こうして、ステップ1から「 $n=1$ に成り立つ」ことが示せて、ステップ2から「 $n=k$ で成り立てば $n=k+1$ でも成り立つ」ことが示せました。このため、この2つを組み合わせると、 $n=1,2,3,\cdots$ のときに成り立つことがわかります。よって、すべての自然数 n に対して、「1から n までの和は $\dfrac{1}{2}n(n+1)$ で表すことができる」ことが示せたことになります。

数学的帰納法を使った証明方法は、次のようになります。

数学的帰納法
すべての自然数 n について事柄 P が成り立つことを数学的帰納法を使って証明するには、次の2つを示す。
(1) $n=1$ のときに P が成り立つ。
(2) $n=k$ のときに P が成り立つなら、 $n=k+1$ のときも P が成り立つ。

この証明方法は、すべての自然数 n に対して成り立つことを直接示すことが難しい場合に役立つことが多いです。上の(1)(2)を示したほうが易しい場合は、数学的帰納法を使うようにしましょう。

おわりに

ここでは、すでに成り立つことがわかっている事柄を使って、数学的帰納法を使った証明方法がどのようになるかを見てきました。すべての自然数に成り立つことを直接示すことが難しい場合でも、数学的帰納法を使えば示せるようになることもあります。この証明方法の使い方に慣れていきましょう。