математическая индукция

Week induction

Метод доказательства, который использует инкрементальный подход:

1. мы выдвигаем утверждение, которое содержит формулу
2. мы проверяем формулу для базы (обычно для числа 1)
3. мы полагаем, что если n - верно, то пытаемся доказать, что n+1 тоже верно

Таким образом имея базу и инкрементальный подход, мы доказываем что общее утверждение верно.

Пример:

1. для суммы первых n натуральных чисел = n(n+1)/2.
2. n=1 → 1(1+1)/2 → 2/2 = 1
3. допусти для n=k всё выполняется, считаем для k+1 - 1+2+…k+k+1 = k(k+1)/2 + (k+1) = (k+1)(k+1+1)/2

Strong induction

Отличается от слабой индукции тем, что нам нужно взять более широкую базу.

1. Берём числа l >= m, такие что P(m), P(m+1) .. P(l) - истина
2. Тогда для любого n > l, надо доказать что P(m) .. P(n) ⇒ P(n+1)

Для примера можно доказать, что число Фибоначи всегда меньше 2^n.

Что дальше

context:: математика problem:: методы математических доказательств

Источники

• https://ncatlab.org/nlab/show/induction

Как улучшить

• [ ]