数学的帰納法

自然数に関する主張 $P(n)$ を示す手法。

1. 基底 — $P(1)$ が成り立つ
2. 帰納段階 — $P(k)\Rightarrow P(k+1)$

この 2 つから、すべての $n$ について $P(n)$ が言える。

ドミノの比喩#

最初のドミノが倒れ（基底）、 どのドミノも次を倒す（帰納段階）なら、 すべて倒れる。

強い帰納法#

$P(1),\dots ,P(k)$ すべてを仮定して $P(k+1)$ を示す形。 分割統治のアルゴリズムの正しさを示すときに使う （半分のサイズの問題について仮定する）。

何に使うか#

アルゴリズムの正しさの証明が主な用途。

• ループ不変条件 — 各反復で保たれる性質を帰納法で示す
• 再帰関数の正当性 — 再帰の構造がそのまま帰納法の構造
• 計算量の漸化式を解く

抽象構文木のような 再帰的なデータ構造に対しては、 構造帰納法という形で一般化される。

参考文献#

• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
• Thomas H. Cormen et al. Introduction to Algorithms, 4th ed. MIT Press, 2022. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/