Введение

Форма математического доказательства

Математическая индукция – это метод доказательства того, что утверждение истинно для каждого натурального числа, то есть, что бесконечное множество случаев выполняются. Это достигается путём доказательства простого случая, а затем демонстрации того, что если мы предполагаем истинность утверждения для данного случая, то оно также истинно и для следующего. Неформальные метафоры помогают объяснить эту технику, например, падающие костяшки домино или подъём по лестнице: текст=Математическая индукция доказывает, что мы можем подняться на любую высоту по лестнице, доказывая, что мы можем взобраться на нижнюю ступеньку (базис) и что с каждой ступеньки мы можем подняться на следующую (шаг). |источник=Конкретная математика, страница 3, поля. Доказательство индукцией состоит из двух случаев. Первый, базовый случай, доказывает утверждение для без предположения о знании других случаев. Второй случай, шаг индукции, доказывает, что если утверждение верно для любого заданного случая , то оно должно быть верно и для следующего случая. Эти два шага устанавливают истинность утверждения для каждого натурального числа. Базовый случай не обязательно начинается с , но часто начинается с , и, возможно, с любого фиксированного натурального числа , устанавливая истинность утверждения для всех натуральных чисел. Метод может быть расширен для доказательства утверждений о более общих хорошо обоснованных структурах, таких как деревья; это обобщение, известное как структурная индукция, используется в математической логике и информатике. Математическая индукция в этом расширенном смысле тесно связана с рекурсией. Математическая индукция – это правило вывода, используемое в формальных доказательствах, и является основой большинства доказательств корректности компьютерных программ. Несмотря на своё название, математическая индукция принципиально отличается от индуктивного рассуждения, используемого в философии, где рассмотрение множества случаев приводит к вероятностному заключению. Математический метод рассматривает бесконечное множество случаев для доказательства общего утверждения, но делает это посредством конечной цепочки дедуктивных рассуждений, включающей переменную , которая может принимать бесконечное количество значений. Результатом является строгое доказательство утверждения, а не утверждение о его вероятности.

Пример: формирование сумм в долларах по монетам

Предположим, что имеется бесконечный запас монет номиналом 4 и 5 долларов. Индукция может быть использована для доказательства того, что любую сумму в долларах, большую или равную 12, можно составить комбинацией таких монет. Пусть S(k) обозначает утверждение "k долларов можно составить комбинацией монет номиналом 4 и 5 долларов". Доказательство того, что S(k) верно для всех k ≥ 12, можно осуществить индукцией по k следующим образом:

Базовый случай: Показать, что S(k) верно для k = 12, просто: возьмите три монеты по 4 доллара. Шаг индукции: Предполагая, что S(k) верно для некоторого k ≥ 12 (гипотеза индукции), докажем, что S(k + 1) также верно. Предположим, что S(k) верно для некоторого произвольного k ≥ 12. Если существует решение для k долларов, включающее хотя бы одну монету в 4 доллара, замените её монетой в 5 долларов, чтобы получить k + 1 доллар. В противном случае, если используются только монеты в 5 долларов, k должно быть кратно 5 и, следовательно, не меньше 15; но тогда мы можем заменить три монеты по 5 долларов на четыре монеты по 4 доллара, чтобы получить k + 1 доллар. В каждом случае S(k + 1) верно. Следовательно, по принципу математической индукции, S(k) верно для всех k ≥ 12, и доказательство завершено. В этом примере, хотя S(k) также верно для , вышеприведенное доказательство нельзя изменить, чтобы заменить минимальную сумму в 12 долларов на любое меньшее значение m. Для m = 11 базовый случай фактически неверен; для m = 10 второй случай на шаге индукции (замена трех монет по 5 долларов на четыре монеты по 4 доллара) не сработает; не говоря уже о еще меньших значениях m.

Индукция на более чем одном счетчике

Иногда бывает полезно доказать утверждение, касающееся двух натуральных чисел, n и m, посредством итеративного применения метода математической индукции. А именно, доказывается базовый случай и шаг индукции для n, а в каждом из этих случаев – базовый случай и шаг индукции для m. Например, это можно увидеть в доказательстве коммутативности сложения натуральных чисел. Возможны и более сложные рассуждения, включающие три или более переменных.

Бесконечный спуск

Метод бесконечного спуска — это разновидность математической индукции, использованная Пьером де Ферма. Он применяется для доказательства ложности утверждения Q(n) для всех натуральных чисел n. Традиционная форма метода заключается в том, чтобы показать, что если Q(n) истинно для некоторого натурального числа n, то оно также истинно для некоторого строго меньшего натурального числа m. Поскольку бесконечной убывающей последовательности натуральных чисел не существует, такая ситуация невозможна, что, посредством доказательства от противного, демонстрирует ложность Q(n) для любого n.

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

Полная (сильная) индукция

