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

Материал из Юнциклопедии
(перенаправлено с «МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ»)
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

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

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

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