МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ

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

«Большая часть великих идей современных математиков, если не все, получила свое начало в наблюдении». Дж. Сильвестр

На заре теории чисел математики открыли многие факты индуктивным путем: Л. Эйлер и К. Гаусс рассматривали подчас тысячи примеров, прежде чем подметить числовую закономерность и поверить в нее. Но одновременно они понимали, сколь обманчивыми могут быть гипотезы, прошедшие «конечную» проверку. Числа Ферма  оказались простыми при  но у  Эйлер обнаружил делитель. Числа Мерсенна , где  – простые числа, сами являются простыми при , но не при  (а потом вновь будут простыми при ). Лейбниц думал какое-то время, что  делится на , проверив это при . Но при  это не так.

Итак, для индуктивного перехода от утверждения, проверенного для конечного подмножества, к аналогичному утверждению для всего бесконечного множества необходимо доказательство. Но как осуществить проверку бесконечного числа случаев? Такой способ предложили Б. Паскаль и Я. Бернулли. Теперь он носит название метода математической индукции. Пусть некоторое свойство надо доказать для элементов последовательности . Тогда достаточно:

1) проверить это утверждение для  (этот шаг называется началом или базисом индукции);

2) в предположении, что утверждение справедливо для , надо доказать его справедливость для  (индуктивный переход).

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

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

Приведем несколько примеров. Пусть  - сумма первых  натуральных чисел. Надо доказать, что . При  имеем . Далее, если , то  - и теорема доказана. Другой пример:  - сумма нечетных чисел. Надо доказать, что . При  это верно. Если , то  - и индуктивный переход проведен.

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

Часто приходится доказывать по индукции утверждение, справедливое не для всех , а лишь для достаточно больших , т.е. для всех , больших некоторого заданного числа . Тогда в основании индукции лежит проверка для . Докажем, что имеет место неравенство  при . Нетрудно непосредственно убедиться, что при  оно справедливо. Чтобы сделать индуктивный переход, заметим, что при переходе от  и  к левой части прибавляется , а к правой – . Все будет доказано, если мы докажем справедливость вспомогательного неравенства  при . При  оно справедливо (проверяется непосредственно), а далее рассуждаем аналогично: при переходе от  и  к левой части добавляется , а к правой -  2000. Поскольку  при , доказательство окончено. Этот пример иллюстрирует одновременно важную ситуацию: индуктивное предположение, в свою очередь, иногда целесообразно доказывать по индукции. При этом возникает цепочка индуктивных доказательств, причем на каждом шагу получается все более простое утверждение.

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

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