Многие утверждения говорят о всех натуральных n: «сумма первых n чётных чисел равна n(n + 1)». Проверить все n по очереди нельзя — их бесконечно много. Но можно поступить, как в игре «испорченный телефон»: если первый игрок получил слово и каждый передаёт его следующему, слово дойдёт до любого игрока.
Принцип математической индукции. Если утверждение A(n) верно при n = 1 и из того, что оно верно при каком-то n, следует, что оно верно при n + 1, то оно верно при всех натуральных n.
Метод доказательства
- База индукции: проверить утверждение при n = 1.
- Предположение индукции: допустить, что оно верно при произвольном натуральном n.
- Шаг индукции: опираясь на предположение, доказать его при n + 1.
Пример 1. 2 + 4 + … + 2n = n(n + 1). База: 2 = 1 · 2. Пусть S_n = n(n + 1). Тогда S₍n + 1) = S_n + 2(n + 1) = n(n + 1) + 2(n + 1) = (n + 1)(n + 2) — это и есть формула при n + 1.
Пример 2 (неравенство). 3ⁿ ≥ 1 + 2n при всех натуральных n. База: 3 ≥ 3. Шаг: 3⁽n + 1) = 3 · 3ⁿ ≥ 3(1 + 2n) = 3 + 6n > 1 + 2(n + 1).
Индукция не с единицы. Если утверждение верно лишь начиная с некоторого n₀, базу проверяют при n = n₀, а шаг доказывают для n ≥ n₀. Например, 2ⁿ > n² верно при n ≥ 5: 32 > 25; если 2ⁿ > n² и n ≥ 5, то 2⁽n + 1) > 2n² ≥ (n + 1)², так как n² ≥ 2n + 1 при n ≥ 3.
Главное в шаге — выразить утверждение для n + 1 через утверждение для n (например, S₍n + 1) = S_n + последнее слагаемое) и воспользоваться предположением. База без шага (и шаг без базы) ничего не доказывает.