Энциклопедический словарь юного математика

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

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

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

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

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

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

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

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

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

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

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

МАТЕМАТИЧЕСКАЯ ЛОГИКА