数学的帰納法とは (スウガクテキキノウホウとは) [単語記事]

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

概要

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

定義

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

n = 0のとき真である。

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

このとき

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

であるので、全ての自然数nに対して真であることがわかる。

応用

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

また、「n = 1で真であることを証明し、n ≤ kのときに真であるならばn = k+1のときにも真になることを示す」というパターンもある。

例

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

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

適用されない事例

ハゲ頭のパラドックス

数学的帰納法は、日常生活における事例には当てはまらないことがある。
有名な例は「すべての人間はハゲである」という理論の数学的帰納法による証明である。

髪の毛の本数をnとする。

n=0のとき、ハゲであることは自明である。

ハゲの人に髪の毛を1本足してもやっぱりハゲである。

⇒すべての人間はハゲである

このパラドックスが派生してしまう原因は主に2点ある。

「髪の毛が何本あればハゲなのか」というハゲの定義が作成されていないため。髪の毛が少なければもちろんハゲであるが、髪の毛の本数が多くても生え際が上の方に来ていればハゲと呼ばれるかもしれない。
「少量の増加程度ではその現象に大差はないだろう」という考えがあるため。この考えを採用してしまうと、数学的帰納法では「沢山の増加でも差はない」となり、大幅な増加において認識がずれてしまうことがある。