数学的帰納法の原理を発見したのは、哲学者パスカルである。パスカルは算術三角形の理論に関連して、1654年頃に数学的帰納法を初めて自覚的に使用した。パスカルの著述『パンセ』にも、数学的帰納法の持つ回帰的特質を踏まえて始めて理解できると思われる、内容が記述されている。自然数に関する1つの命題を証明したとする。このとき、与えられた命題を成立させる自然数の集合をSとする。S=N(自然数全体の集合)ならば、この命題はすべての自然数に対して真である。S=φ(空集合)ならば、この命題は偽である。それでは、S=Nとなるためには、Sはどのような条件を満たさなければならないのだろうか。この条件を与えるのが、次の原理である。自然数のある集合Sが、次の2つの条件を満たすとする。(1)1∈S(2)k∈Sならば、k+1∈Sこのとき、S=Nとなる。自然数全体の集合Nのある部分集合Sが与えられたとき、Sが1を含むこと、したがって空ではないこと。Sがもしkを含めば必ずk+1も含むこと。この2つの条件が満たされるならば、実はSはNに一致する。これが上の数学的帰納法の原理の内容である。形式を変えると次のように書ける。自然数nに関する命題P(n)が、次の2つの条件を満たすとする。(1)P(1)が成り立つ。(2)P(k)が成り立つならば、P(k+1)も成り立つ。このとき、すべての自然数nに対してP(n)が成り立つ。[補講]数学的帰納法の威力の秘密は、「P(k)ならばP(k+1)である」という簡単な条件の中に、3段論法の無限回の推論が集約されていることである。数学的帰納法の第1形式は、しばしば次の形式も用いられる(同値であるため、どちらを使ってもよい)。自然数nに関する命題P(n)が、次の2つの条件を満たすとする。(1)P(1)が成り立つ。(2)n=1,2,...,kのときP(n)が成り立つならば、n=k+1のときも成り立つ。整数nに関する命題P(n)を、自然数に対してではなく、ある整数(負や0でもよい)以上のnに対して証明したいことがある。この場合は、次の形式に変形した数学的帰納法を用いればよい。[定理]数学的帰納法の変形1整数nに関する命題P(n)が、次の2つの条件を満たすとする。(1)ある1つの整数mについて、P(m)が成り立つ。(2)P(k)が成り立つならば、P(k+1)も成り立つ。このとき、m以上のすべての整数nに対してP(n)が成り立つ。この変形1を用いた場合、nが正の方向に伸びているため、下限mが存在する。これに対して、0および正負の整数すべてに対して命題P(n)を示す場合は、次の形式を用いる。[定理]数学的帰納法の変形2整数nに関する命題P(n)が、次の2つの条件を満たすとする。(1)P(0)が成り立つ。(2)P(k)が成り立つならば、P(k±1)も成り立つ。このとき、すべての整数nに対してP(n)が成り立つ。パスカル(3320d)。