数学的帰納法１
数学的帰納法
自然数 \(n\) を含んだ命題 \(P(n)\) が、すべての自然数 \(n\) について成り立つことを証明する方法として「数学的帰納法」がある。
１．\(n=1\) のとき、\(P(1)\) が成り立つことを示す。
２．\(n=k\) のとき、\(P(k)\)が成り立つと仮定し、
\(n=k+1\) のとき、\(P(k+1)\) が成り立つことを示す。
１.２より、すべての自然数 \(n\) について、命題 \(P(n)\) が成り立つ。
上のような論法を数学的帰納法といいます。
よく用いられる例えとして、ドミノ倒しがあります。
「\(n=1\) のとき、\(P(1)\) が成り立つ」とは、ドミノ倒しのスタートを倒したようなものです。
そして、「\(n=k\) のとき \(P(k)\) が成り立つならば、\(n=k+1\) のとき \(P(k+1)\) が成り立つ」とは、ドミノが次々と倒れていくことの保証です。
\(n=1\) で倒れたので、\(n=2\) も倒れます。
\(n=2\) で倒れたので、\(n=3\) も倒れます。
\(n=3\) で倒れたので、\(n=4\) も倒れます。
以下永久にこの論理は続くので、すべての自然数 \(n\) についてドミノが倒れます。
例題１
\(n\) を自然数とするとき、次の等式を証明しなさい。
\(1^2+2^2+3^2+\cdots+n^2\)\(= \displaystyle \frac{1}{6}n(n+1)(2n+1)\)
解説
\(2\) 乗の和の公式ですね。この公式がすべての自然数で成立することの証明です。
「すべての自然数で成立する」を証明するのは、数学的帰納法の出番です。
では行きましょう。
この等式を①とする。
１.\(n=1\) のとき
（左辺）\(=1\)、（右辺）\(=\displaystyle \frac{1}{6}\cdot 1 \cdot 2 \cdot 3=1\)
よって、①は成り立つ。
２.\(n=k\) のとき①が成り立つと仮定すると、
\(1^2+2^2+3^2+\cdots+k^2\)\(= \displaystyle \frac{1}{6}k(k+1)(2k+1)\)・・・②
もし成り立つのならば、②の等式が成り立つよね、という意味です。
そして、②が成り立つという仮定のもと、\(n=k+1\) のときに①式が成立することを示すことが目標です。
②式の両辺に \((k+1)^2\) を足すと、
\(1^2+2^2+3^2+\cdots+k^2+(k+1)^2\)\(= \displaystyle \frac{1}{6}k(k+1)(2k+1)+(k+1)^2\)
\(\displaystyle \frac{1}{6}(k+1)\{(k+1)+1\}\{2(k+1)+1\}\)
にもっていくことが目標です。これは、\(n=k+1\) のときの①式です。
\(\displaystyle \frac{1}{6}k(k+1)(2k+1)+(k+1)^2\)
\(=\displaystyle \frac{1}{6}(k+1)\{k(2k+1)+6(k+1)\}\)
\(=\displaystyle \frac{1}{6}(k+1)(2k^2+7k+6)\)
\(=\displaystyle \frac{1}{6}(k+1)(k+2)(2k+3)\)
\(=\displaystyle \frac{1}{6}(k+1)\{(k+1)+1\}\{2(k+1)+1\}\)
したがって、\(n=k+1\) のときも①は成り立つ。
１．２より、すべての自然数 \(n\) について、①が成り立つ。
公式の導出はできない
そもそも①式、\(1^2+2^2+3^2+\cdots+n^2= \displaystyle \frac{1}{6}n(n+1)(2n+1)\) はどうやって作られた式なのかは、この方法ではわかりません。
ただし、試行錯誤の末に①式が成り立つらしいぞ・・・と見つけたとして、
あらゆる \(n\) に使える公式として正しいだろうか？
という疑問を解消するために、この数学的帰納法は用いられます。
例題２
\(n\) を自然数とするとき、次の等式を証明しなさい。
\(1^2+3^2+5^2+\cdots+(2n-1)^2\)\(= \displaystyle \frac{1}{3}n(2n-1)(2n+1)\)
解説
この等式を①とする。
１.\(n=1\) のとき
（左辺）\(=1\)、（右辺）\(=\displaystyle \frac{1}{3}\cdot 1 \cdot (2\cdot1-1)(2 \cdot1+1)=1\)
よって、①は成り立つ。
２.\(n=k\) のとき①が成り立つと仮定すると、
\(1^2+3^2+5^2+\cdots+(2n-1)^2\)\(= \displaystyle \frac{1}{3}k(2k-1)(2k+1)\)・・・②
より、
\(1^2+3^2+\cdots+(2k-1)^2+\{2(k+1)-1\}^2\)\(= \displaystyle \frac{1}{3}k(2k-1)(2k+1)+\{2(k+1)-1\}^2\)
\(=\displaystyle \frac{1}{3}(2k+1)\{k(2k-1)+3(2k+1)\}\)
\(=\displaystyle \frac{1}{3}(2k+1)(2k^2-k+6k+3)\)
\(=\displaystyle \frac{1}{3}(2k+1)(2k^2+5k+3)\)
\(=\displaystyle \frac{1}{3}(2k+1)(2k+3)(k+1)\)
\(=\displaystyle \frac{1}{3}(k+1)\{2(k+1)-1\}\{2(k+1)+1\}\)
したがって、\(n=k+1\) のときも①は成り立つ。
１．２より、すべての自然数 \(n\) について、①が成り立つ。