Метод математической индукции

Метод математической индукции

Метод математической индукции — это способ доказательства утверждений, которые зависят от натурального числа n. Если утверждение верно для начального значения и из его верности для произвольного n следует верность для n + 1, то оно верно сразу для всех натуральных чисел, начиная с базового. Метод позволяет доказать бесконечно много утверждений одной короткой цепочкой рассуждений.

Принцип индукции часто сравнивают с падением домино. Если поставить костяшки в ряд так, что каждая, падая, роняет следующую, и толкнуть первую, то упадут все. База индукции — это «толчок первой костяшки», а шаг индукции — гарантия, что любая упавшая костяшка обязательно уронит соседнюю. Вместе они дают вывод обо всём бесконечном ряде.

Из каких шагов состоит доказательство

1. База индукции. Проверяют утверждение для наименьшего значения, обычно n = 1.
2. Предположение. Считают утверждение верным для некоторого n = k.
3. Шаг индукции. Доказывают, что тогда оно верно и для n = k + 1.

Разобранный пример

Докажем: 1 + 2 + 3 + ... + n = n(n + 1)/2.

База: при n = 1 слева 1, справа 1·2/2 = 1 — верно.

Предположение: 1 + ... + k = k(k + 1)/2.

Шаг: добавим k + 1: k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2.

Это и есть формула при n = k + 1. Значит утверждение верно для всех натуральных n.

Особенно важно понимать роль каждого шага. Без базы вся цепочка повисает в воздухе: даже если переход верен, нет первой «упавшей костяшки». Без шага индукции, наоборот, проверка отдельных значений ничего не доказывает для всех чисел. Поэтому оба шага обязательны, и пропуск любого из них делает доказательство неполным.

Частые ошибки. Пропускают проверку базы. Подменяют шаг индукции простой подстановкой нескольких чисел. Не используют предположение при переходе, хотя именно оно и есть ключ к доказательству. Считают, что проверка десяти или ста случаев заменяет общее доказательство.

Где применяется

• Формулы сумм последовательностей и прогрессий.
• Доказательство делимости выражений на заданное число.
• Неравенства, зависящие от натурального n.

Иногда базу проверяют не при n = 1, а при другом начальном значении — например, при n = 0 или n = 2, если утверждение сформулировано именно для таких чисел. Тогда вывод метода тоже относится только к числам, начиная с этой базы. Важно лишь, чтобы база совпадала с тем наименьшим числом, для которого утверждение должно быть верным.

Метод индукции — это не способ догадаться о формуле, а способ строго её доказать. Сначала формулу часто угадывают, рассматривая несколько первых случаев, а уже затем подтверждают индукцией. Поэтому метод обычно идёт в паре с наблюдением закономерности: наблюдение подсказывает гипотезу, а индукция превращает её в доказанный факт.

Кратко о главном

• Метод доказывает утверждения для всех натуральных n.
• Сначала проверяют базу — наименьшее значение.
• Затем предполагают верность при n = k.
• В шаге доказывают переход к n = k + 1, опираясь на предположение.
• Без любого из шагов доказательство неполно.