この用語はまだ監査を通っていません（未確認）。
累積帰納法
るいせききのうほう ／ 強帰納法 ／ 強い数学的帰納法 1対1で対応strong induction
名詞 ・話し言葉・書き言葉
式と読み方
P of 1 and dot dot dot and P of k implies P of k plus 1
定義
数学的帰納法の一種で、n = 1, 2, …, k のすべてで成り立つと仮定して、n = k + 1 でも成り立つことを示す証明法。直前の 1 つだけでなく、それより前のすべての場合を仮定に使える。
A form of induction in which you assume the statement holds for every case from the base case up to k, and use that to prove it for k + 1. It helps when the k + 1 case depends on cases earlier than k.
例文
話し言葉 To show every integer greater than one has a prime factorization, knowing just the case k isn't enough, so we'll use strong induction. 1 より大きいすべての整数が素因数分解できることを示すには、n = k の場合だけ仮定しても足りない。だから累積帰納法を使おう。
書き言葉・答案 Use strong induction to prove that every integer n ≥ 12 can be written as 4a + 5b for some nonnegative integers a and b. 累積帰納法を用いて、12 以上のすべての整数 n は、0 以上の整数 a, b を用いて 4a + 5b と表せることを証明せよ。
言い間違えやすいところ
- 数B の「n = k, k + 1 のとき成り立つと仮定して n = k + 2 を示す」形の帰納法は、strong induction の特別な場合にあたる。
- base case が 1 つでは足りないことがある。上の 4a + 5b の例では 12〜15 の 4 つを先に確かめる。
- 用例コーパスでは話し言葉はすべて MIT OCW、書き言葉はすべて MIT の講義ノート。Levin は 4.6 Strong Induction ほかで 33 件使う。