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

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

概要

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

定義

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

n = 0のとき真である。

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

このとき

n = 0のとき真である。
n = 0のとき真であるので、n = 0+1 = 1のときも真である。
n = 1のとき真であるので、n = 1+1 = 2のときも真である。
n = 2のとき真であるので、n = 2+1 = 3のときも真である。
n = 3のとき真であｒ(ry

となるので、全ての自然数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を無限大に持って行った場合、つまり極限には適用されない。以下の数列は再帰的に定義されているため数学的帰納法が適用できるが、その極限はさまざまである。

例1
S[1]=1/2
S[n+1]=S[n]+(1/2)ⁿ⁺¹

例2
S[1]=0.1
S[n+1]=S[n]+0.1ⁿ⁺¹

例3
a[1]=1.5
a[n+1]=a[n]/2+1/a[n]

例1、例2、例3はいずれも有理数の数列である。数学的帰納法からすべての自然数nで各項は必ず有理数になり、自然数や無理数が現れる事はない。
しかし、各数列の収束する極限値は、それぞれ1（自然数）、1/9（有理数）、√2（無理数）である。有理数に有理数を何回足したり掛けたりしても有理数であることは変わらないが、無限回の演算を施すとその限りではなくなる。
つまり、数学的帰納法は基本的に有限の自然数で成り立つ論法なのである。ある対象に数学的帰納法が成り立つからと言って、その極限も同じ性質を持つとは言えない。そのため、極限とそれ以外の項の性質は全く独立に考察しなければならない。

ハゲ頭のパラドックス

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

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

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

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

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

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

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