простых чисел. Для проверки данной гипотезы продолжаем вычисления и находим р(6). Ура! р(6) = 11, что подтверждает наше предположение.

[Но, к сожалению, оказывается, что р(7) равно 15. Увы, все идет насмарку, и приходится начинать сначала. Известно, что значения р{п) отличаются довольно сложным поведением, хотя С. Рамануджану (S. Ramanujan) удалось угадать и доказать много замечательных фактов, касающихся этих чисел. Более подробную информацию можно найти в книге G. Н. Hardy, Ramanujan (London: Cambridge University Press, 1940), гл. 6 и 8.]

Математическая индукция не имеет ничего общего с тем индуктивным методом, который мы только что описали. Это не догадка, а неопровержимое доказательство утверждения; скажу больше: это доказательство бесконечного числа утверждений, по одному для каждого п. "Индукцией" этот метод назван только потому, что сначала нужно выдвинуть предположение о том, что нужно доказать, а затем уже применять метод математической индукции. Начиная с этого момента, слово "индукция" в книге будет использоваться только для обозначения доказательства методом математической индукции.

Существует геометрический способ доказательства соотношения (2). На рис. 3 для п = 6 показано, что

клеток разбиты на группы 1 + 3 Н-----h (2п - 1) клеток.

Но в конечном счете этот рисунок можно считать "доказательством" только в случае, если мы покажем, что данное построение можно выполнить для любого п. А это, в сущности, и будет доказательством по индукции.

В нашем доказательстве соотношения (2) был использован только частный случай (Ь); мы просто показали, что из справедливости Р{п) следует справедливость Р{п + 1). Это очень важный случай, который встречается довольно часто, но в следующем примере будут проиллюстрированы более широкие возможности

метода математической индукции. Определим последовательность Фибоначчи Fq, Fl, F2, ... с помощью такого правила: Fo = О, Fi = 1, а каждый последующий член равен сумме двух предыдущих. Таким образом, первые члены этой последовательности выглядят так: О, 1, 1, 2, 3, 5, 8, 13, ... (более подробно мы изучим эту последовательность в разделе 1.2.8). А теперь докажем, что если через ф обозначить число (1 + у/5)/2 , то имеем

Рис.3. Нечетные числа в сумме дают квадрат.

Fn<Ф

для всех целых положительных п. Назовем эту формулу утверждением Р{п).

Если п = 1, то Fl = 1 = ф° = Ф~, поэтому п. (а) выполнен. Переходя к п. (Ъ), заметим сначала, что Р(2) также справедливо, поскольку F2 = 1 < 1-6 < = ф"-А теперь, если все Р(1), Р(2), Р(п) справедливы и п > 1, то мы знаем, в частности, что справедливы Р(п - 1) и Р(п). Поэтому P„ i < ф"~ Fn < ф"~ Складывая данные неравенства, получаем

Fn+i = Р„-1 + Р„ < Н ф""- = 0"-(1 + ф).

Важное свойство числа ф, которое и является причиной первоочередного выбора этого числа для данной задачи, состоит в том, что

\ + ф = ф\ (5)

Подставив (5) в (4), получим F„+i < 0", а это и есть утверждение Р{п + 1). Таким образом, п. (Ь) выполнен и формула (3) доказана методом математической индукции. Обратите внимание, что п. (Ь) мы выполняли двумя различными способами: непосредственно доказали Р{п + 1) при п - 1 w. использовали индуктивный метод при п > 1. Это было необходимо, так как при п = 1 ссылка на Р{п - 1) = Pifi) была бы незаконной.

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

Алгоритм Е [Обобщенный алгоритм Евклида). Даны два целых положительных числа тип. Требуется найти их наибольший общий делитель* d и два целых числа а и Ь, таких, что am + bn = d.

El. [Инициализация.] Присвоить а <- b <- 1, а b О, с т, d п.

Е2. [Деление.] Пусть диг - это частное и остаток от деления с на d соответственно. (Тогда с = qd + r, где О < г < d.)

ЕЗ. [Остаток - нуль?] Если г = О, то выполнение алгоритма прекращается; в этом случае имеем am + bn = d, как и требовалось.

