Доказательство по индукции

Большинство предло­жений теории чисел являются утверждениями о произвольном натуральном числе; например, теорема Лагранжа говорит о том, что каждое натуральное число есть сумма не более четырех квадратов. Как же доказать, что некоторое утверждение истин­но для любого натурального числа? Конечно, некоторые утвер­ждения непосредственно вытекают из законов арифметики; та­ковы, например, алгебраические тождества типа

(n+1)² = n² +2n+ 1.

Но более интересные и более арифметические по своей природе утверждения не столь просты.

Ясно, что мы никогда не докажем общего предложения, последовательно убеждаясь в его истинности для 1, 2, 3 и так далее, ибо нельзя перебрать бесконечного числа возможностей. Установив, что утверждение верно для любого числа, меньшего миллиона или миллиона миллионов, мы не приблизимся к до­казательству того, что оно верно всегда. (Иногда, правда, бывает, что некоторые предложения теории чисел, установленные путем вычислений для большого числа частных случаев, ока­зываются верными в довольно широкой области.)

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

Если это доказано, то из истинности нашего предложения для числа 1 следует, что оно верно для числа 2, из того, что оно верно для 1 и 2, вытекает, что оно верно для 3, и так далее до бесконечности. Это предложение будет поэтому верным для любого числа, если оно верно для числа 1.

В этом и состоит принцип доказательства по индукции, ко­торый относится к предложениям о том, что что-то верно для любого натурального числа. Чтобы применить этот принцип, необходимо доказать две вещи: во-первых, нужно доказать, что предложение верно для 1, а во-вторых, что если предложение верно для каждого из чисел 1, 2,..., n-1, меньших n, то оно верно и для числа n. Установив эти факты, мы заключаем, что доказываемое предложение верно для любого натурального числа.

Простой пример проиллюстрирует этот принцип. Будем изу­чать отрезки ряда 1 + 3 + 5 +... последовательных нечетных чисел. Легко заметить, что

1 = 1², 1+3=2², 1+3+5=3², 1+3+5+7=4²

и т. д.

Этим подсказывается общее утверждение: при любом нату­ральном n сумма первых n нечетных чисел равна n². Докажем это общее предложение по индукции. Оно, конечно, верно, если n равно 1. Мы должны доказать, что результат верен для лю­бого натурального числа n; в силу принципа индукции можно предполагать, что предложение уже доказано для всех нату­ральных чисел, меньших n. Пусть, и частности, нам уже из­вестно, что сумма первых n-1 нечетных чисел равна (n-1)². Сумма первых n нечетных чисел получится из нее добавлени­ем n-го нечетного числа, равного 2n-1. Таким образом, сумма первых n нечетных чисел есть

(n-1)² + 2n - 1,

что равно n². Этим требуемое утверждение доказано.

Изложение доказательства по индукции в безупречной фор­ме требует некоторого внимания. В приведенном примере дока­зывалось, что сумма первых n нечетных чисел равна n². Здесь n — любое натуральное число, и, конечно, утверждение не изме­нится, если всюду, где встречается n, употреблять какой-нибудь другой символ. Когда мы приступаем к доказательству, n есть вполне определенное число и имеется опасность употребить один и тот же символ в разных смыслах или даже высказать бессмыс­лицу типа «предложение верно при n, равном n-1». Чтобы избежать этого, нужно использовать в случае необходимости разные символы.

С общелогической точки зрения нет ничего более очевид­ного, чем законность доказательства по индукции. Тем не менее, можно спорить, является ли этот принцип по своей при­роде определением или аксиомой или это логический принцип. Но, так или иначе, ясно, что принцип индукции служит для того, чтобы расположить натуральные числа в определенном порядке: установив, что вначале идут числа 1, 2,.... n-1, мы объявляем следующим числом число n. Таким образом, этот принцип объясняет, что означают на самом деле слова «и так далее», встречающиеся при попытке перечислить вес натураль­ные числа.

Простые числа

Очевидно, что каждое натуральное чис­ло а делится на 1 (отношение равно а) и на а (отношение равно 1). Множитель а, отличный от 1 или а, называется собственным множителем. Известно, что существуют числа, не имеющие соб­ственных множителей; они называются простыми числами или простыми. Первые несколько простых таковы:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...

Считать ли простым числом 1 вопрос соглашения, но удобнее 1 не считать простым.

Число, не являющееся простым и не равное 1, называется со­ставным, такое число можно представить в виде произведения двух чисел, каждое из которых больше 1. Хорошо известно, что любое составное число можно представить в виде произведения простых; при этом, конечно, некоторые простые могут встре­титься по нескольку раз. Возьмем, например, число 666; ясно, что оно делится на 2, и мы получаем 666 = 2 • 333. Далее, 333 имеет очевидный множитель 3, откуда 333 = 3• 111. Множитель 111 снова делится на 3, так что 111 = 3 • 37. Следовательно,

666 = 2 • 3 • 3 • 37,

и мы получили представление составного числа 666 в виде про­изведения простых. Имеется общая теорема о том, что каждое число представимо в виде произведения простых, или, что то же самое, любое число, большее 1, является простым либо разла­гается в произведение простых.

Для доказательства этого общего утверждения воспользу­емся методом индукции. Докажем утверждение для числа n, считая, что оно уже доказано для любого числа, меньшего n. Если n простое, доказывать нечего. Если n составное, то его можно представить в виде произведения аb, где a и b больше 1 и меньше n. Мы уже знаем, что числа а и b или являются про­стыми, или разлагаются в произведение простых; подставив их разложения в равенство n = аb, получаем разложение n на про­стые множители. Это доказательство столь просто, что может показаться читателю совершенно излишним. Другая общая те­орема о разложении на простые будет доказываться уже не так просто.

Ряд простых 2, 3, 5, 7,... издавна интересовал людей. В дальнейшем мы сформулируем некоторые из полученных в этом направлении результатов. В настоящий момент мы ограничим­ся доказательством того, что ряд простых бесконечен. Это до­казательство Евклида (книга IX, предложение 20) может слу­жить образцом изящества и простоты. Пусть 2, 3, 5,..., Р — ряд простых до некоторого простого Р. Рассмотрим произведе­ние всех этих простых, добавим к нему 1 и положим

N =2•3•5,...P+1.

Это число не может делиться на 2, так как если бы оно делилось на 2, то и 2•3•5... Р, а потому и разность N- 2•3•5... Р делились бы на 2. Но разность этих чисел равна 1 и на 2 не делится. Аналогично убеждаемся в том, что N не может делиться на 3, на 5 и вообще ни на какое другое простое вплоть до Р. С другой стороны, N должно делиться на какое-нибудь простое (на само себя, если N простое, или на любой простой делитель N, если N составное). Следовательно, существует простое число, отличное от любого из простых 2, 3, 5,..., Р и потому большее Р. Таким образом, ряд простых оборваться не может.