Индукция - это не про числа, а про сведение

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

Как думаешь, почему этого достаточно

Утверждение: сумма первых n нечётных чисел равна n². Проверим: 1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16. Четыре совпадения ничего не доказывают, это мы уже выяснили. А вот два факта - доказывают:

• при n = 1 сумма равна 1, и это 1²;
• если сумма первых n нечётных равна n², то сумма первых n+1 равна n² + (2n+1) = (n+1)².

Дальше рассуждение разворачивается само: верно для 1, значит верно для 2; верно для 2, значит для 3; и так до любого числа. Каждое конкретное n достигается за конечное число шагов, поэтому утверждение верно для всех сразу.

Схема

Математическая индукция доказывает утверждение P(n) для всех натуральных n двумя шагами:

• база: P верно для наименьшего значения;
• шаг: из P(n) следует P(n+1).

Разница между индукцией и проверкой примерами в том, что шаг проверяется один раз для произвольного n, а не для каждого. В этом и весь выигрыш: одна проверка вместо бесконечности.

Сильная индукция отличается предположением: в шаге разрешено пользоваться P(1), P(2), ..., P(n) целиком, а не только P(n). Она нужна почти всегда, когда рассуждение сводит задачу не к соседнему случаю, а к половине: чтобы доказать что-то про n, удобно опираться на n/2, а это не предшественник.

Разбор: индукция по структуре, а не по числу

Индукция не привязана к натуральным числам. Достаточно, чтобы объекты можно было разложить на меньшие и чтобы разложение не продолжалось бесконечно.

Утверждение: в двоичном дереве из n узлов ровно n - 1 ребро.

• База. Дерево из одного узла: рёбер ноль, и 1 - 1 = 0.
• Шаг. Пусть дерево имеет n > 1 узлов. У корня есть поддеревья; всего в них n - 1 узлов. По предположению непустое поддерево из p узлов содержит p - 1 ребро, а пустое - ноль рёбер при нуле узлов (формула p - 1 верна только для непустого - у пустого рёбер ноль, а не «минус одно»). Значит внутри поддеревьев рёбер на столько меньше n - 1, сколько поддеревьев непусто. Ровно столько рёбер добавляет корень - по одному к каждому непустому поддереву. Итого n - 1.

Это структурная индукция: разбор идёт по устройству объекта. Ею доказывается почти всё про деревья, списки и выражения, и ею же оправдывается рекурсия, которая обходит такие объекты.

Разбор: где индукция ломается

Классический ложный вывод: «все лошади одной масти». База: одна лошадь - очевидно, одной масти. Шаг: пусть верно для n; возьмём n+1 лошадей, уберём первую - оставшиеся n одной масти; уберём последнюю - оставшиеся n тоже одной масти; значит все n+1 одной масти.

Ошибка в шаге, и она ровно одна: при n = 1 два подмножества по одной лошади не пересекаются, и связать их нечем. Шаг верен для n ≥ 2, а база дана для n = 1 - цепочка рвётся на первом же звене.

Отсюда практическое правило: шаг проверяют на наименьшем значении, к которому его собираются применить, а не на удобном большом. В алгоритмах это ровно те случаи, где рекурсия ломается на пустом или одноэлементном входе.

Связь с инвариантом

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

Теперь сам

Докажи индукцией: у полного двоичного дерева высоты h ровно 2^(h+1) - 1 узлов. Полное дерево - такое, где у каждого узла либо два потомка, либо ни одного, и все листья на одном уровне; высота дерева из одного узла равна нулю.