数学的帰納法
すうがくてききのうほう 1対1で対応proof by induction
名詞 ・話し言葉 別の言い方 mathematical induction
場面で変わる言い方
- induction proof
- 書き言葉・答案 MIT 6.042（離散数学）のテキストの言い方。Levin（4.5）も Induction Proof Structure と書く。
定義
n = 1 で成り立つことと、n = k で成り立てば n = k + 1 でも成り立つことを示して、すべての自然数 n で成り立つことを証明する方法。
A method of proving a statement for every positive integer n: show it for n = 1, then show that if it holds for n = k it holds for n = k + 1.
例文
話し言葉 Proof by induction has two parts: the base case and the inductive step. 数学的帰納法は 2 段階。基底段階と帰納段階。
書き言葉・答案 Use mathematical induction to prove that 1 + 2 + ⋯ + n = n(n + 1)/2 for every positive integer n. すべての正の整数 n について 1 + 2 + ⋯ + n = n(n + 1)/2 が成り立つことを、数学的帰納法で証明せよ。
よく使う言い方
- by induction on n
- n についての数学的帰納法により
言い間違えやすいところ
- 話し言葉はほとんどが MIT OCW 6.042（離散数学）。単に by induction と言うことが多い（用例コーパスでは話し言葉・書き言葉とも、ほとんどが MIT 6.042 のもの）。
- n = k + 1 を示す段は inductive step、仮定は induction hypothesis（inductive-hypothesis を参照）。