数学的帰納法

数学的帰納法とは
ある性質 P が全ての自然数 n で成立する事を示す証明形式
数学的帰納法による証明
n=0 の時に P(n) が成立する事を示す
この部分はプログラミング上では重要(終了条件問題)
n=k の時に P(n) が成立する事を利用し、n=k+1 の場合も成立する事を示す
P を証明するのに P を使っている所がミソ(自然数の構造)
関数定義の場合は、この部分が「再帰的定義」の部分
無限の数の命題をたった二つの記述で示せる強力な手段
P(n) の形の命題は n が自然数なので無限個存在する
「無限を有限にする」(「繰り返し」を繰り返しを使わず表現する)仕組
帰納法の例(全ての自然数は偶数か奇数である)
帰納法による証明
n=0) 0 は偶数なので、「偶数か奇数」は正しい
n=k+1) 帰納法の仮定より k は偶数か奇数である
n=k が偶数の時は、n=k+1 は奇数になる/ n=k が奇数の時は、n=k+1 は偶数になる
k が偶数でも奇数でも k+1 は奇数か偶数になる。すなわち、n=k+1 の時も n は奇数か偶数である