Е4. [Повторение цикла.] Присвоить с <- d, d <- г, t < а, а <- а, а t - да, t Ь, Ь Ь, Ь <- t - дЬ и вернуться к шагу Е2.

Если изъять из алгоритма переменные а, Ь, а и Ь и использовать m и п в качестве вспомогательных переменных с и d, то получим старый алгоритм 1.1Е. В новой версии алгоритма вьшолняется немного больше вычислений, так как необходимо определить коэффициенты а и Ь. Предположим, что m = 1 769 и п = 551. Тогда последовательно (после шага Е2) имеем:

Проверяя полученные результаты, убеждаемся в том, что все правильно, так как 5 X 1769 - 16 X 551 = 8845 - 8816 = 29, т. е. мы получили наибольший общий делитель чисел 1 769 и 551.

Теперь нужно доказать, что рассматриваемый алгоритм работает правильно при любых тип. Для этого попробуем применить метод математической индукции к следующему утверждению Р(п): "Алгоритм Е дает правильное решение для заданного п и всех целых т". Но провести подобное доказательство не так-то просто, поэтому нужно доказать сначала несколько дополнительных фактов. После

Сокращенно-gcd (greatest common divisoi). - Прим. перев.

некоторого изучения проблемы выясняется, что нужно доказать какой-то факт, связанный с коэффициентами а, Ь, а и Ь. Этот факт заключается в том, что равенства

ат + Ьп = с, am + bn = d (6)

верны в каждом случае выполнения шага Е2. Данные равенства можно доказать непосредственно, заметив, что они безусловно справедливы после первого выполнения шага Е2 и что шаг Е4 не меняет это положение вещей (см. упр. 6).

Теперь мы готовы индукцией по п доказать, что алгоритм Е работает правильно. Если т кратно п, то очевидно, что алгоритм работает правильно, поскольку его работа заканчивается на шаге ЕЗ в первом же цикле и мы получаем верный результат. Это происходит всегда, когда п = 1. Поэтому остается провести доказательство для случая, когда п > 1 и m не является кратным п. В такой ситуации в первом цикле осуществляется переход к шагу Е4 и выполняются операции присвоения с п, d г. И так как г < п, по индукции можно предположить, что окончательное значение d - это наибольший общий делитель чисел п и г. Из доказательства, приведенного в разделе 1.1, следует, что пары {т,п} и {п,г} имеют одинаковые наибольшие общие делители и, в частности, один и тот же наибольший общий делитель. Значит, d - это наибольший общий делитель чисел m и п и согласно (6) am + bn = d.

Фраза, которая в приведенном выше доказательстве выделена курсивом, является иллюстрацией того общепринятого условного языка, который так часто используется в доказательствах методом индукции. Например, выполняя п. (Ь), вместо того чтобы сказать "Теперь предположим, что утверждения Р(1), Р(2),..., Р(п) справедливы, и на этом основании докажем справедливость утверждения P(n-f 1)", мы будем говорить просто "Теперь докажем утверждение Р(п); по индукции мы можем предположить, что Р{к) верно для любого 1 < к < п".

Если хорошо вдуматься и посмотреть на все вышесказанное с несколько иной точки зрения, то перед нами предстанет общий метод доказательства корректности любого алгоритма. Идея состоит в том, чтобы взять блок-схему некоторого алгоритма и к каждой стрелке добавить примечание о текущем состоянии дел в тот момент, который соответствует стрелке. На рис. 4 эти примечания (мы их будем называть также утверждениями) обозначены через А1, А2, А6. (Все они сделаны при дополнительном условии, что переменные принимают только целые значения; это усчовие опущено с целью экономии места.) В утверждении А1 даются первоначальные предположения о входных данных алгоритма, а в Л. формулируется положение о том, что мы хотим доказать по поводу выходных значений а, 6 и d.

Общий метод заключается в том, чтобы для каждого блока на блок-схеме доказать следующее:

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

Согласно описанному методу для нашего примера мы должны доказать, что если до выполнения шага Е2 верно А2 либо А6, то после выполнения этого шага верно A3. (В данном случае утверждение А2 является более сильным, чем А6, т. е. из А2