第 5 章数学的帰納法

数学的帰納法 (induction) は全ての非負整数で何らかの性質が成り立つことを証明するための強力な手法である。離散数学と情報科学で数学的帰納法は中心的な役割を果たす。さらに言えば、数学的帰納法が使われることは離散数学の ── 連続でない対象を扱う数学の ── 最も際立った特徴である。本章では通常の数学的帰納法と強い数学的帰納法 (strong induction) の二種類を紹介し、それらが正しい理由と証明で使う方法を説明する。また、ステップごとに進行する処理に関する命題の証明で有用な不変条件の原理 (invariant principle) と呼ばれる数学的帰納法の変種も紹介する。