再帰的定義と数学的帰納法

再帰的定義
関数 f() を定義する本体に f() 自身を含める仕組み
「繰返し」を表現
最低一つの引数があり、引数の値が「小く」なり、「最小」で終了になるように定義
そうしないと、「無限ループ」になってしまう
数学的帰納法
任意の自然数 n に関する命題 P(n) を証明するための「枠組み」
次の「手順」で、「P(n) が、任意の自然数 n で成立する事」を示す
[Start Step] 「P(0) が成立」する事を示す
[Next Step] 「P(k) が成立」すれば、「P(k+1)が成立」する事を示す
上記の 2 つと「数学的帰納法の原理」から、「P(n) の成立」を示す
再帰的定義と数学的帰納法の関係
再帰的定義された関数の性質は、数学的帰納法で証明しやすい
再帰的定義には、[Start Step] と [Next Step] がそのまま書いてある
数学的帰納法の証明をする時に、その記述がそのまま利用できる
数学的帰納法で証明された性質を実現する再帰的定義された関数が作れる
帰納法の証明から、再帰的定義を作る事ができる
帰納法の証明の [Start Step] と [Next Step] を抜き出せばよい