Математическая индукция
Математическая индукция — это метод математического доказательства . По сути, он используется для доказательства того, что утверждение P ( n ) выполняется для каждого натурального числа n = 0, 1, 2, 3, ... ; то есть общее утверждение представляет собой последовательность бесконечного числа случаев P (0), P (1), P (2), P (3), ... . Объяснить этот прием помогают неформальные метафоры, такие как падение костяшек домино или подъем по лестнице:
Математическая индукция доказывает, что мы можем подняться по лестнице так высоко, как нам нравится, доказывая, что мы можем подняться на нижнюю ступеньку ( базис ) и что с каждой ступеньки мы можем подняться на следующую ( ступеньку ).
Доказательство по индукции состоит из двух случаев. Первый, базовый случай (или базис ), доказывает утверждение для n = 0, не предполагая каких-либо знаний о других случаях. Второй случай, шаг индукции , доказывает, что если утверждение верно для любого данного случая n = k , то оно также должно выполняться для следующего случая n = k + 1. Эти два шага устанавливают, что утверждение верно для любого натурального числа n . Базовый случай не обязательно начинается с n = 0, но часто с n = 1 и, возможно, с любым фиксированным натуральным числом n = N , устанавливая истинность утверждения для всех натуральных чисел n ≥ N .
Метод может быть расширен для доказательства утверждений о более общих хорошо обоснованных структурах, таких как деревья ; это обобщение, известное как структурная индукция , используется в математической логике и информатике . Математическая индукция в этом расширенном смысле тесно связана с рекурсией . Математическая индукция — это правило вывода , используемое в формальных доказательствах и являющееся основой большинства доказательств корректности компьютерных программ. [3]
Хотя название может указывать на обратное, математическую индукцию не следует путать с индуктивными рассуждениями , используемыми в философии (см. Проблема индукции ). Математический метод исследует бесконечное множество случаев, чтобы доказать общее утверждение, но делает это с помощью конечной цепочки дедуктивных рассуждений , включающих переменную n , которая может принимать бесконечно много значений. [4]
В 370 г. до н.э. « Парменид » Платона мог содержать ранний пример неявного индуктивного доказательства. [5] Противоположный итеративный метод, счет в сторону уменьшения , а не вверх, встречается в парадоксе соритов , где утверждалось, что если 1 000 000 песчинок образуют кучу, и удаление одной песчинки из кучи оставляет ее кучей, то песчинка (или даже отсутствие песчинки) образует кучу. [6]
