数学的帰納法

数学的帰納法とは、自然数に関する命題を証明する方法のひとつである。

概要

「すべての」自然数に関する命題を示す際、nを任意の自然数として証明する方法があるが、すべてが簡単にいくとは限らない。1つずつ値を代入する方法をとると、自然数は無限個あるので有限回の手続きでは終わらない。一方、数学的帰納法を用いれば、有限回の手続きで終了し、かつ比較的容易に証明できる。このことから非常に有用性の高い証明法としてよく使われる。

定義

ある命題がすべての自然数nについて真であることを証明するには、次の2つが成り立つことを証明すれば十分である。

• n = 1のとき真である。
• n = kのとき真であるならば、n = k+1のときも真である。(kは任意の自然数)

ここのとき

1. n = 1のとき真である。
2. n = 1のとき真であるので、n = 1+1 = 2のときも真である。
3. n = 2のとき真であるので、n = 2+1 = 3のときも真である。
4. n = 3のとき真であるので、n = 3+1 = 4のときも真である。
5. (以下略

であるので、全ての自然数に対して真であることがわかる。0を自然数に含める場合は、n = 1の代わりにn = 0のとき真であることを示せばよい。

応用

n = 1, 2のときに真であることを証明して、n = k, k+1のときに真であるならばn = k+2のときにも真であることを示すことによっても、すべての自然数について真であることを証明できる。nが3つ以上の値に渡る場合でも同様のことが可能である。

例

• 「おっ、続き物の動画を発見したぞ。とりあえずパート1だけ見て寝よう」→1番目の動画を見る
• k番目の動画を見る→「初めはこれ見たら寝ようと思ってたけど、続きが気になるな。よし、次の見たら寝よう」→k+1番目の動画を見る

⇒最終回を見るまで寝れない

関連動画

関連項目

• 数学
• 数列
• 再帰
• 演繹
• 明日から本気出す