Принцип математической индукции

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

Математическая индукция — метод доказательства утверждений вида «для всех натуральных n верно P(n)»: доказываем базу и переход от n к n+1.

Зачем нужна индукция

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

Принцип домино

Представь бесконечный ряд костяшек домино. Чтобы упали все, достаточно двух вещей:

База: первая костяшка упала.
Шаг: каждая падающая костяшка роняет следующую.

Если оба условия выполнены — упадут все, по цепочке. Математическая индукция работает ровно так. Чтобы доказать «P(n) верно для всех n ≥ 1»:

База индукции: проверяем P(1) (первая костяшка падает).
Предположение индукции: допускаем, что P(k) верно для некоторого k.
Шаг индукции: из P(k) выводим P(k+1) (падающая костяшка роняет следующую).

Если база и шаг доказаны — по принципу индукции P(n) верно для всех n. Ключевая идея: мы не доказываем каждое P(n) отдельно, мы доказываем механизм, который дотягивается до любого n.

Разбор: сумма первых n чисел

Докажем знаменитую формулу: 1 + 2 + ... + n = n(n+1)/2.

База (n=1): левая часть = 1, правая = 1·2/2 = 1. Совпадает. Костяшка упала.

Предположение: пусть для некоторого k верно 1 + 2 + ... + k = k(k+1)/2.

Шаг: докажем формулу для k+1. Берём сумму до k+1 и используем предположение для первых k слагаемых:

1 + ... + k + (k+1) = k(k+1)/2 + (k+1) — подставили предположение.
Вынесем (k+1): (k+1)·(k/2 + 1) = (k+1)·(k+2)/2.
А это и есть формула для k+1: (k+1)((k+1)+1)/2.

База и шаг доказаны — формула верна для всех n. Обрати внимание на сердце метода: в шаге мы воспользовались предположением (заменили длинную сумму на короткую формулу). Без этого «опирания на предыдущее» индукция не работает.

Проверяем формулу машиной

Доказательство верно для всех n, но машина может убедить нас, проверив много значений напрямую.

# Проверяем 1+2+...+n == n(n+1)/2 для всех n от 1 до 1000
def check(N):
    return all(sum(range(1, n + 1)) == n * (n + 1) // 2
               for n in range(1, N + 1))

print("Формула суммы верна для n = 1..1000:", check(1000))

# Заодно проверим формулу суммы квадратов: 1²+...+n² = n(n+1)(2n+1)/6
def check_squares(N):
    return all(sum(i * i for i in range(1, n + 1))
               == n * (n + 1) * (2 * n + 1) // 6
               for n in range(1, N + 1))

print("Формула суммы квадратов верна для n = 1..1000:", check_squares(1000))

Вывод:

Формула суммы верна для n = 1..1000: True
Формула суммы квадратов верна для n = 1..1000: True

Машина сверила прямой подсчёт суммы с формулой для тысячи значений n — и нигде расхождения. Это отличная страховка: если бы в доказательстве была арифметическая ошибка, проверка её бы почти наверняка поймала. Но помни: True для n до 1000 — не доказательство для всех n. Доказывает именно индукция; код лишь проверяет.

Сильная индукция

Иногда в шаге одного предыдущего значения мало — нужно опираться на все предыдущие. Это сильная (полная) индукция: предполагаем, что P(m) верно для всех m от базы до k, и из этого выводим P(k+1). Классический пример — доказательство, что любое число ≥ 2 раскладывается на простые множители: чтобы разложить n, мы используем разложения его делителей, которые меньше n. Обычная и сильная индукция равносильны по силе, но сильная иногда удобнее.

Ещё один классический пример: сумма нечётных чисел

Докажем индукцией удивительно красивый факт: сумма первых n нечётных чисел равна n². То есть 1 = 1², 1+3 = 2², 1+3+5 = 3², и так далее.

База (n=1): сумма равна 1 = 1². Верно. Шаг: пусть 1+3+...+(2k−1) = k². Добавим следующее нечётное число 2k+1: получим k² + (2k+1) = k² + 2k + 1 = (k+1)² — ровно квадрат следующего числа. Шаг доказан, значит формула верна для всех n. Проверим машиной.

def check(N):
    # сумма первых n нечётных = 1 + 3 + ... + (2n-1)
    return all(sum(range(1, 2 * n, 2)) == n * n for n in range(1, N + 1))

print("Сумма нечётных = n² для n = 1..500:", check(500))
for n in range(1, 6):
    odds = list(range(1, 2 * n, 2))
    print(f"n={n}: сумма {odds} = {sum(odds)} = {n}² = {n * n}")

Вывод:

Сумма нечётных = n² для n = 1..500: True
n=1: сумма [1] = 1 = 1² = 1
n=2: сумма [1, 3] = 4 = 2² = 4
n=3: сумма [1, 3, 5] = 9 = 3² = 9
n=4: сумма [1, 3, 5, 7] = 16 = 4² = 16
n=5: сумма [1, 3, 5, 7, 9] = 25 = 5² = 25

Есть и наглядное «доказательство без слов»: квадрат n×n можно разрезать на «уголки» (Г-образные слои) размером 1, 3, 5, ..., (2n−1) клеток. Сумма уголков — это весь квадрат, то есть n². Индукция и геометрия пришли к одному ответу — так часто бывает в дискретной математике.

Типичные ошибки

Забыть базу. Без базы «шаг» доказывает пустоту: костяшки роняют друг друга, но первую никто не толкнул. Известный «парадокс»: «все лошади одной масти» — ложное утверждение, которое ломается именно на стыке базы и шага.
Не использовать предположение в шаге. Если в переходе от k к k+1 вы не опёрлись на P(k), это не индукция, а что-то другое (и, скорее всего, неверное).
Считать проверку примеров доказательством. Проверка для n = 1..100 — не доказательство. Гипотеза Эйлера и другие знаменитые «почти-теоремы» рушились на огромных числах.

Итог

Индукция доказывает «P(n) для всех n» через базу и шаг (принцип домино).
В шаге обязательно опираемся на предположение P(k) — это сердце метода.
Сильная индукция опирается сразу на все предыдущие значения.
Индукция — основа доказательства корректности циклов и рекурсии в программировании.