Другой вариант, называемый полной индукцией, индукцией по ходу значений или сильной индукцией (в отличие от которой основная форма индукции иногда известна как слабая индукция), упрощает доказательство шага индукции, используя более сильную гипотезу: доказывается утверждение при предположении, что оно верно для всех натуральных чисел, меньших чем ; в отличие от этого, основная форма предполагает только, что . Название "сильная индукция" не означает, что этот метод может доказать больше, чем "слабая индукция", а лишь указывает на более сильную гипотезу, используемую на шаге индукции. Фактически, можно показать, что эти два метода на самом деле эквивалентны, как объясняется ниже. В этой форме полной индукции все равно необходимо доказать базовый случай, , и может даже потребоваться доказать дополнительные базовые случаи, такие как , прежде чем общий аргумент станет применимым, как в примере с числами Фибоначчи, приведенном ниже. Хотя описанная форма требует доказательства базового случая, это не требуется, если можно доказать (предполагая для всех меньших) для всех . Это частный случай трансфинитной индукции, описанной ниже, хотя он больше не эквивалентен обычной индукции. В этой форме базовый случай включается в случай , где доказывается без каких-либо других предположений; этот случай может потребоваться рассматривать отдельно, но иногда тот же аргумент применим и к , и к , что делает доказательство проще и элегантнее. Однако при использовании этого метода важно убедиться, что доказательство не предполагает неявно, что , например, говоря "выберем произвольное ", или предполагая, что множество из m элементов содержит элемент.

Эквивалентность обычной индукции

Полная индукция эквивалентна обычной математической индукции, как описано выше, в том смысле, что доказательство одним методом может быть преобразовано в доказательство другим. Предположим, существует доказательство утверждения P(n) полной индукцией. Тогда это доказательство можно преобразовать в обычное доказательство индукции, предположив более сильную индуктивную гипотезу. Пусть утверждение "P(k) истинно для всех k таких, что k ≤ n" является индуктивной гипотезой для обычной индукции. Тогда мы можем показать P(n) и, при условии P(n), показать, что P(n+1) истинно.

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

Пример: Числа Фибоначчи

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

где — n-е число Фибоначчи, а (золотое сечение) и — корни многочлена Используя тот факт, что для каждого , данное тождество можно проверить прямым вычислением для , если предположить, что оно уже верно для обоих и Для завершения доказательства тождество необходимо проверить в двух базовых случаях: и .

Пример: разделение на простые множители

Другое доказательство полной индукцией использует гипотезу о том, что утверждение верно для всех меньших чисел, рассмотренных более тщательно. Рассмотрим утверждение, что "каждое натуральное число, большее 1, является произведением (одного или нескольких) простых чисел", что является частью "существования" в фундаментальной теореме арифметики. Для доказательства шага индукции, гипотеза индукции заключается в том, что для заданного числа утверждение верно для всех меньших чисел. Если число *n* простое, то оно, безусловно, является произведением простых чисел, а если нет, то по определению оно является произведением: *n = a * b*, где ни один из множителей не равен 1; следовательно, ни один из них не равен *n*, и, таким образом, оба больше 1 и меньше *n*. Теперь гипотеза индукции применима к *a* и *b*, поэтому каждое из них является произведением простых чисел. Таким образом, *n* является произведением произведений простых чисел, и, следовательно, по сути, является произведением простых чисел.

Пример: пересмотренные суммы в долларах

Мы постараемся доказать тот же пример, что и выше, на этот раз с помощью сильной индукции. Утверждение остаётся прежним:

Однако, структура и предположения доказательства будут немного отличаться, начиная с расширенного базисного случая. Доказательство. Базисный случай: Покажем, что выполняется для
Базисный случай выполняется. Индуктивный шаг: Предположим, что для некоторого выполняется для всех с Докажем, что выполняется. Выберем и заметим, что выполняется, согласно индуктивной гипотезе. То есть, сумма может быть сформирована некоторой комбинацией монет номиналом и долларов. Затем, просто добавив монету в один доллар к этой комбинации, получим сумму, то есть выполняется. Q.E.D.

Индукция вперед-назад

Иногда удобнее рассуждать от обратного, доказывая утверждение для *n*, предполагая его справедливость для *n+1*. Однако, доказательства справедливости утверждения для какого-либо одного числа недостаточно для установления базового случая; вместо этого необходимо доказать утверждение для бесконечного подмножества натуральных чисел. Например, Огюстен Луи Коши впервые использовал прямую (обычную) индукцию для доказательства неравенства арифметического и геометрического сред для всех степеней 2, а затем использовал обратную индукцию, чтобы показать его справедливость для всех натуральных чисел.

Пример ошибки в этапе индукции

Шаг индукции должен быть доказан для всех значений n. Чтобы проиллюстрировать это, Джоэл Э. Коэн предложил следующий аргумент, который якобы доказывает математической индукцией, что все лошади одного цвета:

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

Введение

(гл. 8.) (Раздел 1.2.1: Математическая индукция, с. 11–21.) (Раздел 3.8: Трансфинитная индукция, с. 28–29.)

История

Перепечатано (CP 3.252–288), (W 4:299–309)