Математическая индукция

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

На заре теории чисел математики открыли многие факты индуктивным путем: Л. Эйлер и К. Гаусс рассматривали подчас тысячи примеров, прежде чем подметить числовую закономерность и поверить в нее. Но одновременно они понимали, сколь обманчивыми могут быть гипотезы, прошедшие «конечную» проверку. Числа Ферма F_k = 2^2k + 1 оказались простыми при k = 0,1,2,3,4, но у F₅ Эйлер обнаружил делитель. Числа Мерсенна М_p = 2^p — 1, где р - простые числа, сами являются простыми при р = 2,3,5,7, но не при р = 11 (а потом вновь будут простыми при р = 13,17,19,...). Лейбниц думал какое-то время, что n^2k+1 - n делится на 2k + 1, проверив это при к = 1,2,3. Но при k = 4 это не так.

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

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

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

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

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

Приведем несколько примеров. Пусть а_n = 1 + 2 + ... + n - сумма первых п натуральных чисел. Надо доказать, что а_n = n(n + 1)/2. При n = 1 имеем а₁ = 1. Далее, если а_k = k(k + 1)/2, то а_k+1 = а_k + k + 1 = (k + 1)(k + 2)/2 - и теорема доказана. Другой пример: а_n = 1 + 3 + ... + (2n - 1) - сумма нечетных чисел. Надо доказать, что а_n = n². При n = 1 это верно. Если а_k = k², то а_k+1 = а_k + (2k + 1) = k² + 2к + 1 = (k + 1)² - и индуктивный переход проведен.

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

Часто приходится доказывать по индукции утверждение, справедливое не для всех т, а лишь для достаточно больших т, т.е. для всех т, больших некоторого заданного числа N. Тогда в основании индукции лежит проверка для a_N. Докажем, что имеет место неравенство n³ - 4 > 1000n² + 3n при n ≥ 2000. Нетрудно непосредственно убедиться, что при n = 2000 оно справедливо. Чтобы сделать индуктивный переход, заметим, что при переходе от k к k + 1 к левой части прибавляется Зk² + 3k + 1, а к правой - 2000k + 1003. Все будет доказано, если мы докажем справедливость вспомогательного неравенства Зk² + Зk + 1 ≥ 2000k + 1003 при k ≥ 2000. При k = 2000 оно справедливо (проверяется непосредственно), а далее рассуждаем аналогично: при переходе от k к k + 1 к левой части добавляется 6k + 6, а к правой - 2000. Поскольку 6k + 6 ≥ 2000 при k ≥ 2000, доказательство окончено. Этот пример иллюстрирует одновременно важную ситуацию: индуктивное предположение, в свою очередь, иногда целесообразно доказывать по индукции. При этом возникает цепочка индуктивных доказательств, причем на каждом шагу получается все более простое утверждение.

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

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