Воробьев Н. Н. Числа Фибоначчи. — Изд. 5-е. — М. : Наука, 1984. — 144 с. — (Популярные лекции по математике ; вып. 6).

Популярные лекции по математике

Н. Н. ВОРОБЬЕВ

ЧИСЛА ФИБОНАЧЧИ

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 6

Н. Н. ВОРОБЬЕВ

ЧИСЛА ФИБОНАЧЧИ

ИЗДАНИЕ ПЯТОЕ

МОСКВА «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

1984

22.131 В 75

УДК 511

Воробьев H. Н.

В 75 Числа Фибоначчи.— 5-е изд.— М.: Наука, 1984.— 144 с.— (Популярные лекции по математике).— 20 к.

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

Предназначается учащимся старших классов средней школы и всем любителям математики.

1702030000—031 ББК 22.131

В 053(02)-84 54"83 517.1

D 1702030000—031 гл 00

В--54-83

053(02)-84

© Издательство «Наука» Главная редакция физико-математической литературы, 1978.

ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ

В элементарной математике существует много задач, часто трудных и интересных, которые не связаны с чьим-либо именем, а скорее носят характер своего рода «математического фольклора». Такие задачи рассыпаны по обширной популярной или просто развлекательной математической литературе, и часто бывает очень трудно установить, в каком именно сборнике появилась впервые та или иная задача.

Эти задачи нередко имеют хождение в нескольких вариантах; иногда несколько таких задач объединяют в одну, более сложную; иногда, наоборот, одна задача распадается на несколько более простых; словом, часто оказывается трудно указать, где кончается одна задача и где начинается другая. Правильнее всего было бы считать, что в каждой из таких задач мы имеем дело с маленькими математическими теориями, имеющими свою историю, свою проблематику и свои методы, — все это, разумеется, тесно связанное с историей, проблематикой и методами «большой математики».

Такой теорией является и теория чисел Фибоначчи. Выросшие из знаменитой «задачи о кроликах», имеющей почти семисотпятидесятилетнюю давность*), числа Фибоначчи до сих пор остаются одной из самых увлекательных глав элементарной математики. Задачи, связанные с числами Фибоначчи, приводятся во многих популярных изданиях по математике,

*) А сейчас, к моменту очередного издания данной брошюры, — уже более чем семисотпятидесятилетнюю давность.

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

Предлагаемая книжка содержит круг вопросов, послуживших темой нескольких занятий математического кружка школьников при Ленинградском государственном ордена Ленина университете им. А. А. Жданова в 1949/50 учебном году. В соответствии с желаниями участников кружка на этих занятиях рассматривалась преимущественно теоретико-числовая сторона вопроса, которая развита более подробно и в настоящей брошюре.

Книжка рассчитана в основном на школьников 9—10 классов. Понятие предела встречается здесь только в пп. 8 и 9 § 3. Читатель, не знакомый с этим понятием, может без ущерба для понимания дальнейшего эти пункты при чтении пропустить. Сказанное относится также к биномиальным коэффициентам (пп. 11—15 § 1) и к тригонометрии (пп. 3 и 4 § 4). Излагаемые в брошюре элементы теории делимости и теории непрерывных дробей никаких предварительных знаний, выходящих за рамки школьного курса, у читателя не предполагают.

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

ПРЕДИСЛОВИЕ К ЧЕТВЕРТОМУ ИЗДАНИЮ

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

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

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

Далее, числа Фибоначчи проявили себя еще в нескольких математических вопросах, среди которых в первую очередь следует назвать решение Ю. В. Матиясевичем десятой проблемы Гильберта и далеко не столь глубокую, но приобретшую широкую известность теорию поиска экстремума унимодальной функции, построенную впервые, по-видимому, Дж. Кифером.

Наконец, было установлено довольно большое количество ранее неизвестных свойств чисел Фибоначчи, а к самим числам существенно возрос интерес. Значительное число связанных с математикой людей в различных странах приобщилось к благородному хобби «фибоначчизма». Наиболее убедительным свидетельством этому может служить журнал The Fibonacci Quarterly, издаваемый в США с 1963 г.

Все сказанное определило изменения содержания книги от издания к изданию и тот вид, в котором она предлагается читателю сейчас. Во втором издании был добавлен параграф о фибоначчиевых планах поиска экстремума унимодальной функции вместе с возникающими при этом общематематическими и вычислительными вопросами. В третьем издании была расширена теоретико-числовая тематика, и этот материал из § 2 оказался полезной информацией при решении десятой проблемы Гильберта. Наконец, в настоящем издании «подтягиваются» до общего уровня и объема § 3 и 4. В § 3 приводятся ставшие классическими теоремы о точности приближений подходящими дробями и описывается роль чисел Фибоначчи в этих фактах, а в § 4 включен анализ игры «цзяньшицзы», теоретико-игровой анализ которой опирается на детальное рассмотрение фибоначчиевых представлений натуральных чисел.

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

Вырица Н. Н. Воробьев

1978 г.

Настоящее издание отличается от предыдущего (1978 г.) лишь незначительными исправлениями.

ВВЕДЕНИЕ

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

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

Тем больший интерес представляет для нас сочинение «Liber abacci» («Книга об абаке»), написанная знаменитым итальянским математиком Леонардо из Пизы, который известен больше по своему прозвищу Фибоначчи (Fibonacci — сокращенное filius Bonacci, т. е. сын Боначчи). Эта книга, написанная в 1202 г., дошла до нас во втором своем варианте, который относится к 1228 г.

«Liber abacci» представляет собой объемистый труд, содержащий почти все арифметические и алгебраические сведения того времени и сыгравший заметную роль в развитии математики в Западной Европе в течение нескольких следующих столетий, В частности, именно по этой книге европейцы познакомились с индусскими («арабскими») цифрами.

Сообщаемый в «Liber abacci» материал поясняется на большом числе задач, составляющих значительную часть этого трактата.

Пара 1

Первый 2

Второй 3

Третий 5

Четвертый 8

Пятый 13

Шестой 21

Седьмой 34

Восьмой 55

Девятый 89

Десятый 144

Одиннадцатый 233

Двенадцатый 377

Рассмотрим одну такую задачу, помещенную на стр. 123— 124 рукописи 1228 г.

«Сколько пар кроликов в один год от одной пары рождается?»

«Некто поместил пару кроликов в некоем месте, огороженном со всех сторон стеной, чтобы узнать, сколько пар кроликов родится при этом в течение года, если природа кроликов такова, что через месяц пара кроликов производит на свет другую пару, а рождают кролики со второго месяца после своего рождения. Так как первая пара в первом месяце дает потомство, удвой, и в этом месяце окажутся 2 пары; из них одна пара, а именно первая, рождает и в следующем месяце, так что во втором месяце оказывается 3 пары; из них в следующем месяце 2 пары будут давать потомство, так что в третьем месяце родятся еще 2 пары кроликов, и число пар кроликов в этом месяце достигнет 5; из них в этом же месяце будут давать потомство 3 пары, и число пар кроликов в четвертом месяце достигнет 8; из них 5 пар произведут другие 5 пар, которые, сложенные с 8 парами, дадут в пятом месяце 13 пар; из них 5 пар, рожденных в этом месяце, не дают в том же месяце потомства, а остальные 8 пар рождают, так что в шестом месяце оказывается 21 пара; сложенные с 13 парами, которые родятся в седьмом месяце, они дают 34 пары; сложенные с 21 парой, рожденной в восьмом

месяце, они дают в этом месяце 55 пар; сложенные с 34 парами, рожденными в девятом месяце, они дают 89 пар; сложенные вновь с 55 парами, которые рождаются в десятом месяце, они дают в этом месяце 144 пары; снова сложенные с 89 парами, которые рождаются в одиннадцатом месяце, они дают в этом месяце 233 пары; сложенные вновь с 144 парами, рожденными в последнем месяце, они дают 377 пар; столько пар произвела первая пара в данном месте к концу одного года. Действительно, на этих полях ты можешь увидеть, как мы это делаем; именно, мы складываем первое число со вторым, т. е. 1 и 2; и второе с третьим; и третье с четвертым; и четвертое с пятым; и так одно за другим, пока не сложим десятое с одиннадцатым, т. е. 144 с 233; и мы получим общее число упомянутых кроликов, т. е. 377; и так можно делать по порядку до бесконечного числа месяцев».

2. Перейдем теперь от кроликов к числам и рассмотрим следующую числовую последовательность:

ии и2, ип, (1)

в которой каждый член равен сумме двух предыдущих членов, т. е. при всяком п > 2

Un = Un-l + Un-2- (2)

Такие последовательности, в которых каждый член определяется как некоторая функция предыдущих, часто встречаются в математике и называются рекуррентными или, по-русски, возвратными последовательностями. Сам процесс последовательного определения элементов таких последовательностей называется рекуррентным процессом, а равенство (2) — возвратным (рекуррентным) уравнением. Элементы общей теории возвратных последовательностей читатель может найти в уже упоминавшейся книжке А. И. Маркушевича (см. стр. 4).

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

этому условию; например,

2, 5, 7, 12, 19, 31, 50, 1, 3, 4, 7, 11, 18, 29, -1, -5, -6, -11, -17, ...

и т. д.

Значит, для однозначного построения последовательности (1) условия (2) явно недостаточно, и нам следует указать некоторые дополнительные условия. Например, мы можем задать несколько первых членов последовательности (1). Сколько же первых членов последовательности (1) мы должны задать, чтобы можно было вычислять все следующие ее члены, пользуясь при этом только условием (2)?

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

Но этого, очевидно, уже и достаточно для того, чтобы иметь возможность вычислить любой член последовательности (1). В самом деле, и3 можно вычислить как сумму заданных нам щ и и2; и4 — как сумму и2 и уже вычисленного ранее и3\ us — как сумму уже вычисленных и3 и и4 и т. д. «по порядку до бесконечного числа членов». Переходя таким образом от двух соседних членов последовательности к непосредственно следующему за ними члену, мы можем дойти до члена с любым наперед заданным номером и вычислить его.

3. Обратимся теперь к важному частному случаю последовательности (1), когда и\ = 1 и U2 = 1. Условие (2), как было только что отмечено, дает нам возможность вычислять последовательно один за другим все члены этого ряда. Нетрудно проверить, что в этом случае первыми четырнадцатью его членами будут числа

1, 1, 2, 3, 5, 8, 13, 21, 34; 55, 89, 144, 233, 377, которые уже встречались нам в задаче о кроликах.

В честь автора этой задачи вся последовательность (1) при u\ = и2 = 1 называется рядом Фибоначчи, а члены ее — числами Фибоначчи.

Числа Фибоначчи обладают целым рядом интересных и важных свойств, рассмотрению которых и посвящена вся эта книжка.

§ 1. ПРОСТЕЙШИЕ СВОЙСТВА ЧИСЕЛ ФИБОНАЧЧИ

1. Вычислим сначала сумму первых п чисел Фибоначчи. Именно, докажем, что

+ ... +Un= Un+2— 1. (LI)

В самом деле, мы имеем:

Сложив все эти равенства почленно, мы получим

их + и2 + ... + ип = ип+2 — и2,

и нам остается вспомнить, что и2 = 1.

2. Сумма чисел Фибоначчи с нечетными номерами:

U\ + Uz + Us+ ... +U2n-l = U2n. (1.2)

Для доказательства этого равенства напишем

Сложив эти равенства почленно, мы и получим требуемое.

3. Сумма чисел Фибоначчи с четными номерами: и2 + и^-г ... +и2л = М2Л+1 —1. (1.3)

На основании п. 1 мы имеем

и\ + и2 + «з +... + и2п — и2п+2 — 1;

вычтя почленно из этого равенства равенство (1.2), мы получим

U2 + «4 + • • • + U>2n = U2n+2 — 1 — tl2n = #2я-Н — 1|

а это нам и требовалось.

Вычитая, далее, почленно (1.3) из (1.2), получаем

Ui — U2 + Uz — U4 + ... + U2n-l—U2n = — «2Л-1+1. (1.4)

Прибавим теперь к обеим частям (1.4) по и2п+\:

U\ — U2 + Uz — U4+ — U2n + U2n+\ = 1. (1.5)

Объединяя (1.4) и (1.5), получаем выражение для знакопеременной суммы чисел Фибоначчи:

Hl — u2 + Uz — w4+ ... +(—l)rt+1Wn =

= (_1)«+1„я_1 + 1, (1.6)

4. Формулы (1.1) и (1.2) были выведены при помощи почленного сложения целой серии очевидных равенств. Еще одним примером применения этого приема может служить вывод формулы для суммы квадратов первых п чисел Фибоначчи:

и\ + ul + , , . + il\= Unlin+U (1.7)

Заметим для этого, что

UkUk+l — tlk-\Uk = Uk (Uk+l — Uk-l) = ilk'

Сложив равенства

почленно, мы получаем формулу (1.7).

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

Сущность метода полной индукции (называемого часто также методом математической индукции) состоит в следующем: для доказательства, что некоторое утверждение справедливо для всякого натурального числа, достаточно установить, что:

а) оно имеет место для числа 1;

б) из справедливости доказываемого утверждения для какого-либо произвольно выбранного натурального числа п следует его справедливость для числа п + 1.

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

В первой части (обычно сравнительно простой) устанавливается справедливость доказываемого утверждения для единицы. Справедливость доказываемого утверждения для единицы называют иногда основанием индукции. Во второй части доказательства (как правило, более сложной) делается предположение о справедливости доказываемого утверждения для некоторого произвольного (но фиксированного) числа п, и из этого предположения, которое часто называют индуктивным предположением, выводится, что и для числа п + 1 доказываемое утверждение имеет место. Вторая часть доказательства называется индуктивным переходом.

Подробное изложение метода полной индукции и многочис* ленные примеры применения различных вариантов этого метода можно найти в брошюре И. С. Соминского «Метод математической индукции» (серия «Популярные лекции по математике», вып. 3, М., «Наука», 1074). Так, в частности, неоднократно применяемый нами далее вариант метода полной индукции с основанием индукции, состоящим в доказательстве утверждения при п = 1 и az = 2, и индуктивным переходом «от п и п + 1 к п -|- 2» приводится в брошюре И. С. Соминского на стр. 13 и иллюстрируется на стр. 21—22 примером 7 и задачей 12.

Иногда применяется индуктивное рассуждение, которое мож« но назвать переходом «от всех чисел, меньших /г, к я». При этом необходимость в специальном доказательстве основания индукции отпадает, так как, говоря формально, доказательство для случая п = 1 и есть переход от «всех» целых положительных чисел, меньших единицы (которых просто нет), к единице. Именно таким является следующее доказательство возможности разложения любого натурального числа на простые множители.

Предположим, что каждое из чисел, меньших некоторого п9 разложимо в произведение простых множителей. Если число п оказывается простым, то оно само и является своим разложением. Если же число п составное, то его, по определению, можно представить в виде произведения хотя бы двух сомножителей: п = п\п2> где П\ Ф 1 и П2 Ф 1. Но тогда П\ < п и п2 < л, а по индуктивному предположению как пи так и п2 разлагаются на простые множители. Тем самым и п разложимо на простые множители.

Более сложные варианты индуктивного рассуждения лежат в основе доказательства теоремы п. 36 § 2 и в построении из п. 10 § 4.

6. Простейшей реализацией идеи индукции в применении к числам Фибоначчи является само

определение чисел Фибоначчи. Оно, как разъяснялось во Введении, состоит в указании двух первых чисел Фибоначчи: и\ = 1 и и2 = 1 и в индуктивном переходе от ип и Un+\ к Un+2, даваемым рекуррентным соотношением

tin + Un+l — Un+2'

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

В качестве примера рассмотрим так называемую «задачу о прыгуне». Она состоит в следующем.

Прыгун может прыгать в одном направлении вдоль разделенной на клетки полосы, перемещаясь при каждом прыжке либо в соседнюю клетку, либо через клетку. Сколькими способами может он сдвинуться на п—1 клетку и, в частности, переместиться из первой клетки в /г-ю? (Способы прыгания считаются одинаковыми, если в ходе каждого из них прыгун побывает в одних и тех же клетках.)

Обозначим искомое число через хл. Очевидно, х\ = 1 (ибо переход из первой клетки в первую же осуществляется только одним способом — отсутствием прыжков) и х2 = 1 (переход из первой клетки во вторую также единствен: он состоит в одном непосредственном прыжке на соседнюю клетку). Пусть целью прыгуна является достижение п + 2-й клетки. Общее число способов осуществления этой цели в наших обозначениях равно хп+2- Но с самого начала эти способы разбиваются на два класса: начинающиеся с прыжка во вторую клетку и начинающиеся с прыжка в третью клетку. Из второй клетки прыгун может переместиться в п + 2-ю хп+\ способами, а из третьей Хп способами. Таким образом, последовательность чисел хи *2, хПу ... удовлетворяет рекуррентному соотношению

Хп + Хп+1 = Хп+2

и поэтому совпадает с последовательностью чисел Фибоначчи: Хп —

7. Докажем по индукции следующую важную формулу:

Un+m = Un-\Um + UnUm+\. (1-8)

Доказательство этой формулы будем вести индукцией по т. При m = 1 эта формула принимает вид Un+i = un-\U\ + ипи2, что очевидно. При m = 2 формула (1.8) также верна, потому что

Un+2 = tln-\U2 + UnU2 = Un-l + 2un =

= Un-l + Mn + = Wn+l + W/ï.

Основание индукции, таким образом, доказано. Индуктивный переход докажем в следующей форме: предполагая, что формула (1.8) справедлива при m = k и при m = k + 1, докажем, что она имеет место и при m = k + 2.

Итак, пусть

Un+k+\ = W/i-ittjfe+i + UnUk+2.

Сложив последние два равенства почленно, мы получим

Un+k+2 = Un-lUk+2 + UnUk+3>

а это и требовалось.

Формулу (1.8) легко интерпретировать (и даже доказать) в терминах задачи о прыгуне.

Именно, общее число способов перемещения прыгуна из первой клетки в п + т-ю равно ип+т. Среди этих способов будут как те, при которых прыгун перепрыгнет через п-ю клетку, так и те, при которых он побывает в ней.

При способах первого класса прыгун обязан достичь п—1-й клетки (он может сделать это ип-\ способами), затем совершить прыжок на n+1-ю клетку и, наконец, сместиться на оставшиеся (п + m) — (п + 1) = m—i клеток (это осуществимо ит способами). Следовательно, первый класс насчитывает Un-\um способов. Аналогично, при способах второго класса прыгун достигает п-й клетки (это возможно ип способами), после чего переходит вл + т-ю клетку (одним из um+i способов). Поэтому во втором

классе имеется ипит+\ способов, и формула (1.8) доказана.

8. Полагая в формуле (1.8) т = п, мы получаем

#2/г = Un-\Un + UnUn+U

или

U2n = Un(Un-\ + Un+l). (1.9)

Из написанного равенства видно, что и2п делится на ип- В следующем параграфе мы докажем значительно более общее утверждение.

Так как

ип = Un+l — Un-U

формулу (1.9) можно переписать так: и2п = (ип+\ — ип-\) (Un+l +

или

2 2

U2n = Un+\ — Un-

т. е. разность квадратов двух чисел Фибоначчи, номера которых отличаются на два, есть снова число Фибоначчи.

Аналогично (полагая m = 2п) можно показать,

что

изп = Un+\ + ип — ип-\.

9. В дальнейшем нам пригодится следующая формула:

ul = un-iun+l+ (-1)"*1. (1.10)

Докажем ее индукцией по п. Для п = 2 (1.10) принимает вид

III = U\Uz— 1,

что очевидно.

Предположим теперь формулу (1.10) доказанной для некоторого п. Прибавим к обеим частям ее по UnUn+\. Мы получим

и\ + UnUn+l = Un-lUn+l + UnUn+\ +{—1)я+1,

или

Un (Un + Un+\) = Un+l (Un-l + Un) + (—1) n+l,

или или

Этим индуктивный переход обоснован, и формула (1.10) доказана для любого п.

10. Аналогично только что доказанным свойствам чисел Фибоначчи можно установить еще и такие свойства этих чисел:

Доказательство предоставляется провести читателю.

11. Не менее замечательными, чем числа Фибоначчи, являются другие числа, называемые биномиальными коэффициентами.

Биномиальными коэффициентами называются коэффициенты при степенях х в разложениях степеней (1+*)":

(l+x)n = Cl + С\х + Clx2 +...+ Clxn. (1.11)

Очевидно, числа С* однозначно определены при всех целых неотрицательных п и всех целых неотрицательных k, не превосходящих п.

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

Предварительно установим некоторые свойства биномиальных коэффициентов.

Положив в (1.11) п = 1, мы сразу видим, что

С?=С! = 1; кроме того, имеет место следующая лемма,

Лемма.

Доказательство. Мы имеем

или, пользуясь определением биномиальных коэффициентов,

Но слева и справа в этом равенстве стоит один и тот же полином. Поэтому и коэффициенты при одинаковых степенях х слева и справа должны быть равны. В частности, должно быть

а это и требовалось.

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

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

т, e,

1 1

1 2 1 13 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1

Подробное изложение основных свойств треугольника Паскаля и составляющих его биномиальных коэффициентов содержится в брошюре В. А. Успенского «Треугольник Паскаля» (серия «Популярные лекции по математике», вып. 43, «Наука», 1979).

Строки треугольника Паскаля принято нумеровать сверху вниз, причем верхняя строка, состоящая из единственной единицы, считается нулевой.

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

13. Формула (1.11) позволяет нам сразу вывести два важных соотношения, связывающих биномиальные коэффициенты, составляющие одну строку треугольника Паскаля.

Полагая в (1.11) х = 1, мы получаем

2П = С°П + С{п + С1+ ...+С1 Если же принять х = —1, то мы получим

o=c°n-cn + cl +...+(- 1)пСпп.

14. Докажем индукцией по п, что

С«= П("~1\2\\^Гкк + 1) ■ (1-12)

Эта формула часто принимается за определение биномиальных коэффициентов. Она характеризует биномиальный коэффициент С„ как «число сочетаний из п элементов по k». Мы пошли здесь по иному, более

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

Если условиться считать, что произведение нулевого числа сомножителей всегда равно единице, то при k = 0 мы из (1.12) получаем уже известное нам С°п = 1. Имея это в виду, мы можем ограничиться случаем k ^ 1.

При n = 1 мы имеем

Пусть теперь при некотором данном n формула (1.12) справедлива для любого значения Ä = 0,1, ..., п.

Рассмотрим число C*+i. Так как k^l, мы можем написать

Сh _ 1 ; r>k

n+\ — "Г ^П9

или, воспользовавшись индуктивным предположением (1.12),

Последнее равенство является формулой (1.12) для биномиальных коэффициентов из следующей, /г+ 1-й строки треугольника Паскаля.

15. Проведем через числа треугольника Паскаля линии, идущие под углом 45 градусов к его строкам, и назовем их восходящими диагоналями треугольника Паскаля. Восходящими диагоналями будут, например, прямые, проходящие через числа 1, 4, 3 или 1, 5, 6, 1.

Покажем, что сумма чисел, лежащих на некоторой восходящей диагонали, есть число Фибоначчи.

В самом деле, первая, самая верхняя восходящая диагональ треугольника Паскаля состоит только из единицы. Только из единицы состоит и вторая его диагональ. Для доказательства инте-

ресующего нас предложения нам достаточно показать, что сумма всех чисел, составляющих п-ю и п+ 1-ю диагонали треугольника Паскаля, равна сумме чисел, составляющих его п + 2-ю диагональ.

Но на п-й диагонали расположены числа

^9 ^,1 г2

ип-1> u/i-2> °/i-3> ••• »

а на п + 1 -й — числа

Сумму всех этих чисел запишем так:

С°п + К-1 + Сп-1) + (с\-2 + С2п-г)+ .... или, принимая во внимание лемму в п. 11,

Си+ + •••

Последнее выражение есть сумма чисел, лежащих на п + 2-й восходящей диагонали треугольника.

Из только что доказанного на основании формулы (1.1) мы сразу получаем: сумма всех биномиальных коэффициентов, лежащих выше п-й восходящей диагонали треугольника Паскаля (включая саму эту диагональ), равна ип+2— 1.

Используя формулы (1.2), (1.3), (1.4) и подобные им, читатель без труда может получить дальнейшие тождества, связывающие числа Фибоначчи с биномиальными коэффициентами.

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

Исследуем для этого различные последовательности mi, U2, ♦.., ип, ..., удовлетворяющие соотношению

Un = Un-2 + Un-L (1.13)

Все такие последовательности мы будем называть решениями уравнения (1.13).

Будем обозначать буквами V, У и У" соответственно последовательности

v[> v2> v3> • •• •

/ r r V[9 V2, l>3, ...

rr rr rr V{, V2, Vj , ...

Сначала докажем две простые леммы,

Лемма 1. Если V есть решение уравнения (1.13), а с — произвольное число, то последовательность cV (г. е. последовательность cv\, cv2i cvz, ...) есть также решение уравнения (1.13).

Доказательство. Умножив соотношение

Vn = Vn-2 + Vn-l

почленно на с, мы получаем

Cün = CVn-2 + CVn-U

а это и требовалось.

Лемма 2. Если последовательности V и V" являются решениями уравнения (1.13), то и их сумма V + Vй (г. е. последовательность v\ + v\, v2 + v2t Щ + v", ... ) также является решением уравнения (1.13).

Доказательство. Из условия леммы мы имеем

v'n = Vn-2 + Vn-i

и

Vn =Vn-2+ Оя-1-

Сложив эти два равенства почленно, мы получим

Vn + Vn = Wn-2 + Vn-2) + (v'n-\ + t>„-l).

Этим лемма доказана.

Пусть теперь V и V" — два непропорциональных решения уравнения (1.13) (т. е. два таких решения уравнения (1.13), что при любом постоянном с найдется такой номер п, для которого -тг ф с). Покажем, что всякую последовательность V, являющуюся решением уравнения (1.13), можно представить в виде

C1V + C2V", (1.14)

где с\ и C2 — некоторые постоянные. Поэтому принято говорить, что (1.14) является общим решением уравнения (1.13).

Предварительно докажем, что если решения V и V" уравнения (1.13) непропорциональны, то

^Ф^г (1.15)

(т. е. что эта непропорциональность проявляется уже в первых двух членах последовательностей V и V").

Доказательство (1.15) ведется от противного. Пусть для непропорциональных решений V и V" уравнения (1.13)

(1.16)

Написав производную пропорцию, мы получаем

или, принимая во внимание, что V и V" являются решениями уравнения (1.13),

Аналогично убеждаемся (индукция!) в том, что

Таким образом, из (1.16) следует, что последовательности V и V" пропорциональны, а это противоречит предположению. Значит, справедливо (1.15).

Возьмем теперь некоторую последовательность V, являющуюся решением уравнения (1.13). Эта последовательность, как уже было выяснено в п. 2 Введения, вполне определена, если заданы два ее первых члена, vi и и2.

Найдем такие С\ и с2> чтобы имело место

C\VÏ + CoVi = vu ^

C\V2 + c2v" = v2.

Тогда на основании лемм 1 и 2 C\V + c2V" даст нам последовательность У.

Ввиду условия (1.15) система уравнений (1.17) разрешима относительно С\ и с2, каковы бы ни были числа v\ и и2:

(Условие (1.15) означает, что общий знаменатель этих дробей отличен от нуля.) Подставив вычисленные значения С\ и с2 в (1.14), мы и получим требуемое представление последовательности V.

Значит, для описания всех решений уравнения (1.13) нам достаточно найти какие-нибудь два его непропорциональных решения.

Будем искать эти решения среди геометрических прогрессий. В соответствии с леммой 1 достаточно ограничиться рассмотрением только таких прогрессий, у которых первый член равен единице. Итак, возьмем прогрессию

1, <7, Я2, ...

Чтобы она была решением уравнения (1.13), необходимо, чтобы при всяком п выполнялось

дП-2 + qn-\ _ qnf

или, сокращая на qn~2y

\ + q = q2. (1.18)

Корни этого^ квадратного уравнения, т. е. 1 + У 5 i _ Уб _- и --—, и будут искомыми знаменателями прогрессий. Мы будем их обозначать соответственно через а и ß. Подчеркнем, что для чисел а и ß, как для корней уравнения (1.18), должно иметь место 1 + а = а2, 1 + ß = ß2 и aß = — 1.

Мы получили, таким образом, две геометрические прогрессии, являющиеся решениями уравнения (1.13). Поэтому все последовательности вида

ci + c2l cia + c2ß, cia2 + c2ß2, О-19)

являются решениями уравнения (1.13). Так как найденные нами прогрессии имеют разные знаменатели и потому непропорциональны, формула (1.19) при

различных ci и с2 дает нам все решения уравнения (1.13).

В частности, при некоторых с\ и с2 формула (1.19) должна дать нам и ряд Фибоначчи. Для этого, как указывалось выше, нужно определить С\ и с2 из уравнений

С\ + с2 = их

и

С\<Х + C2ß = "2,

т. е. из системы

Решив эту систему, мы получаем

откуда

т. е.

(1.20)

Формула (1.20) называется формулой Бине (по имени математика, который ее вывел).

Очевидно, подобные формулы можно указать и для других решений (1.13). Пусть читатель сделает это для последовательностей, приведенных в п. 2 Введения.

17. Мы видели, что а2 = а+ 1. Ясно поэтому, что любую целую положительную степень числа а можно представить в виде аа + b с целыми коэффициентами а и Ь. Так,

Покажем (по индукции), что

ап = ЫпЫ + ttrt-i.

Действительно, мы видим, что для п = 2, 3 это так, Предположим, что

ak — uka + Uk-u

Сложив эти равенства, мы получим

ak _|_ ak+i = (Uk _|_ Uk+l)a + (Uk-i + uk),

или

и индуктивный переход обоснован. Аналогично из ß2 = ß + 1 следует

ß" = Un$ + Un-\.

18. При помощи формулы Бине удобно вычислять различные суммы, связанные с числами Фибоначчи. Найдем, например, чему равна сумма

«з + tie + «9 + ... + "га-

Мы имеем

или, суммируя встретившиеся нам геометрические прогрессии,

Но

и аналогично ß3— 1 = 2ß. Поэтому

или, произведя сокращения,

19. В качестве следующего примера применения формулы Бине вычислим сумму кубов первых п чисел Фибоначчи. Заметим предварительно, что

Поэтому

или, пользуясь формулой (1.6) и результатами предыдущего пункта,

20. Уместно поставить вопрос о том, как быстро растут числа Фибоначчи при увеличении их номеров. Формула Бине дает нам достаточно исчерпывающий ответ и на этот вопрос.

Нетрудно доказать следующую теорему.

Теорема. Число Фибоначчи ип есть ближайшее ап целое число к —j=r, т. е. к п-му члену ап геометрической прогрессии, первый член которой есть —~% а знаменатель равен а.

Доказательство. Очевидно, нам достаточно установить, что абсолютная величина разности между ип и ап всегда меньше 4- • Но

Так как ß =—0,618 то |ß|<l, а значит, |ß|" < 1 при любом п, и тем более (так как д/5>2) должно быть ^L < —. Теорема доказана.

Читатель, знакомый с теорией пределов, легко сможет, несколько видоизменив доказательство этой теоремы, показать, что

lim \ ип — ап\ = 0.

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

Вычислим, например, («и, как легко сообразить, должно являться ответом задачи Фибоначчи о кроликах) :

Ближайшим целым числом к 376,9 является 377; это и есть «и.

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

В виде упражнения читатель может доказать, что в десятичной системе счисления ип при п ^ 17 имеет не более -~- и не менее — цифр. А из скольких цифр состоит wiooo?

21. Результат предыдущего пункта можно уточнить. Следующая теорема пригодится нам в дальнейшем. Теорема.

Доказательство. Мы ограничимся доказательством левой стороны неравенства: правая доказывается аналогично. Поскольку согласно формуле Бине

a aß = —1, для наших целей будет достаточно показать, что

или

a » ^а2Л- 1, пли, возводя в степень л,

a2«2-1 ^ (a2rt — 1)^ (1.21)

Будем доказывать это неравенство по индукции. При п = 1 оно превращается в

a ^ а2 - 1,

что действительно имеет место (именно, со знаком равенства). При п = 2 (1.21) означает

a7 (а4 - I)2. (1.22)

Это неравенство можно проверить и прямым вычислением. Однако его можно и доказать, воспользовавшись соотношением, выведенным в п. 17. В данном случае мы имеем

а4 = За + 2,

(а4 - 1)2 = (За + I)2 = 9а2 + 6а + 1 = 15а + 10,

и (1.22) переписывается как

а7 = 13а+ 8 ^ 15а + 10,

что очевидно. Наконец, при п = 3 (1.21) переписывается как

а17 ^ (а°- I)3,

что проверяется аналогично предыдущему.

Предположим теперь, что п > 2 и (1.21) имеет место, и докажем, что

a2(rt-M)2-l ^ (а2/г+2_

Для этого достаточно показать, что при увеличении п на единицу правая часть (1.21) растет быстрее левой части. Но левая часть, очевидно, возрастает в а4"+2 раз. Оценим увеличение правой части. Мы имеем

Последняя дробь больше, чем а2, и притом на

Следовательно, пользуясь формулой бинома (см., например, п. 11 § 1),

где точки стоят вместо положительных слагаемых.

Ввиду того, что п > 2, написанное выражение больше, чем а2п + 1. Значит,

и теорема доказана.

22. Рассмотрим еще один класс последовательностей, основанных на числах Фибоначчи. Пусть х— произвольное число. Вычислим сумму

Sn (х) = U{ X + U2X2 + . . . + ипХп.

Для этого воспользуемся прежде всего формулой Бине:

(1.23)

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

В соответствии со сказанным рассмотрим сначала случай, когда ах Ф 1 и §хф 1, т. е. когда х Ф ~ — = —ß и X ф = — а. В этих случаях, суммируя

в (1.23) геометрические прогрессии, мы получаем

или, выполняя естественные преобразования,

и далее —

Вспоминая, что мы имеем

и окончательно

(1.24)

В частности, полагая в этой формуле х — 1, мы получим

что соответствует сказанному в п. 1. При x = —1 имеем

(ср. формулу (1.6)).

Рассмотрим теперь оставшиеся «особые» случаи.

Пусть X — —~~ ß- Тогда в (1.23) каждый член

первой прогрессии равен единице, и сумма этой прогрессии равна п. Во второй же прогрессии знаменатель оказывается равным —ß2.

Таким образом,

Замечая, что

мы получаем окончательно

(1.25)

Наконец, пусть х = ^. В этом случае в (1.23)

единице равен знаменатель второй прогрессии, а знаменатель первой прогрессии равен —а2. Мы имеем

Аналогично предыдущему получаем

и в итоге

(1.26)

23. Посмотрим, как ведет себя сумма sn{x) при фиксированном х и неограниченно возрастающем я.

Переходя в равенстве (1.23) к пределу по п} мы получаем

Здесь под знаками двух последних пределов стоят суммы геометрических прогрессий. Поэтому сами пределы являются суммами соответствующих бесконечных геометрических прогрессий. Но, как известно, для того, чтобы можно было говорить о сумме бесконечной геометрической прогрессии, необходимо и достаточно, чтобы ее знаменатель по абсолютной величине был меньше единицы. В имеющихся у нас прогрессиях знаменатели равны ах и ßx. Здесь |a|>|ß|. Поэтому из |ax|<l следует |ßjt|<l. Таким образом, выполнение неравенства |ах|<1 будет обеспечивать существование всех интересующих нас в данный момент пределов. Итак, предел

lim sn(x) (1.27)

существует, если | х | < ~. Обозначим этот предел через s{x). Для его вычисления мы можем воспользоваться формулой (1.24).

Заметим для этого, что на основании сказанного В п. 20

Поэтому

Ввиду [а*[< 1 должно быть и \х\< 1, так что оба написанных предела равны нулю. По тем же причинам и

lim ип+{хп+{ = 0.

Следовательно, переходя в формуле (1.24) к пределу по п при неограниченном возрастании п, мы получаем

Найденный результат можно переписать в развернутом виде как

щх + и2х2 + ... +ипхп+ ... = —YZ—ï- (1-28)

Придавая переменной х те или иные значения, мы будем получать различные конкретные формулы. Например, полагая х = -j» обнаружим, что

2 i 22 "Г" • • • ~т~ 2^ i • • • — ^*

24. Формулу (1.28) можно получить также при помощи несколько иных рассуждений. Напишем

Ulx + u2x2 + ... +ипхп+ ... =s(x) (1.29) (помня при этом, что выражение s(x) имеет смысл лишь при IXI < ~) и умножим это равенство почленно на X и на х2:

щх2 + и2х3 + ... +ипхп+] + ... =xs(x), (1.30) тх3 + и2х4+ ... +мла;л+2+ ... =x2s(x). (1.31)

Вычитая из равенства (1.29) оба равенства (1.30) и (1.31), мы после приведения подобных членов получим

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

X = ( 1 — X — X2) s (х),

откуда и следует (1.28).

25. Говоря о числе Фибоначчи ип, мы пока все время предполагали, что его номер п является целым положительным числом. Однако основное рекуррентное соотношение, определяющее числа Фибоначчи, может быть записано и как

Un-2 = Un — Un-l. (1-32)

При этом оно будет служить для выражения чисел Фибоначчи с меньшими номерами через числа с большими.

Полагая последовательно в (1.32) п = 2, 1, О, —1, ..., мы можем вычислить

Uq = 0, U-i = 1, U-2 = —1, и_з = 2, ...

и вообще, как легко убедиться (пусть читатель убедится сам!),

U-n = (—l)n+lUn. (1.33)

Это простое выражение числа Фибоначчи с произвольным целым номером позволяет сводить все задачи о таких числах Фибоначчи к задачам об обычных числах Фибоначчи с натуральными номерами.

Например, для вычисления суммы п «первых назад» чисел Фибоначчи

и-\ + и-2 -К . •. Н достаточно переписать ее в соответствии с (1.33):

U\ — и2 + ... ;+( — \)n~lUn>

и вспомнить формулу (1.6):

и^ + и_2+ ... +"-rt=(-ir+Vi+ l=-r/_rt+1 + L

Опирающееся на основное рекуррентное соотношение индуктивное рассуждение о числах Фибоначчи типа переходов «от п и п + 1 к п + 2» можно в связи с соотношением (1.32) проводить по схеме «от п

и n—1 к n — 2». В частности, таким образом без труда доказывается для любых целых пят важная формула (1.8)

Un+m = tln-lUm ~f~ UnUm+l*

26. Основные уравнения для чисел аир: а"+2 = а" + ап+\

ß"+2 _ ßn + ßü+lf

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

Заметим в заключение, что и результат п. 17 можно (по индукции «назад») перенести на отрицательные значения номера:

а~п = и-па + и-п-и (1.34)

Это равенство переписывается как

(-1)лРл = (-1)Х| + (-1)Ч+1,

т. е.

ß*+i = ип+ф + Un,

Кроме того, (1.34) можно представить в виде а-п = (—1)п~1ипа + (—1)пип+и

т. е,

(—1)яа-я = Un+i — ипаг

или, иначе,

Jb±L-a = (-l)na-n-ï-. (1-35)

Un ип

27. Числа Фибоначчи могут составить основу своеобразной «фибоначчиевой» системы счисления, т. е., представления любого натурального числа а в виде некоторой последовательности «цифр» ф1ф2 ... qv. Эта последовательность может быть получена следующим (индуктивным!) образом.

Отнимем от заданного числа а = а0 наибольшее из не превосходящих его чисел Фибоначчи ип и, написав цифру ф1 = 1 и разность а\ = ао — иПу будем считать это первым шагом нашего построения.

Предположим, что k шагов построения уже выполнены, в результате чего появилась последовательность цифр

Ф1 ... ф*, (1.36)

состоящая из нулей и единиц, а также некоторое число ük. Тогда é+1-й шаг построения будет состоять в следующем: сравним число а* с числом Фибоначчи Un-k, и если окажется а*. < un-k, то припишем к последовательности (1.36) ф£+1 = 0 и фиксируем число CLk+i = ak, а если будет а* ^ un-k, то припишем (1.36) фй+1 = 1 и положим йк+\ = Q>k — Un-k- Мы выполним п—1 шагов этого процесса, в результате чего, очевидно, придем к п—1-членной последовательности (1.36) и числу = 0.

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

Окончательную соответствующую числу а последовательность (1.36) будем называть его фибонач* чаевой записью и обозначать через Ф(а). Составляющие Ф(а) нули и единицы назовем фибоначчиевыми цифрами числа а. Ясно, что если Ф(а) =ф1 ... фя_1,то

а = unq>\ + #Л-1ф2 + ... '+ «2фл-1. (137)

Поясним сказанное на примере. Пусть а = 19, Тогда

Таким образом,

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

Действительно, пусть в Ф(а) две единицы встречаются подряд после некоторого нуля: фА = 0, ф*+1 = = фй+2 = 1. Это значит, что

Но почленное сложение всех составляющих вторую строку соотношений дает нам

CLk-l = Un-k + Un-k-\ — Un-k+l,

что противоречит (1.38).

Значит, две единицы подряд могли бы встретиться в Ф(а) разве лишь в том случае, когда впереди них вовсе не было бы нулей, т. е. было бы cpi = ф2 = 1. Но тогда по определению процесса а\ = а0 — ип ^ ^ ип-\, так что

dp > Un -\- Un-\ = Un+l,

и ип не является наибольшим числом Фибоначчи, не превосходящим а.

Вместе с тем ограничение, заключающееся в отсутствии двух стоящих рядом единиц, оказывается уже достаточным: всякая последовательность из п— 1 нулей и единиц, начинающаяся с единицы и не содержащая двух единиц подряд, есть фибоначчиева запись Ф(а) некоторого числа а, для которого

Un Si а < un+\. (1.39)

В этом можно убедиться, воспользовавшись, например, результатом задачи о прыгуне из п. 6. Пусть имеется п — 1 клетка, по которым прыгун прыгает доступными для него способами (т. е. на соседнюю клетку или через клетку). После выполнения прыжков все клетки, в которых прыгун побывал, помечаются нулями, а остальные клетки — единицами. Так как всего возможно ип-\ способов выполнения прыжков, различных способов пометок будет тоже иЛ-ь

Если к каждой из них приписать впереди единицу, то мы получим запись, которая может быть фибоначчиевым значением для числа а, удовлетворяющего (1.38). Но таких чисел ровно ип-и и каждое из них должно иметь свою запись; поэтому каждой записи соответствует хотя бы одно число.

§ 2. ТЕОРЕТИКО-ЧИСЛОВЫЕ СВОЙСТВА ЧИСЕЛ ФИБОНАЧЧИ

1. Рассмотрим теперь некоторые свойства чисел Фибоначчи, касающиеся их делимости.

Теорема. Если п делится на m, то и ип делится на ит.

Доказательство. Пусть п делится на m, т. е. п = mk. Будем вести доказательство индукцией по

Для k = 1 n — m, так что в этом случае ип делится на Um очевидным образом. Предположим теперь, что Umk делится на ит, и рассмотрим um(k+\y Но Um(k+i) = Umk+m и на основании (1.8)

Um{k+l) = Umk-lUm + UmkUm+\-

Первое слагаемое правой части написанного равенства, очевидно, делится на ит. Второе же ее слагаемое кратно Umk, т. е., по индуктивному предположению, тоже делится на ит. Значит, на ит делится и их сумма, т. е. um(k+\)- Этим теорема доказана.

2. Возьмем теперь некоторое число т. Если существует хотя бы одно число Фибоначчи ип, делящееся на m, то таких делящихся на m чисел Фибоначчи можно найти сколь угодно много. Ими будут, кроме Un, например, числа и2п, иЪп, и±Пу ...

Интересно поэтому выяснить, можно ли по заданному числу m найти хотя бы одно делящееся на него число Фибоначчи. Оказывается, это сделать можно.

Пусть k обозначает остаток от деления k на т. Будем выписывать последовательность пар таких остатков от деления чисел Фибоначчи на m:

(fib U2>, <U2, Й3>, <ЙЗ, Й4>, - - - , <Лп, йп+\У, ... (2.1)

Если считать пары <аь Ь\) и (а2, Ь2} равными при а\ = а2 и Ь\ = Ь2, то число всех различных пар

остатков от деления на m равно m2. Поэтому если в последовательности (2.1) взять т2 + 1 первых членов, то среди них обязательно окажутся равные.

Пусть (йк, йк+\У — первая пара, которая повторится в последовательности (2.1). Покажем, что этой парой является пара <1, 1>. В самом деле, предположим обратное, т. е. что первой повторившейся парой окажется пара (ük,uk+\>, где k > 1. Найдем в (2.1) пару (üi,üi+i} (l>k), равную паре (uk,uk+i}. Так как = ui+i — щи Uk-i = Uk+i — Uk, a üi+i = ük+i и m — Uk, остатки от деления щ-\ и Uk-i на m также должны быть равны, т. е. т-\ = uk-i. Однако из этого следует, что и (uk-u ük> = <й/_ь üi}, а пара (йк-и йкУ встречается в последовательности (2.1) раньше, чем {uk, ûk+ù, и поэтому {uk, uk+\} не является первой повторившейся парой, что противоречит нашему предположению. Значит, предположение, что k > 1, неверно, а это означает, что k = 1.

Итак, <1, 1> есть первая повторившаяся в последовательности (2.1) пара. Пусть она повторилась на /-м месте (в соответствии с установленным ранее мы можем считать, что 1 < / < m2t+ 1), т. е.

<ш, ut+iy = <1, 1>.

Это значит, что и m и щ+\ при делении на m дают в остатках единицы. Значит, их разность делится на m нацело. Но

щ+\ — Ш = Ut—и

так что на m делится t—1-е число Фибоначчи.

Мы доказали, таким образом, следующую теорему. Теорема. Каково бы ни было целое число т, среди первых т2 — 1 чисел Фибоначчи найдется хотя бы одно, делящееся на т.

Заметим, что доказанная теорема не утверждает ничего о том, какое именно число Фибоначчи разделится на т. Она говорит только, что первое число Фибоначчи, делящееся на m, не должно быть особенно большим. Далее мы еще вернемся к этому вопросу.

Из того, что <1, 1> есть первая повторившаяся пара в последовательности (2.1), вытекает, что начиная

с tit, последовательность остатков повторяется как бы сначала. Это значит, что последовательность остатков оказывается периодической. Например, при m = 4 этот период в последовательности остатков будет следующим:

1, 1, 2, 3, 1, 0. (2.2)

Длина периода в данном случае равна 6. Таким образом, если число п имеет вид 6&+1, 6£ + 2 или 6k + 5, то ип при делении на 4 дает в остатке единицу, если п имеет вид 6k + 3, то 2, а если 6k + 4, то 3.

3. Большой интерес представляет вопрос об арифметической природе чисел Фибоначчи, об их делителях. Докажем, что при п составном и отличном от 4 ип есть составное число.

Действительно, для такого п можно написать п = п\п2, где 1 < п\ < л, 1 < п2 < п и либо п\ > 2, либо п2 > 2. Пусть для определенности г\\ > 2. Тогда ввиду только что доказанной теоремы ип делится на «яр причем 1 <. иП[< ип, а это и означает, что — составное число.

4. Прежде чем продолжать изучение чисел Фибоначчи, напомним читателю несколько простейших сведений из теории чисел.

Сначала укажем процесс нахождения наибольшего общего делителя чисел а и о.

Разделим а на b с остатком. Пусть при этом частное равно qo, а остаток г\. Очевидно,

а — bqo + n и 0 ^ Г\ < Ь.

Заметим, что при а < b будет qo = 0.

Разделим, далее, b на г\ и обозначим частное через qu а остаток через г2. Очевидно, b = r\q\+r2 и 0 r2 < ri. Так как г\ < 6, должно быть q\ Ф 0. Затем, разделив г\ на г2, найдем такие q2 Ф 0 и г3, что П = ^2^2 + гъ и 0 ^ г3 < г2. Будем поступать так до тех пор, пока этот процесс можно продолжать.

Рано или поздно наш процесс должен оборваться, так как все целые положительные числа п, г2, г3, ... различны, и каждое из них меньше Ь. Значит, число

их не превосходит 6, и процесс должен закончиться не позднее &-го шага. Оборваться же он может лишь на том, что некоторое деление окажется произведенным нацело, т. е. остаток окажется равным нулю, и дальше делить на него будет уже нельзя.

Описанный процесс носит название алгорифма Евклида. В результате его применения к числам а и b мы получаем такую последовательность равенств:

a = bqQ + ги b = r{q{ + r2, г, = r2q2 + r3,

• ••••• (2 • 3)

Г п-2 = r n-lQn-l + rn> rn-l — rnQn*

Рассмотрим последний отличный от нуля член в последовательности а, Ь> п, г2, ..., гп и именно его обозначим через гп. Разумеется, в частности, им может оказаться и число b (для единообразия можно положить b = г0). Очевидно,

тл—i делится на

гп. Возьмем теперь в (2.3) предпоследнее равенство. В правой его части оба слагаемых делятся на гЛ, а потому и Гп-2 делится на гп. Аналогичным образом убеждаемся последовательно (индукция!) в том, что на гп делятся гл-з, • • • и, наконец, b и а. Итак, гп является общим делителем а и Ь. Покажем, что гп есть наибольший общий делитель а и Ь. Для этого нам достаточно показать, что всякий общий делитель а и b будет делить и гп.

Пусть d — некоторый общий делитель а и 6. Из первого равенства (2.3) усматриваем, что d должно делить г\. Но тогда на основании второго равенства (2.3) d делит г2. Аналогично (индукция!) доказываем, что d делит г3, ..., гп-\ и, наконец, гп.

Мы доказали, таким образом, что алгорифм Евклида, примененный к натуральным числам а и Ь, действительно приводит к наибольшему общему делителю этих чисел. Этот наибольший делитель чисел а и b мы будем обозначать через (а, Ь).

Очевидно, а делится на b тогда и только тогда, когда (а, Ь) = 6,

В качестве примера найдем (и2<ь ^15) = (6765, 610):

6765 = 610- 11 +55, 610= 55 - 11 +5, 55= 5-11.

Итак,

(иго, "15) =5 = us.

То, что наибольшим общим делителем двух чисел Фибоначчи вновь оказалось число Фибоначчи, не случайно. В дальнейшем будет доказано, что так бывает всегда.

5. Процесс, аналогичный алгорифму Евклида, встречается в геометрии при нахождении общей меры двух соизмеримых отрезков. В самом деле, рассмотрим два отрезка: один длиной а и другой длиной Ъ. Вычтем из первого отрезка второй столько раз, сколько это возможно (если b > а, то, очевидно, мы этого не сможем сделать ни разу), и обозначим длину остатка через г\. Очевидно, г\ <С Ь. Вычтем теперь из отрезка длиной b отрезок длиной г\ столько раз, сколько возможно, и обозначим получившийся вновь остаток через г2. Поступая таким же образом дальше, мы получим последовательность остатков, длины которых, очевидно, убывают. До этого места сходство с алгорифмом Евклида, как мы видим, полное.

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

6. Установим несколько простых свойств наибольшего общего делителя двух чисел.

(а, be) делится на (a, ft). Действительно, Ъ, a потому и be, делится на (a, fe); а делится на (а, Ь) очевидным образом. Значит, по доказанному в п. 4 и (a, fee) делится на (а,&).

7. (ас, be) = (а, Ь)с.

Доказательство. Пусть равенство (2.3) описывают процесс нахождения (а,Ь). Умножив почленно каждое из этих равенств на с, мы, как легко проверить, получим систему равенств, соответствующую алгорифму Евклида, примененному к числам ас и be. Последний ненулевой остаток при этом будет равен гпс, т. е. (а, Ь)с.

8. Если (а, с)=1, то (a, be) = (а, 6), В самом деле, (at be) на основании п. 6 является делителем (ab, be). Но

(аб, 6с) = (а, с)Ь = Ь6 = b

ввиду п. 7. Таким образом, b делится на (a, 6с)« С другой стороны, (а, fee) есть делитель а. Значит, (a, be) ввиду доказанного в п. 4 делит и (a, 6). А так как по п. 6 и (а, Ь) делит (а, 6с), мы получаем (а, 6) = (а, 6с).

Пусть 6с делится на а. Это значит, что (а, 6с) = а. Если при этом (а, с) = 1, то по предыдущему (а, 6) = = а, т. е. 6 делится на а.

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

9. В качестве примера, который будет полезен в дальнейшем, рассмотрим один из вопросов о делимости биномиальных коэффициентов.

Теорема. Если р — простое, акф§иЬ,Фр, то С% делится на р.

Доказательство. Согласно сказанному в п. 14 § 1

Р Ь2. ... • *

Так как в действительности эта дробь равна целому числу, ее числитель должен делиться на знаменатель. Но каждый из сомножителей знаменателя меньше, чем р, и потому на р не делится. Следовательно, так как р — простое, по предыдущему на р не делится и их произведение, т. е. весь знаменатель. Значит, знаменатель взаимно прост с р.

Рассмотрим числитель дроби как произведение двух чисел р и (р—1) ... (р — k+l). Это произведение делится на знаменатель. Так как р взаимно просто со знаменателем, на него делится второй сомножитель: (р—1 ) ... (р — £+1). Пусть (р — — 1) ... (р — k+ 1)= M-2- ... -k. Тогда С£= tp, а это и требовалось.

10. Если с делится на 6, то (а, 6) = (а + с, 6).

Доказательство. Пусть применение алгорифма Евклида к числам а и 6 приводит к системе равенств (2.3), Применим этот алгорифм к числам

а + с и Ь. Так как с делится на b по условию, то мы можем положить с = С\Ь\ первый шаг алгорифма дает нам равенство

a + c = (q0 + ci)b + n.

Все дальнейшие шаги этого алгорифма дадут нам последовательно второе, третье и т. д. равенства системы (2.3). Последним отличным от нуля остатком по-прежнему является rn, а это и значит, что (а, 6)=» = (а + с,Ь).

Полезным упражнением для читателя будет доказательство этой теоремы только на основании результатов пп. 6—8, т. е. без повторного обращения к понятию алгорифма Евклида и системе (2.3).

11. Теорема. Соседние числа Фибоначчи взаимно просты.

Доказательство. Пусть вопреки утверждению теоремы ип и ип+\ имеют некоторый общий делитель d> 1. Тогда и их разность ип+\— ип будет делиться на d. А так как ип+\ — ип = ип-и на d должно делиться и ип-\. Аналогично показываем (индукция!), что на d будут делиться и ип-2, и ип-г, и т. д. и, наконец, u\. Но ai=l9 и поэтому на d > 1 делиться не может. Полученное противоречие доказывает теорему.

12. Теорема. Имеет место равенство

{Um, Un) = Щщ, п)•

Доказательство. Пусть для определенности m > п. Применим к числам шип алгорифм Евклида:

Как нам уже известно, п есть наибольший общий делитель m и п.

Итак, m = nqo + г\\ значит,

или

fan. Un) = {Unq*-\Urx + Unq0Uri+U tln)f

или, на основании пп. 1 и 10,

("m> Un) = {unqa-lUri> Un\

или ввиду пп. 11 и 8

("m» Un) = (urii Un).

Аналогично доказываем, что

Сопоставляя все эти равенства, получаем

а так как rt-\ делится на г/, так что и Urt_x делится на Urt, должно быть {tirv urt-x)—urt- Замечая, наконец, что п = {т,п), мы получаем требуемое.

В частности, из только что доказанного следует теорема, обратная теореме п. 1: если ип делится на «m, то п делится на т. В самом деле, если ип делится на ит, то, как отмечалось в п. 4,

(Un, Um) = Um. (2.4)

Но, по доказанному,

(Un, Um)= Щп,т). (2.5)

Сопоставляя формулы (2.4) и (2.5), мы получаем

Um = li(n, m),

т. е. m = (n, m), a это и означает, что п делится на m.

13. Объединяя теорему п. 1 и следствие теоремы п. 12, мы имеем: ип делится на ит тогда и только тогда, когда п делится на т.

Ввиду этого о делимости чисел Фибоначчи можно судить, рассматривая делимость их номеров.

Найдем, например, несколько «признаков делимости» чисел Фибоначчи. Под признаком делимости мы понимаем здесь признак, по которому можно определить, делится или нет то или иное число Фибоначчи на некоторое данное число, д

Число Фибоначчи четно тогда и только тогда, когда его номер делится на 3.

Число Фибоначчи делится на 3 тогда и только тогда, когда его номер делится на 4.

Число Фибоначчи делится на 4 тогда и только тогда, когда его номер делится на 6.

Число Фибоначчи делится на 5 тогда и только тогда, когда его номер делится на 5.

Число Фибоначчи делится на 7 тогда и только тогда, когда его номер делится на 8.

Число Фибоначчи делится на 16 тогда и только тогда, когда его номер делится на 12.

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

Пусть заодно читатель докажет, что не существует чисел Фибоначчи, дающих при делении на 8 в остатке 4, а также, что нет нечетных чисел Фибоначчи, делящихся на 17.

14. На протяжении этого параграфа нам часто придется высказывать суждения типа «числа а и b при делении на m дают один и тот же остаток», или, что, в сущности, то же самое, «разность а — b делится на m».

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

Определение. Числа a u b называются сравнимыми по модулю m, если при делении на m числа а и b один и тот же остаток, или если а — b делится на т. Сравнимость а и b по модулю m записывается как

а = b(mod m). Очевидно, если а делится на т, то

а = 0(mod m),

и наоборот.

15. Сравнения по одному и тому же модулю можно подобно равенствам почленно складывать. Лемма. Если

Доказательство. Из условия следует, что на m делится каждая из разностей

а{ — Ьи ci2 — b2, ., ап — bn,

а потому и их сумма:

(ах — Ьх) + (а2 — Ь2) + ... + (я« — Ьп),

т. е. разность

(ai + а2 + •.. + ап) — (Ь{ + Ь2 + •. • + &„)•

Это и означает требуемое сравнение.

16. В п. 9 мы установили, что при простом р и 0 < k < р

СрзО (mod р). (2.6)

Это можно записать также как

С£+1 г O(modp) (2.7)

при 0 ^ £ < р— 1.

Значит, при 0 < k < р — 1 справедливы оба сравнения (2.6) и (2.7). Сложив их, мы получим

с£ + С*+1^ 0 (mod р),

или

C^J^O(modp).

Иными словами, при простом р в р + 1-й строке треугольника Паскаля все члены, кроме четырех (по два крайних справа и слева), делятся на р.

Нетрудно проверить также, что

С°р+1 - Схр+1 - С£+1 - С£+! - 1 (mod р).

17. Сравнение (2.6) можно переписать как

Это имеет место при любом k = Т, 2.....р— 1. Значит,

— — Cpi, -с£_,--с£_,- ...-C£:{(inodp).

Так как Ср—1 = 1, последнее сравнение означает, что члены р-~\-й строки треугольника Паскаля с нечетными номерами сравнимы по модулю р с 1, а члены с четными номерами с — 1.

18. Сравнения по одному и тому же модулю можно не только почленно складывать, но и почленно перемножать.

Лемма. Если

ai = bi (mod m),

a2 ss b2 (mod m), ^ 3)

an s 6n (mod m),

aia2 ... art s= 6^2 ... bn (mod m). (2.9)

Доказательство будем вести индукцией по п. При п = 1 лемма тривиальна.

Предположим, что для некоторого п лемма верна (т. е. что из (2.8) следует (2.9)), и присоединим к ее условиям сравнение

ап+х = Ьп+1 (mod m). (2.10)

Сравнения (2.9) и (2.10) соответственно означают, что разности а{а2... аа — b\b2.. .Ьп и ап+\ — Ьп+\ делятся на т. Следовательно,

а{а2 ... ап = bxb2 ... bn + тТ9 fl/i+i = bn+i +mt,

где Tut — целые числа. Перемножая полученные равенства, мы имеем

aia2 ... ап ап+\ = Ьф2 ... bnbn+{ +

+ m (b\b2 ... bnt + bn+{T + mTt).

Справа в скобках стоит целое число, поэтому

а{а2 ••• апап+\ = b\b2 ,.. ЬпЬп+\ (mod m),

а это и требовалось.

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

Как тривиальный частный случай можно получить следующий факт: произведение чисел вида 4/ + 1 тоже имеет вид 4/+1« В самом деле, пусть аь а2, ..., ап — данные числа.

По условию,

а{ = 1 (mod 4), а2 == 1 (mod 4), «>м ап а 1 ( mod 4). Перемножая эти сравнения, мы получим, что ûiû2 ... ап ss 1 (mod 4).

19. Правила сокращения сравнений также подобны правилам сокращения равенств: равенства можно сокращать на любое число, отличное от нуля, а сравнения — на любое число, взаимно простое с модулем.

Лемма. Если

ас s be (mod m), (2.11)

причем (с, m) = 1, то

а н= b (mod m). (2.12)

Доказательство. Сравнение (2.11) означает, что разность ас — be делится на пг. Но

ас — be = (а — Ь) с,

а так как (с, т) = 1, на m должна делиться разность а — Ь, что и означает (2.12).

20. Во многих вопросах оказывается полезным следующее утверждение, называемое «малой теоремой Ферма».

Теорема. Если р — простое число, и а не делится на р,

то

ар-1 ез l(mod р).

Доказательство. Рассмотрим числа

а, 2а, (р- 1)а. (2.13)

Никакие два из них не сравнимы по модулю р. Действительно, из

ka = la (mod р) ввиду (а, р) = 1 по п. 19 следовало бы, что

k = / (mod р),

т. е. что k — / делится на р, чего при 0 < £, I < р и k Ф I быть не может.

Кроме того, ни одно из рассматриваемых чисел ке делится на р.

Значит, все числа (2.13) при делении на р дают различные остатки г и г2, ..., гр-\, каждый из которых отличен от нуля. Но чисел (2.13) р—1 штук, а ненулевых остатков от деления на р тоже р — 1 штук, и все они различны. Следовательно, при делении чисел (2.13) на р с остатком (т. е. среди чисел г\, г2, ...

Гр-i) каждый из остатков 1, 2, р—1 встретится ровно по одному разу. Итак, мы имеем

а n (mod р), 2а = г2 (mod р),

(р — 1) а = гр-х (mod р). Перемножая все эти сравнения почленно, мы получаем

1.2 ..... (р - 1) а**-1 = г{г2 ... Гр-i (mod р). (2.14)

Но, как уже было замечено, числа гь г2, гр-{—это те же числа 1, 2, р—1, только выписанные в каком-то ином порядке. Следовательно, сравнение (2.14) можно переписать как

1.2..... (р - 1) a*»-» в 1 .2 • .... (р - 1) (mod р). (2.15)

Заметим, наконец, что произведение 1-2- ... -(р — 1) взаимно просто с р, и потому в сравнении (2.15) можно произвести сокращение:

аР-х == 1 (mod р),

что и требовалось.

21. Из сказанного в п. 2 следует, что среди делителей чисел Фибоначчи имеются все вообще числа. Сейчас мы убедимся в том, что можно выделить некоторые классы чисел Фибоначчи, обладающие делителями довольно конкретного вида.

Например, имеет место следующая теорема*):

Теорема. Если число Фибоначчи имеет нечетный номер, то все его нечетные делители имеют вид 4^+1.

Доказательство. Формула (1.10) (см. п. 9 § 1) в случае нечетного п дает нам

откуда

"Л_1 ип+{ - и\ = ип_{ (ил_! + ип) - и\ —

-«î-l + ««-i«n-«£--l. (2.16)

Пусть р — простой делитель ип, причем р ф 2. Из (2.16) следует, что u^_i + \ делится на ип> и потому на р. Следовательно,

— —1 (mod Р)-

Возводя почленно это сравнение в степень —^—» мы получим ^ ^

(4-.)^=<:i-(-i)£^(tnodp).

Далее, (ип-и ип) = 1, так что ип-\ не делится на р, и мы оказываемся в условиях «малой теоремы Ферма», согласно которой

«gl} - 1 (mod р).

Но тогда и

*) Автор признателен ленинградскому любителю чисел Фибоначчи тов. Фрейштадту, обратившему его внимание на этот факт.

т. е. (—1) ~ = 1. Следовательно, число ^--четное, а это означает, что р имеет вид 4/ + 1.

Итак, все простые нечетные делители ип имеют вид At + 1. Следовательно, ввиду сказанного в конце п. 18, такой же вид должны иметь и все их произведения, т. е. все вообще (см. п. 5 § 1) нечетные делители ип.

22. Согласно определению сравнения все числа, дающие при делении на m один и тот же остаток, сравнимы между собой по модулю т. Наоборот, если числа при делении на m дают различные остатки, то они несравнимы.

Остатком от деления на m может быть одно из m чисел: 1, 2, m — 1. Следовательно, несравнимых друг с другом по модулю m чисел может быть не более, чем т.

Пусть m нечетно; возьмем числа

m — 1 /п — З m — 3 m — 1

— 2 , 2 » ü' *• Z' 2 ' 2 *

(2.17)

Этих чисел m штук, и никакие два из них не сравнимы по модулю m (иначе их разность, которая по абсолютной величине меньше, чем m, и отлична от нуля, делилась бы на m). Следовательно, каждое число сравнимо по модулю m с одним из чисел списка (2.17). Числа (2.17) называются абсолютно наименьшими вычетами по модулю т. Очевидно, абсолютная величина каждого из абсолютно наименьших вычетов меньше половины модуля.

Заметим, что систему абсолютно наименьших вычетов можно построить и для четного т. Она будет выглядеть несколько иначе, чем (2.17):

m — 2 m —4 1 . m —2 m

2 ' 2 ' ~~ ' ' ' 2 ■ ~2~'

Система абсолютно наименьших вычетов для четных m нам не будет нужна.

23. Пусть m — нечетное число, не делящееся на 5. Составим последовательность абсолютно наименьших вычетов по модулю m чисел 5, 2 • 5, 3 • 5, ..., — ^ - » 5. Например, при m = 21 этой последовательностью будет

5, ю, _6, —1, 4, 9, —7, —2, 3, 8.

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

Лемма. Если m = 10^+1, то последовательность абсолютно наименьших вычетов устроена следующим образом:

t положительных, t отрицательных, t положительных, t отрицательных, t положительных^

Если m=10/ + 3, то схема чередования знаков будет такой:

t положительных, t отрицательных, t положительных, / + 1 отрицательных, t положительных.

Если пг= 10/ + 7, то в последовательности будет t положительных, t + 1 отрицательных, / + 1 положительных, t отрицательных, t + 1 положительных.

Если m = 10/ + 9, то мы получим t положительных, t -f 1 отрицательных, t + 1 положительных, t + 1 отрицательных, t -j- 1 положительных.

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

Итак, пусть пг = 10/+ 1. Очевидно, что k ^ t будет 5k <2 < (т.— 1)/2, так что все такие числа bk уже являются абсолютно наименьшими вычетами по модулю т. Количество их равно /, а последним будет 5/. Так как 5(/ +1) > (т — 1)/2, следующий абсолютно наименьший вычет будет отрицательным (он будет равен —5/+ 4). Прибавляя к нему последовательно одну за другой / — 1 пятерок, мы получим всего серию из / отрицательных чисел, которая заканчивается на —1. Затем будет положительное 4, а за ним — еще / — 1 положительных чисел (т. е. до 4 + -\- (/— 1 ) • 5 = 5/—1 включительно), после чего снова появляются отрицательные числа (от —5/+ 3 до —2; всего / штук). Наконец, от 3 до 5/ — 2 мы получаем завершающие / положительных членов последовательности.

Этим требуемое доказано.

В сущности, основным итогом этой леммы для нас будет то обстоятельство, что при т=10/±1 в последовательности абсолютно наименьших вычетов имеется четное число отрицательных членов, а при m = 10/ ± 3 — нечетное.

24. Лемма*). Если р — простое число вида 5/±1, то 5(Р-0/2 _ j делится на р.

Если р — простое число вида 5/± 2, то 5*р_1)/2+1 делится на р.

Доказательство. Мы имеем

где 8*га — абсолютно наименьший вычет k-5 по модулю р, причем Гк > 0, а е* = ±1 и указывает на знак вычета.

*) Эта лемма является частным случаем важной теоретико-числовой теоремы, называемой законом взаимности квадратичных вычетов.

Перемножая все эти сравнения, мы получаем

(2.18)

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

Каждое из положительных чисел гь г2, ..г { не превосходит числа —-—•

Если бы среди этих чисел нашлись одинаковые: rk = , то было бы 5k гз ±5/(mod р)> а ввиду того, что (5, р) = 1, и k = zfc/(modp). Но этого не может быть, так как —р < k — / < k + I < р и k — / Ф 0. Следовательно, все числа гь г2, ..., г j различны. Значит, этими числами будут 1,2, ..-i"^2—• Расположенные в некотором порядке. Все они взаимно просты с модулем, и поэтому мы можем сравнение (2.18) сократить на произведение 1 • 2 ^—^—. В результате мы получаем 5 2 = 6182.. .е р_х (mod р).

Согласно лемме п. 23 в произведении Eie2 ... 8p_i число сомножителей, равных —1, четно при р= 10/+1 (ввиду нечетности р это равносильно тому, что р имеет вид 5/±1) и нечетно при р = 10/ zb 3 (т. е. р имеет вид 5/ dh 2).

Отсюда непосредственно получаются оба утверждения леммы.

25. Теперь мы можем доказать основное свойство делимости чисел Фибоначчи на простое число.

Теорема. Если простое число р имеет вид 5/±1, то ир-х делится на р. Если р имеет вид 5/ ±2, то ир+х делится на р.

Доказательство. Пусть р имеет вид 5/±1. По формуле Бине мы имеем

или, после очевидных упрощений,

В силу сказанного в п. 17 все перечисленные здесь биномиальные коэффициенты сравнимы по модулю р с —1. Поэтому

Суммируя встретившуюся нам геометрическую прогрессию и учитывая, что 2Р~1 по модулю р сравнимо с единицей, получим

Но по предыдущему числитель стоящей справа дроби делится на р. Так как (р, 2) = 1, и вся дробь делится на р. Значит, и ир-\ делится на р, так что первое утверждение теоремы доказано.

Обратимся к случаю, когда р имеет вид Ы ± 2. Тогда, применяя, как и выше, формулу Бине, мы получим

По п. 16 все члены в скобках, кроме двух крайних, делятся на р* а Ср+1=С£+1 при делении на р дает в остатке единицу. Поэтому

Применение в данном случае предыдущей леммы дает нам, что Ир+1 делится на р.

26. Пусть ип делится на некоторое простое число р, причем ни одно из чисел Фибоначчи, меньших ип, не делится на р. В этом случае мы будем называть число р собственным делителем ип. Например, 11 есть собственный делитель Кщ, 17 — собственный делитель и$ и т. д.

Оказывается, что всякое число Фибоначчи, кроме щ, «2» "в и ип, обладает хотя бы одним собственным делителем.

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

27. Начнем с некоторых общих теоретико-числовых соображений.

Установленный нами в п. 8 важный факт о делимости произведения на простое число позволяет доказать теорему, которая иногда называется «основной теоремой арифметики».

Теорема. Всякое натуральное число разлагается на простые множители лишь одним способом.

Доказательство. Заметим прежде всего, что возможность такого разложения является весьма простым фактом и была установлена нами еще в п. 5 § 1 при помощи непосредственного индуктивного рассуждения.

Для доказательства единственности разложения рассмотрим два возможных разложения числа а на простые множители:

PlP2..-Pk*=ci = qiq2...ql.

Будем для определенности считать, что k ^ /. Здесь правая часть должна делиться на рь Поэтому согласно сказанному в п. 8 на р\ должен делиться хотя бы один из входящих в нее сомножителей. Пусть, для определенности, q\ делится на р\. Так как число Ц\ простое, это возможно лишь при р\ = q\. Произведя сокращение, мы получим

Р2« —?2"-?Г

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

\=qk+v..ql.

Но последнее возможно лишь при qk+i = ... = qi = 1, т. е. простые сомножители qk+i, qi должны отсутствовать. Теорема доказана.

28. Объединяя в разложении а на простые сомножители все одинаковые сомножители в степени, мы получим

« = р№...р°*. (2.19)

Это представление натурального числа а называется его каноническим разложением.

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

29. Как легко проверить, для того чтобы число а с каноническим разложением (2.19) делилось на

6-pf'pf*...pi*. (2.20)

необходимо и достаточно, чтобы было

Pi — av h = а2.....ßfc = ak-

(В частности, если некоторое се/ = 0, то должно быть и ß* = 0.)

Теперь мы можем по-новому описать наибольший общий делитель двух или нескольких чисел.

Пусть au а2, ..., ап — произвольный набор натуральных чисел, и pit pk — все такие простые числа, что каждое из них

является делителем хотя бы одного из чисел au а2, ..., ап. Напишем канонические разложения для аи а2, ..., ап:

(2.21)

(здесь все показатели а// ^ 0). Очевидно, всякий общий делитель d чисел ai, ..., ап может иметь в своем каноническом разложении лишь простые множители из числа ри ..., pk:

При этом каждый показатель ôt не должен превосходить каждого из соответствующих ему показателей ац, a2i, ая/, входящих в разложения аь а2, ..., ал при рг.

ai ^ ai/, at ^ а2/, ..., ôt ^ anî. (2.22)

Если этот общий делитель d является наибольшим общим делителем, то показатели о/ должны быть наибольшими из всех чисел, удовлетворяющих соответствующим неравенствам (2.22). Но это значит, что каждое о/ должно быть просто наименьшим из соответствующего набора чисел au, a2i, ..., аЛ/. Это можно записать так:

ôi = min{a,jf a2i, ani}.

Наибольший общий делитель чисел ai, а2, ..., ап обозначается, как и в случае двух чисел, через (аь а2,

30. В некотором смысле двойственным к понятию наибольшего общего делителя является понятие наименьшего общего кратного.

Очевидно, всякое число, делящееся на числа а\, а2, ..., ап с каноническими разложениями (2.21), должно иметь в своем каноническом разложении все простые сомножители, входящие хотя бы в одно из разложений (2.21), т. е. числа р\, р2, pk. Кроме того, в каноническое разложение общего кратного могут входить еще какие-либо «посторонние» множители. Таким образом, каноническое разложение всякого общего кратного m чисел а\, а2, ... ,,., ап должно иметь вид

m=splilp\i2 ялл p»kQt

где через Q обозначено произведение всех «посторонних» простых множителей. При этом, очевидно, для любого i = 1, k должно быть

Vi ^ ац, \ii ^ а2{, ..., щ ^ ani. (2.23)

Если m является наименьшим общим кратным чисел а\, а2, ..., ап, то, очевидно, множитель Q должен отсутствовать совсем (т. е. он должен быть равен единице), а все показатели ^

должны быть наименьшими из тех, которые удовлетворяют неравенствам (2.23). Но последнее означает, что каждое Ц/ должно быть просто наибольшим числом среди au, а2/, .. •, Q>m:

max {au, a2;, ani).

Наименьшее общее кратное чисел аи а2у ..., ап обозначается через [аи а2у ..., ап].

31. Докажем вспомогательную лемму.

Лемма. Каковы бы ни были числа ai, a2, ..., a*,

(2.24)

(здесь во второй строке стоят все минимумы из двух чисел, в третьей — все минимумы из трех и т. д.).

Доказательство. Не нарушая общности, мы можем с самого начала считать, что числа аь а2, ..., ап расположены в порядке невозрастания:

ai ^ a2 ^ ... ^ ап.

Тогда

max {аь а2, ап] = ai.

Вычислим значение левой части (2.24). Подсчитаем для этого, сколько раз (алгебраически) входит в нее каждое из чисел ai, a2, ..., an. При этом в случае равенства двух чисел а/ и а/ мы будем в качестве минимального писать то, которое имеет больший номер (очевидно, это чисто формальное соглашение не влияет на величины рассматриваемых нами выражений).

Заметим сначала, что ai является самым большим из рассматриваемых нами чисел. Поэтому оно входит только в первую строку правой части (2.24) и притом ровно один раз. Значит, в правой части (2.24) коэффициент при ai равен единице.

Рассмотрим теперь вхождение в правую часть (2.24) некоторого ai (i > 1). В первую строку оно войдет один раз. Во вторую и последующие строки до i-й включительно оно войдет лишь от тех минимумов, в которых вместе с ai стоит сочетание чисел с номерами, меньшими, чем L Для каждой /-й строки (/ ^ /) число таких вхождений будет равно числу сочетаний из i — 1 чисел аь a/-i по /— 1, т. е. c[z\ (см. п. 14 § 1). Общее число вхождений а/, таким образом, будет равно

На основании п. 13 § 1 это выражение равно нулю.

Следовательно, правая часть (2.24) равна ai, т. е. левой части, и лемма доказана.

32. Воспользуемся доказанным для удобного описания наименьшего общего кратного нескольких чисел.

Теорема.

(2.25)

(2.27)

(Здесь в числителе стоит произведение исходных чисел, наибольших общих делителей всевозможных их троек, пятерок и т. д., а в знаменателе — произведение всех наибольших общих делителей пар исходных чисел, их четверок и т. д.)

Доказательство. Пусть р — произвольный простой сомножитель, входящий в канонические разложения некоторых из ai, ü2, ..., ап. Обозначим через щ показатель, с которым р входит в каноническое разложение ai. Тогда в левую часть (2.25) он согласно п. 30 войдет с показателем

max {аь а2, ап}> (2.26)

a в правую согласно п. 29 — с показателем

На основании же предыдущей леммы выражения (2.26) и (2.27) равны друг другу.

Таким образом, в канонических разложениях правой и левой частей (2.25) имеются одни и те же простые сомножители и входят они с одними и теми же показателями.

33. Вернемся к изучению делимости чисел Фибоначчи.

Лемма.

umn-l — делится на и2п. (2.28)

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

При m = 1 делимое обращается в нуль, и потому делится на и2п. Предположим теперь, что делимость (2.28) справедлива, и рассмотрим

и{т+{) л_г - nJJi1 = (и,™-!",,-! + итпип) - ißji1. Но по индуктивному предположению

Следовательно,

«(«+!) .-1 - <-! - «Î-A.-1 + «т„"« - «C-V (mod и\). (2.29) Как вытекает из п. 1, umn делится на ип\ поэтому

и (2.29) превращается в

Индуктивный переход обоснован; теорема доказана. 34. Лемма.

(2.30)

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

При m = 1 делимое обращается в нуль и поэтому делится на и\.

Предположим, что делимость (2.30) имеет место, и рассмотрим

Но по индуктивному предположению

Следовательно,

или

или

о

По предыдущему стоящая справа разность делится на Поэтому вся правая часть делится на и3п> т. е. сравнима с нулем по модулю unj а это и требовалось.

35. Пусть р — простое число. Как показано в п. 1, иПр делится на Un. Поэтому при переходе от ип к ипр, во-первых, могут появиться новые простые делители, а, во-вторых, могут повышаться показатели при старых простых делителях члена ип. Мы докажем сейчас теорему, из которой будет следовать, что из всех простых делителей ип показатель может повыситься разве лишь у р. Если р Ф 2, то показатель при р увеличивается лишь на единицу, а если р — 2, то не более, чем на 2.

Теорема. Если q — простой делитель ип% отличный от р, то - не делится на q.

Если р — простой нечетный делитель ип, то —— делится на р, но не делится на р2.

Если ип делится на 4, то- делится на 2, но не делится на 4.

Если ип делится на 2, но не делится на 4, то -^2. делится на 4, но не делится на 8.

Доказательство. Полагая в предыдущей лемме m = = р, мы получим, что ипр - ип+\ + ип-\ Делится на и% Но иПр делится на ип согласно п. 1, а

Следовательно, разность

(2.31)

делится на ип.

Во-первых, отсюда следует, что разность (2.31) делится на ип. Это значит, что

(2.32)

Но, очевидно,

"/г-н = "л-1 (mod ип). Поэтому из (2.32) следует, что

Так как справа имеется р слагаемых, должно быть

Следовательно, всякий общий делитель чисел-и ип должен делить также р, и наоборот. Это значит, что

Если теперь q — простой делитель ип, отличный от р, то (Р, Un), равный 1 или рх не делится на q.

Следовательно, и 1-, ип i, равный 1 или р, тоже не делится на q. Но так как ип делится на q, на него не может делиться -, и первая часть теоремы доказана.

Во-вторых, если р— делитель ип, то из делимости разности (2.31) на следует, что

Разделим un+i и ип-\ дважды последовательно на р с остатком. Пусть

ип+\ = rxp + r' (modp2), ип-1 = r2p + r" (mod p2),

где 0 ^ гь г2, r', r" < р (поскольку разность un+i — ип-\ равна ип, т. е. делится на р, остатки г' и г" должны быть равны; положим поэтому г' = г" = г); при этом г =^= 0, так как ни м„-ь ни Un+i на р не делятся). Тогда

Раскроем справа скобки и отбросим слагаемые, делящиеся на р2, k-й член

(riP + r)p-k(r2p + r)k-1

даст нам при этом

или

Суммируя это выражение по всем членам, т. е. по k = 1, ..., pt мы получим

(2.33)

Если р Ф 2, то - 2 1 является целым числом. Поэтому

первые два слагаемых в (2.33) справа делятся на р2, и мы получаем

Наконец, по малой теореме Ферма (см. п. 20) гр~1 — 1 делится на р, и, значит, ргР~1 — р делится на р2. Учитывая это, мы окончательно получаем

—— =2 р (mod р2). ип

Таким образом, при делении на р2 дает в остатке р, т. е. делится на р, но не делится на р2, и мы доказали вторую часть теоремы.

Пусть теперь р = 2. Тогда (2.33) можно переписать как ±VL в 2 (г, + г2 + г) (mod 4). (2.34)

Если Нл делится на 4, то из последовательности остатков (2.2) видно, что в этом случае как ип-и так и ип+\ при делении на 4 дают в остатке 1. Следовательно, в этом случае г\ = г2 = 0, а г = 1, и (2.34) превращается в

-^^2 (mod 4).

Это доказывает третью часть теоремы.

Наконец, пусть ип не делится на 4. Последовательность (2.2) показывает, что теперь г\ = 1, г2 = 0 и г = 1. Поэтому (2.34) превращается в ^isO (mod 4). Нам остается показать, что -^2-^- не делится на 8. Но если бы это было так, то член и2п делился бы на 16. Но тогда согласно сказанному в п. 13 2п должно делиться на 12, т. е. п должно делиться на 6. Но отсюда в свою очередь следует, что ип должно делиться на w6, т. е. на 8, а это противоречит предположенному (именно тому, что ип не делится даже на 4). Теорема доказана полностью.

36. Теперь мы можем непосредственно заняться доказательством существования собственных делителей у чисел Фибоначчи.

Теорема. Всякое число Фибоначчи, за исключением ии «2, «6 и м!2, имеет хотя бы один собственный делитель.

Доказательство. Рассмотрим число Фибоначчи ип. Пусть каноническое разложение числа п будет n = p«ip«2 ... рЧч Возьмем все числа Фибоначчи

(2.35)

и составим их наименьшее общее кратное М. Согласно п. 32

Но при любых г и различных iu 1г, и

Поэтому

Но Un делится на все числа ип,ип,...,ип, а потому и на их наименьшее общее кратное М:

ип = Ш.

Всякий простой делитель M делит одно из чисел (2.35) и потому является несобственным делителем ип. Следовательно, все собственные делители ип должны делить Согласно теореме п. 35 из простых несобственных делителей ип в / могут входить разве лишь рь р2у ..., pk, причем каждое из этих чисел входит в t с показателем, не большим единицы, за исключением двойки, которая может входить с показателем 2.

Доказав неравенство

(крестик под двойкой здесь и далее означает, что эта двойка фактически присутствует лишь в том случае, когда среди чисел Pu р2, Pk уже имеется одна двойка), мы установим существование собственных делителей у числа Фибоначчи ип. Итак, докажем, что

В п. 21 § 1 было показано, что

Поэтому если все числа Фибоначчи в числителе дроби заменить на —-=га п , а в знаменателе — на —т=-а п > то дробь только уменьшится. Доказав требуемое неравенство для новой дроби, мы установим даже несколько больше, чем нужно.

Выполнив указанные замены и произведя сокращение на

, мы получим

или

или

или, логарифмируя

Вспоминая каноническое разложение числа л, мы можем это неравенство переписать как

Выражение p*i • р\к (Pk"~ 1) принято обозначать через <р(л).Эта функция ф называется функцией Эйлера, Она обладает многими важными и интересными свойствами.

Введя обозначение функции Эйлера, мы получим

Нам осталось проверить, для каких целых положительных значений п написанное неравенство выполняется. Мы будем эти значения называть «хорошими», в отличие от «плохих», для которых (2.36) не имеет места. Очевидно, для хороших значений п числа Фибоначчи ип будут иметь собственные делители. Подчеркнем, что обратное может и не иметь места: справедливость неравенства (2.36) есть лишь достаточное, но отнюдь не необходимое условие наличия у ип собственных делителей. Поэтому числа Фибоначчи с плохими номерами (а их наберется 10 штук) будут подлежать дополнительной проверке на наличие собственных делителей. В результате этой проверки окажется, что шесть чисел из этого десятка обладают собственными делителями, а четыре (перечисленные в условии теоремы) — нет.

«На глаз» видно, что левая часть (2.36) увеличивается с ростом п существенно быстрее, чем правая. Поэтому с самого начала следует предполагать, что нарушения неравенства (2.36) будут происходить лишь при небольших значениях п. Однако обе части неравенства при общей тенденции к возрастанию изменяются при увеличении п весьма неправильным образом, и какие-либо непосредственные индуктивные рассуждения едва ли применимы. Следовательно, представляется естественной следующая программа действий. Наметим некоторую схему последовательного перечисления (выписывания) натуральных чисел, при которой от хорошего числа можно переходить только к хорошему. Если на некотором шаге применения этой схемы все получаемые числа будут хорошими, то тогда и все дальнейшие числа также будут хорошими. Следовательно, все плохие числа должны быть перечислены уже до этого шага. Читатель может заметить, что такой способ рассуждений также является одним из вариантов доказательства по индукции.

Докажем предварительно следующие три утверждения.

1. Пусть pu Рг, Pk, ... — все простые числа, перечисленные в порядке их возрастания (т. е. р\ = 2, р2 = 3 и т. д.). Тогда, если число п = ptp2... pk хорошее и > 3, то число PiP2... PkPk+i также хорошее.

Действительно, в данном случае мы имеем

и по условию должно быть

(2.37)

Для того чтобы написать соответствующее неравенство для произведения pipz... p*p*+i, нужно первое слагаемое правой части (2.37) умножить на 1 H--, что меньше двух, а ко второму добавить loga Рл+ь Но число Р\Рг---Рк— 1 взаимно просто с каждым из простых чисел р4, Рг, .... Pk. Следовательно, каждый его простой делитель q больше любого из этих чисел и потому не меньше, чем pk + i. Значит,

и тем более поэтому

Следовательно, прибавление ко второму слагаемому \ogapk+i увеличивает это слагаемое менее, чем вдвое.

Итак, правая часть не может увеличиваться более, чем в два раза. Но левая часть умножается на p*+i — I, что больше 2. Значит, из (2.37) следует

и требуемое доказано.

2. Если п = pip2... pk, где plt рг, ..., Pk — произвольные различные простые числа, п — хорошее число, a q — произвольное простое число, отличное от pu Рг, ..., р* и большее, чем pi, то ЯРг... Рк также является хорошим числом.

В самом деле, в этом случае неравенство (2.36) снова имеет вид (2.37). Произвести здесь замену pi на q — все равно, что прибавить к левой части (2.37) произведение (q — Pi) (рг—1) ...

а в правой умножить первое слагаемое на

и прибавить ко второму loga—. Ввиду того, что q > Pi, первое слагаемое от такого умножения может лишь уменьшиться.

Значит, для сохранения в силе неравенства достаточно, чтобы было

(Я - Р\) (Р2 — О ... (Рп - U > log«

и тем более достаточно, чтобы было

q-pi> log« — . (2.38)

Однако при /2^3 мы имеем а > - ~ j , так что

и суммирование неравенств такого вида по л от « = pi + 1 до п = q дает нам (2.38).

3. Если p^ip^2 ... Pakk — хорошее число, то р^4"^2 также хорошее число.

Для доказательства достаточно заметить, что при замене в неравенстве

показателя ai на большее число ai + 1 левая часть увеличивается, а правая уменьшается. Следовательно, в результате такого преобразования хорошее число может перейти также лишь в хорошее.

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

Первая из этих операций состоит в построении последовательности 1, 2, 6, 30, 210, ... ; вторая заменяет в числе, каноническое разложение которого содержит только первые степени простых, любой простой делитель на больший (для определенности мы будем считать, что замена производится на ближайшее «сверху» простое число), не входящий в каноническое разложение; третья операция увеличивает на единицу некоторый показатель в канонических разложениях. В результате применения этих операций мы, исходя из единицы, перечислим все натуральные числа. Некоторые числа в таком перечислении встретятся более од-

ного раза, но это обстоятельство не играет для нас никакой роли. Важно, что каждое число хотя бы один раз будет учтено.

Начнем в соответствии со сказанным перечислять натуральные числа. Сначала воспользуемся первой операцией.

Число 1 является плохим, так как для него неравенство (2.36) приобретает вид

1 > 1 + log« 2=1 + log« 1 = 1 X

(произведение натуральных чисел, содержащее нулевое число сомножителей, мы по-прежнему принимаем равным единице), что неверно.

Первая операция в применении к 1 дает 2. Для него неравенство

l>^-+loga 2 = |-+l0ga4

X z

неверно, и потому число 2 также плохое.

Плохими будут и следующие числа 6 и 30; для них:

ф (6) = 2 < -| - у + loga 12 = 2 + loga 12,

ф (30) = 8 < -| • -i . |- + loga 60 ~ 2,4 + 8,5. Наоборот, число 2-3-5-7 = 210 уже оказывается хорошим,

ибо

Ф(210) = 48> |. y+loga420^2.7 + 12,5.

Поэтому все дальнейшие числа, получаемые применением первой операции, будут хорошими. Будем применять теперь вторую и третью операции.

Применение их к числу 2 дает нам 3 и 4, также плохие числа:

ф (3) = 2 < у + log« 3^ 1,3 + 2,3,

ф (4) - 2 < -| + log« 4 » 0,75 + 2,9.

Применение операций к числу 3 дает соответственно 5 и 9, причем число 5, как легко проверить, плохое, а 9 хорошее, и дальнейшие преобразования девятки нас не интересуют. Далее, от 5 можно перейти по второй операции к числу 7, а по третьей — к числу 25. Оба эти числа хорошие; поэтому все происходящие от них числа также будут хорошими, и их можно не рассматривать.

Третья операция, примененная к числу 4, приводит к хорошему числу 8.

Итак, применение к двойке в любом числе второй и третьей операций дает нам плохие числа 3, 4 и 5, а все остальные числа будут хорошими.

Обратимся к числу 6. Вторая операция дает плохое число 10, за которым получаются хорошие 20 и 15 и плохое 14. Но за плохим 14 идут хорошие 21 и 22 (вторая операция), а также хорошие 28 и 98 (третья операция).

Третья операция, применяемая к б, дает плохое 12 и хорошее 18. Но за 12 следуют по третьей операции хорошие 24 и 36, а вторая операция к числу 12 не применяется, так как 12 делится на квадрат простого числа 2.

Наконец, все получаемые из 30 числа (соответственно 210, 42 и 60) хорошие.

Все проведенные рассуждения наглядно описываются следующей схемой (рис. 1).

Рис. 1.

В результате мы получили следующий список плохих чисел:

1, 2, 3, 4, 5, 6, 10, 12, 14, 30.

Соответствующими числами Фибоначчи будут

1, 1, 2, 3, 5, 8, 55, 144, 377, 832040.

Очевидно, собственными делителями «з, «4, ui0 и и44 будут соответственно числа 2, 3, 5, 11 и 29. Можно было бы, выписав все числа Фибоначчи до изо и их разложения на множители, непосредственно убедиться в наличии собственного делителя у изо. Однако в этом нет нужды. Из теоремы п. 25 следует, что изо делится на 31 (ибо 31 есть простое число вида 5/ + !)• С другой стороны, ни «а = 8, ни ui0 — 55, ни «i5 = 610 на 31 не делятся. Следовательно, 31 есть собственный делитель и3о.

Остались числа щ = 1, иг — 1, и6 = 8 и u\2 = 144, которые, очевидно, собственных делителей не имеют.

Теорема доказана.

37. В «противовес» тем четырем числам Фибоначчи, которые не имеют собственных делителей, существуют числа Фибоначчи, обладающие несколькими собственными делителями. Например,

для Wig такими делителями будут числа 37 и ИЗ, для ыгт — числа 53 и 109 и т. д. Много ли чисел Фибоначчи с двумя и более собственными делителями — совершенно не ясно.

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

Из п. 25 следует, что п ^ р— 1, если р имеет вид 5* ± 1, и Л ^ р -f- 1, если р имеет вид 5/ -f- 2. Однако никакой формулы, позволяющей непосредственно вычислять номера членов с наперед заданным собственным делителем р, пока не известно.

Нами в п. 3 было доказано, что все числа Фибоначчи с составными номерами, кроме и4, сами составные. Обратное неверно, так как, например, «19 = 4181=37-113. Возникает вопрос, конечно или бесконечно число всех простых чисел Фибоначчи, иными словами, существует или нет среди простых чисел Фибоначчи наибольшее? Вопрос этот сейчас еще далек от своего решения.

§ 3. ЧИСЛА ФИБОНАЧЧИ И НЕПРЕРЫВНЫЕ ДРОБИ

1. Рассмотрим выражение

(3.1)

где qu qi, ..., qn — целые положительные числа, а Со — целое неотрицательное число. Таким образом, в отличие от чисел qu qi> ..., qn, число qo может равняться нулю. Это несколько особое положение числа qo мы всегда будем иметь в виду и поэтому не будем его каждый раз оговаривать.

Выражение (3.1) называется непрерывной дробью, числа <7о, Qu .... qn — неполными частными этой дроби, а все непрерывные дроби вида

(3.2)

— полными частными.

Иногда непрерывные дроби называются также цепными дробями. Непрерывные дроби находят применение в самых разнообразных вопросах математики. Читателю, желающему познакомиться с ними подробнее, можно порекомендовать книгу А. Я. Хинчина «Цепные дроби», «Наука», 1978.

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

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

Рассмотрим для этого алгорифм Евклида, примененный к числам а и Ь:

(3.3)

Первое из этих равенств дает нам

Но из второго равенства системы (3.3) следует

так что

Из третьего равенства (3.3) мы выводим

и потому

Продолжая этот процесс до конца (индукция!), мы, как легко видеть, придем к равенству

По самому смыслу алгорифма Евклида qn > 1. (Если бы qn равнялось единице, то гп-\ было бы равно Гп и гп-2 разделилось бы на гп-\ нацело, т. е. весь алгорифм оборвался бы одним шагом раньше.) Значит, мы можем вместо qn рассматривать выражение

(qn—1) + у, т. е. считать {qn—1) предпоследним

неполным частным и 1 — последним. Такое соглашение оказывается удобным для дальнейшего.

2. Мы видим, что всякую рациональную дробь -~ можно разложить в непрерывную. Покажем, что это разложение единственно, т. е. что у двух равных непрерывных дробей должны быть равны соответствующие неполные частные.

Для того чтобы это доказать, возьмем две непрерывные дроби, со и о/. Пусть <7о, q\, Ц2, •.. и го' #р Чоу соответственно их неполные частные.

Покажем, что из равенства (û = о/ следует, что q0 = q'Q, а[ = й'[> Q2 = Qf2 и т- д- в самом деле> Я есть целая часть числа ш, a q'o — целая часть со'; поэтому qo = q'o- Далее, непрерывные дроби со и со' можно представить соответственно в виде

где coi и coî—снова непрерывные дроби. Из со = со' и со = q'o следует, что и coi = coi. Значит, равны и целые части чисел coi и coi, т. е. q\ и q\. Продолжая эти рассуждения (индукция!), убеждаемся в том, что

Я2 = Яз = Чз и т- Д-3. Пусть

(3.4)

— некоторая непрерывная дробь. Рассмотрим следующие числа:

Эти числа, записанные в виде обычных несократимых дробей

называются подходящими дробями непрерывной дроби со. Заметим, что переход от к осуществляется заменой последнего неполного частного из числа участвовавших в построении этой подходящей дроби, т. е. qky на qk -\--!—. Точно в том же самом смысле переход от подходящей дроби ко всей непрерывной дроби со осуществляется заменой последнего неполного частного qk на qk H---, т. е. на соответствующее полное частное со*..

4. Важную роль в теории непрерывных дробей играет следующая лемма.

Лемма. Для всякой непрерывной дроби (3.4) имеют место следующие соотношения:

(3.5) (3.6) (3.7)

Будем доказывать все эти равенства одновременно индукцией по А.

Докажем их сначала для k = 1:

Так как числа ç0?i + 1 и q\ взаимно просты, дробь q,)qx^ 1 несократима. Дробь же -~- несократима по определению, а у равных несократимых дробей равны числители и знаменатели. Значит, Pi = g0<7i +1 и Qi = q\. Далее,

(3.3)

Наибольший общий делитель чисел qo(q\q2 + 1) + + <?2 и <7i<72 + 1 на основании п. 10 § 2 равен (?2, ?i?2 + 1) и на основании того же предложения равен (q2i 1), т. е. 1. Значит, дробь, стоящая в (3.8) справа, несократима, и потому

Равенство

проверяется без труда.

Этим основание индукции доказано.

Предположим теперь, что равенства (3.5), (3.6) и (3.7) справедливы, и рассмотрим подходящую дробь

(3.9)

Переход от к по сделанному ранее замечанию осуществляется заменой q^i в выражении

PhA- 1

для п +l на qk+{ -\--; так как в выражения для Pu, Qk> Pk-u Qk-\ величина qk+\ не входит, мы имеем

или, вспоминая индуктивные предположения (3.5) и (3.6),

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

Предположим, что числа Pk+iqk+2+Pk и Q*+i<7*+2 + + Qk имеют некоторый общий делитель d> 1. Тогда выражение

тоже должно разделиться на d. Но по индуктивному предположению (3.7) это выражение равно (—l)k+{ и делиться на d не может.

Итак, правая часть (3.10) несократима, и (3.10) есть, таким образом, равенство двух несократимых дробей. Значит,

Для завершения доказательства индуктивного перехода нам остается показать, что

Pk+2Qw - Pk+i = (-1) *Ч (3.11)

Но ввиду только что доказанного

Pk+2Qk+\ — Pk+\Qk+2 =

= Pk+\Ok+2Qk+i + PkQk+\ — Pk+\qk+2Qk+i — Pk+iQk>

и (3.11) вытекает непосредственно из индуктивного предположения (3.7). Этим индуктивный переход обоснован, и вся лемма доказана. Следствие.

/Уи Pk = (-0* п im

Qk+i Qu QkQk+i ' v '

Доказательство очевидно.

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

Р0<Рх<Р2< (313)

Qo<Qi<Q2< ...

Это простое, но важное замечание мы в дальнейшем еще уточним.

5. В ходе доказательства леммы предыдущего пункта мы осуществляли переход от равенства (3.10) к равенству (3.11). Если, однако, заменить в (3.10) неполное частное qk на полное частное со*, то, как тоже было оговорено в конце п. 4, мы получим дробь (о:

(3.14)

Теперь мы можем несколько дополнить сформулированное в п. 2 утверждение о единственности разложения числа в непрерывную дробь.

Лемма. Пусть в (3.14) дробь * 1 является предпоследней, k — 1-й подходящей дробью к ,

я Wfc+i ^ 1, Тогда -щ- является подходящей, дробью к со, а соагч-1 — соответствующим полным частным.

Доказательство. Разложим дробь в непрерывную:

По условию мы имеем

где -— третья от конца подходящая дробь к-7— .

Замена здесь qk на qk ^--приведет нас справа к что по (3.14) равно о). Следовательно,

(3.15)

и требуемое получено. Здесь в ходе доказательства не было упомянуто условие cd/h-i ^ 1. В действительности оно используется в самом написании выражения (3.15): в случае (Dä+i < 1 неполное частное qk следовало бы заменить на большее число.

6. Применим теперь лемму п. 4 для описания всех непрерывных дробей с неполными частными, равными единице. Для таких дробей имеет место следующая интересная теорема.

Теорема. Если непрерывная дробь имеет п не* полных частных и каждое из этих неполных частных равно единице, то дробь равна Un+l .

Доказательство. Обозначим непрерывную дробь с п единичными неполными частными через art« Очевидно,

ai, оь, • •., ал

являются последовательными подходящими дробями ап.

Пусть Так как

должно быть Pi = 1, Р2 = 2. Далее, Рп+\ = РпЦп+х + + Рп-\ = Рп + Рп-\. Поэтому (сравни п. 6 § 1) Рп = — Un+U

Аналогично Qi = I, Q2 = 1 И Qn+\ = QnÇn+l +

+ Q"-i = Qn + Qn-u так что Qn = un. Значит,

(3.16)

Предоставляем читателю сопоставить этот результат с формулами (1.10) и (3.7).

7. Пусть нам даны две непрерывные дроби œ и со':

причем

(3.17)

Обозначим через

подходящие дроби со и через

•—подходящие дроби о/.

Из результатов леммы п. 4 легко усмотреть, что ввиду (3.17)

и

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

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

Лемма. Если непрерывная дробь со имеет неполными частными числа <7о, Qu Цч, •••*> Qn, причем

*0 = Il в ч = • • • - = ь + 1 e • ' • = ЧП " 1»

q. =2 (/ Ф 0),

то

^_ ui+\"n-M + UtUn-i + \

Доказательство этой леммы ведется индукцией по i. Если i — 1, то при всяком п п — 1 неполное частное

или ввиду доказанного в начале этого пункта

или, полагая в соответствии с п. 25 § 1 //о = О,

Основание индукции этим доказано.

Предположим теперь, что при всяком п непрерывная дробь

/ неполных частных

(3.18)

равна

(3.19)

Возьмем непрерывную дробь

i + 1 неполное частное

Ее, очевидно, можно рассматривать и так:

i неполных частных

(3.20)

Непрерывная дробь, стоящая в (3.20) ниже пунктирной черты, на основании равенства (3.18) и (3.19) равна

Значит, вся дробь (3.20) равна

Этим доказаны индуктивный переход и вся лемма. Следствие. Если не все неполные частные непрерывной дроби о) являются единицами, число этих неполных частных не меньше п и qo Ф 0, то, записав со в виде обычной дроби -тг% мы будем иметь

и аналогично

Существенную роль при этом, конечно, играет лемма п. 4, на основании которой в процессе «свертывания» непрерывной дроби в обыкновенную мы получаем только несократимые дроби. Поэтому уменьшение числителей и знаменателей получаемых дробей из-за их сокращения не будет иметь места.

8. Из доказанного в предыдущем пункте мы можем получить следующую теорему, указывающую на особое положение чисел Фибоначчи по отношению к алгорифму Евклида.

Теорема. Число шагов в алгорифме Евклида, примененном к числам а и Ь, при некотором а равно п— 1, если b = ип, и при всяком а меньше п — 1, если b < ип.

Доказательство. Первая часть теоремы доказывается совсем просто. В качестве а достаточно взять следующее за b число Фибоначчи, т. е. ип+ь Тогда

Непрерывная дробь ап имеет п неполных частных, т. е. число шагов алгорифма Евклида, примененного к числам а и bt равно п — 1.

Докажем вторую часть теоремы. Предположим обратное, т. е. что число шагов указанного алгорифма не меньше п—1. Разложим отношение у в непрерывную дробь со. Очевидно, со будет иметь не меньше, чем л, неполных частных (именно, на единицу

больше, чем длина алгорифма Евклида). Так как b не есть число Фибоначчи, не все неполные частные (о будут единицами, и потому, по следствию леммы п. 7, b > ип, что противоречит условию теоремы.

Доказанная теорема означает, что алгорифм Евклида, примененный к соседним числам Фибоначчи, в некотором смысле «самый длинный».

9. Выражение

(3.21)

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

(3.22)

— последовательность (очевидно, бесконечная) подходящих дробей дроби (3.21). Покажем, что эта последовательность имеет предел.

Рассмотрим для этого отдельно последовательности четных и нечетных подходящих дробей:

(3.23) (3.24)

На основании (3.12) и (3.13)

Значит, последовательность (3.23) — возрастающая, Точно так же из

следует, что последовательность (3.24) — убывающая.

Всякий член последовательности (3.24) больше всякого члена последовательности (3.23). Действительно, рассмотрим числа

и возьмем нечетное число большее как 2п, так и 2т + 1. Из (3.12) вытекает, что

(3.25)

а из возрастания (3.23) и убывания (3.24) —

(3.26) (3.27)

Сравнивая выражения (3.25), (3.26) и (3.27), мы получаем, что

т. е. любая четная подходящая дробь всегда меньше любой нечетной.

На основании (3.12) и (3.13)

и потому при увеличении п разность (дг -f- 1 )-й и п-й подходящих дробей по абсолютной величине стремится к нулю.

Из всего сказанного можно заключить, что последовательности (3.23) и (3.24) имеют один и тот же предел, который, очевидно, является и пределом (3.22). Этот предел называется значением бесконечной непрерывной дроби (3.21).

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

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

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

10. Найдем значение бесконечной непрерывной дроби

(3.28)

По доказанному выше это значение есть lim <хд»

где ап = Un+l . Вычислим этот предел.

Как уже было установлено в п. 20 § 1, ип есть ближайшее к —?= целое число; значит,

каково бы ни было п.

Поэтому ввиду доказанного в п. 5

Ho 8rt+iV5 есть величина ограниченная (она по абсолютной величине меньше двух), а ап при я, стремящемся к бесконечности, неограниченно возрастает (потому что а > 1). Значит,

В силу тех же причин и

и мы получаем

Значение непрерывной дроби (3.28) можно вычислить и не прибегая к формуле Бине и предельным переходам. (Нам в известном смысле «достаточно» проведенного в п. 2 индуктивного рассуждения, обслуживающего, очевидно, не только конечные непрерывные дроби, но и их пределы — бесконечные дроби.)

Представим для этого дробь (3.28) в виде

Очевидно, здесь выражение х само является непрерывной дробью (3.28), так что

откуда

(3.29)

Так как значение дроби (3.28) является неотрицательным числом, оно должно равняться положительному корню уравнения

(3.29), т. е. - 2^ 1 а это и есть а'

Из доказанного следует, что отношение соседних чисел Фибоначчи с ростом их номеров приближается к а. Этим можно воспользоваться для приближенного вычисления числа а (сравни вычисление ип в п. 20 § 1, а также формулу (1.35)). Ошибка при таком вычислении получается маленькой, даже если мы возьмем небольшие числа Фибоначчи. Например (с точностью до пятого знака),

а а= 1,6180. Ошибка, как мы видим, меньше 0,1%. Между прочим, в отношении ошибок при приближенном вычислении иррациональных чисел с помощью подходящих дробей и их разложений в непре-

рывные дроби число а представляет собой наихудший случай. Всякое другое число описывается своими подходящими дробями в некотором смысле более точно, чем а. Остановимся более подробно на рассмотрении этого круга вопросов.

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

Приближения вещественного числа его подходящими дробями являются наиболее точными в смысле следующего утверждения.

Теорема Лежандра. Пусть ш — произвольное число, а -~--некоторая несократимая дробь. Предпоследнюю подходящую дробь при разложении — обозначим через ~г.

Тогда для того чтобы ~ была подходящей дробью к со, необходимо и достаточно выполнение неравенства

(3.30)

Доказательство. Необходимость. Пусть

соответственно п-я и п—1-я подходящие дроби к со. Тогда, вводя в рассмотрение м+1-е полное частное cû/i+i (которое больше единицы), мы согласно (3.17) и (3.7) имеем

(3.31)

Достаточность. Пусть выполняется (3.30), Выберем число 0, для которого будет

Тогда в силу (3.17) и (3.7) мы получаем

так что 9 > 1. Тем самым мы оказываемся в условиях леммы п. 5, согласно которой есть подходящая дробь к о, а 6 — соответствующее полное частное.

12. В обозначениях предыдущего пункта q/ <С q. Поэтому если

(3.32)

то — является подходящей дробью к со. Ясно вместе с тем, что это условие не является необходимым для того, чтобы дробь ~ была подходящей: не все подходящие дроби числа со обладают свойством (3.32). Вместе с тем имеется «достаточно много» подходящих дробей к со, которые неравенству (3.32) удовлетворяют. Точная формулировка этого содержится в следующей теореме.

13. Теорема Валена. Если со — произвольное число, то из двух подходящих дробей о с соседними номерами хотя бы одна — удовлетворяет неравенству

Доказательство. Возьмем две соседние подходящие дроби и п и оценим сумму

(3.33)

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

Значит, хотя бы одно из составляющих s слагаемых должно быть меньше соответствующего слагаемого в (3.33) справа, т. е.,

а это и требовалось.

14. Если мы заменим неравенство (3.32) на еще более сильное, увеличив в нем коэффициент при q2, то у нас окажется еще меньше шансов получить удовлетворяющие ему подходящие дроби. Тем не менее при умеренном увеличении этого коэффициента таких возможностей будет еще довольно много.

Теорема Бореля. Если о) — произвольное число, то из любых трех последовательных его подходящих дробей хотя бы одна — удовлетворяет условию

(3.34)

Доказательство. Возьмем три последовательные подходящие дроби к числу о:

(3.35)

Как было выяснено в (3.31),

(3.36)

Поэтому, обозначая для удобства д/5 через с, мы можем, учитывая (3.36), переписать (3.34) как

или

Далее будем доказывать теорему от противного. Несоблюдение неравенства (3.34) ни для одной из подходящих дробей (3.35) означает, что

(3.37) (3.38) (3.39)

Однако

так что из (3.37) следует

или

(3.40)

Перемножая это неравенство почленно с (3.38), мы получаем

или, полагая

и вспоминая, что с — У 5 , мы имеем

т. е. значения / положительны и для них

откуда

Заметим, что верхняя граница для t оказывается равной а2. Ясно поэтому, что если соп+2 > ос, то

(3.41)

Однако если со,2+2 > et, то из (3.38) следует

т. е.

так что Ii

что противоречит (3.41). Значит, сэЛ+2 ^ а. Так как, однако, величины (дп+2 и Щр- входят в неравенства (3.38) и (3.39) равноправно, аналогичные рассуждения дают нам

(3.42)

По тем же соображениям из (3.40) и (3.39) вытекает, что

(3.43)

Далее заметим, что

Так как qn+i— целое положительное число, отсюда следует, что qn+% = 1. Но тогда

и из (3.43) следует

откуда

Вместе с (3.42) это дает нам

чего, однако, не может быть, так как дробь Д+! рациональна, а число а является иррациональным.

15. Устанавливаемые в теоремах Валена и Бореля факты могут создать впечатление, будто дальнейшее увеличение коэффициента при q2 в формулах (3.32) и (3.34) заставит лишь выбирать нужную подходящую дробь -2 из более длинных серий подходящих дробей.

Это впечатление, однако, оказывается обманчивым. В действительности с увеличением коэффициента при с за V 5 вся картина изменяется весьма резко.

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

Теорема Гурвица. Если с>У5, то существуют числа со, для которых неравенство

(3.44)

выполняется лишь для конечного числа несократимых дробей —.

(Согласно теореме Лежандра все такие дроби должны быть подходящими для числа (0.)

Доказательство. В качестве числа (о можно взять а = 1 . Пусть с> У 5 и

Тогда по теореме п. 13 — должна быть подходящей дробью к а. Положим ~~тг и напишем снова, как в (3.36),

Кроме того, согласно (3.16) в нашем случае (йп+\ = а, a Qn = ип. Значит (в обозначениях п. 10),

причем —-отличается от — на некоторое гПу становящееся с ростом п сколь угодно малым. Поэтому мы имеем

Таким образом, если взять с > У 5 , то при достаточно большом п будет с > У 5 + гп, так что

Значит, в условиях с>д/5 неравенство (3.44) будет при (ù = а выполняться лишь для конечного числа подходящих дробей с не очень большими номерами.

Остается открытым вопрос о том, существуют ли другие, отличные от а, числа со, для которых неравенство (3.44) выполняется лишь для конечного числа подходящих дробей.

§ 4. ЧИСЛА ФИБОНАЧЧИ И ГЕОМЕТРИЯ

1. Разделим отрезок AB единичной длины (рис. 2) на две части так, чтобы большая из его частей являлась средним пропорциональным между меньшей его частью и всем отрезком.

Рис. 2.

Обозначим для этого искомую длину большей части отрезка через х. Очевидно, длина его меньшей части при этом будет равна 1—х, и условие нашей задачи дает нам пропорцию

(4Л)

откуда

(4.2)

Положительным корнем (4.2) является-~--—, так что отношения в пропорции (4.1) равны каждое. Такое деление (точкой Ci) называется делением в среднем и крайнем отношении. Его часто называют также золотым делением или золотым сечением.

Если взять отрицательный корень уравнения (4.2), то делящая точка Сг окажется вне отрезка AB (такого рода деление в геометрии называется внешним делением), как это видно из рис. 2. Легко показать, что и здесь мы имеем дело с золотым сечением:

2. Фактическое построение точки, делящей отрезок золотым сечением, осуществляется без труда,

Рис. 3. Рис. 4.

Пусть AB = 1; восставим из точки А перпендикуляр и возьмем точку Е} для которой АЕ = у (рис, 3). Тогда _

Проведя из Е, как из центра, дугу через А до пересечения с ЕВ в точке D, мы получаем

Наконец, проведя через D дугу с центром в ß, мы находим искомую точку d. Точку внешнего деления С2 можно найти из условия АС2 = = Bd.

3. Золотое сечение довольно часто встречается в геометрии. Например, для квадрата, вписанного в полукруг (см. рис. 4), точка С делит золотым сечением отрезок AB.

Сторона d\Q правильного десятиугольника (рис. 5), вписанного в круг радиуса /?, как известно, равна

т. е. 2R sin 18°.

Вычислим sin 18°. На основании известных формул тригонометрии

Рис. 5.

так что

(4.3)

Так как sin 72° = cos 18° ф О, из (4.3) следует, что

1 = 4 sin 18° (1 — 2 sin2 18°), и потому sin 18° является одним из корней уравнения 1 = 4jc (1 —2х2),

или

8а:3 - 4а- + 1 = 0.

Разложив левую часть последнего уравнения иа множители, мы получаем

(2а - 1) (4*2 + 2*- 1)=0,

откуда

Так как sin 18° есть положительное число, отличное от имеем

Заметим для дальнейшего, что

Таким образом,

Иными словами, аю равно большей части радиуса круга, разделенного золотым сечением.

Практически при вычислении аю можно вместо а брать отношение соседних чисел Фибоначчи (см. п. 26 § 1 или п. 10 § 3) и считать приближенно, что аю есть -^R или даже |- R.

4. Рассмотрим правильный пятиугольник. Его диагонали образуют правильный звездчатый пятиугольник (рис, 6),

Рис. 6.

Угол ÄFD равен 108°, а угол ADF равен 36°. Значит, по теореме синусов

Так как очевидно, что AF = АС, должно быть

и точка С делит отрезок AD золотым сечением. Но тогда, по определению золотого сечения,

Замечая, что AB = CD, мы получаем

Таким образом, среди отрезков

ВС, AB, AC, AD

каждый последующий в а раз больше предыдущего. Пусть читатель попутно проверит, что и

Б. Возьмем прямоугольник со сторонами а и b и будем последовательно вписывать в него наибольшие возможные квадраты, как это показано на рис. 7.

Рис. 7.

Рассуждения п. 5 § 2 показывают, что такой процесс в случае целых а и b соответствует алгорифму Евклида, примененному к этим числам. Числа квадратов одинаковых размеров равны при этом (п. 1 § 3)

соответствующим неполным частным разложения у в непрерывную дробь.

Если разбивать так на квадраты прямоугольник, стороны которого относятся как соседние числа Фибоначчи (рис. 8), то на основании п. 5 § 3 все квадраты, кроме двух самых маленьких, будут различными.

Так как стороны всех этих квадратов равны соответственно «i, и2, ип, их суммарная площадь, очевидно, равна

uî + ul+ ... +!&

Но это есть площадь разбиваемого нами прямоугольника, равная UnUn+ь

Таким образом, при любом п

и? + ul + ... + ul *= UnUn+\>

и мы получили новое, геометрическое доказательство утверждения п. 4 § 1«

Рис 8.

6. Пусть теперь отношение сторон прямоугольника равно а. (Такие прямоугольники мы будем для краткости называть прямоугольниками золотого сечения.) Докажем, что, вписав в прямоугольник золотого сечения наибольший возможный квадрат (рис. 9), мы снова получим прямоугольник золотого сечения,

В самом деле,

Рис. 9.

по условию AD=AE=EF9 так как AEFD — квадрат. Значит,

Но а2 — 1 = а, так что

На рис. 10 показано, как прямоугольник золотого сечения может быть «почти весь» исчерпан квадратами /, //, ///, ... При этом каждый раз после вписывания очередного квадрата будет оставаться фигура, являющаяся прямоугольником золотого сечения.

Пусть читатель сравнит эти рассуждения с пп. 5 и 9 предыдущего параграфа.

Заметим, что если в квадрат вписать прямоугольник золотого сечения / и квадраты // и ///, как это показано на рис 11, то оставшийся прямоугольник

Рис 10.

Рис 11.

тоже окажется прямоугольником золотого сечения. Доказательство предоставляется провести читателю.

7. По аналогии с прямоугольниками золотого сечения можно говорить и о треугольниках золотого сечения: остроугольном — с углами 36°, 72° и 72° и тупоугольном— с углами 108, 36° и 36°. На рис. 12 видно, как остроугольный треугольник золотого сечения разбивается на меньшие три треугольника золотого сечения, и обозначены величины углов и отрезков.

8. Природа дает нам многочисленные примеры расположений однородных предметов, описываемых числами Фибоначчи.

В разнообразных спиралевидных расположениях мелких частей растений обычно можно усмотреть два семейства спиралей. В одном из этих семейств спирали завиваются по часовой стрелке, а в другом — против. Числа спиралей того и другого типов часто оказываются соседними числами Фибоначчи.

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

На многих шишках семена (т. е. «чешуйки») расположены в трех спиралях, полого навивающихся на стержень шишки. Они же расположены в пяти спиралях, круто навивающихся в противоположном направлении. В крупных шишках удается наблюдать 5 и 8 и даже 8 и 13 спиралей. Хорошо заметны такие спирали и на ананасе: обычно их бывает 8 и 13.

У многих сложноцветных (например, у маргаритки или ромашки) заметно спиральное расположение отдельных цветков в соцветиях-корзинках. Число спиралей бывает здесь 13 в одном направлении и 21 в другом или даже соответственно 21 и 34, Особенно

Рис. 12.

много спиралей можно наблюдать в расположении семечек крупного подсолнуха. Их число в каждом из направлений может достигать соответственно 55 и 89,

9. Прямоугольники золотого сечения выглядят «пропорционально» и приятны на вид. Вещами, имеющими такую форму, оказывается удобным пользоваться. Поэтому многим «прямоугольным» предметам нашего обихода (книгам, спичечным коробкам, чемоданам и т. п.) часто придается именно такая форма. Например, данная книга имеет форму прямоугольника с отношением сторон 1,62, а заполненная текстом часть ее страницы — форму прямоугольника с отношением сторон 1,64. (Напомним еще раз, что а = 1,6180.)

Различными философами-идеалистами древности и средневековья внешняя красота прямоугольников золотого сечения и других фигур, в которых наблюдается деление в среднем и крайнем отношении, возводилась в эстетический и даже философский принцип. Золотым сечением и еще некоторыми числовыми отношениями пытались не только описать, но и объяснить явления природы и даже общественной жизни, а с самим числом а и с его подходящими дробями производились разного рода мистические «операции», Разумеется, подобные «теории» ничего общего с наукой не имеют.

10. Числа Фибоначчи появляются также в вопросах, связанных с исследованием путей в различных геометрических конфигурациях. Рассмотрим, например, сеть путей, изображенную на рис. 13 (такие сети в математике принято называть ориентированными графами) у и подсчитаем число путей, которыми можно, двигаясь вдоль стрелок, перейти из вершины А или вершины В в вершину Сл,

Рис. 13.

Обозначим числа таких путей соответственно через ап и bn. Ясно, что при начале движения, как из точки Л, так и из точки ß, в вершину Сп можно попасть двумя способами: через вершину Сп~\ с последующим шагом вдоль наклонного ребра и через вершину Сп-г с последующим шагом вдоль горизонтального ребра. Значит,

ап = art-i + ал_2,

Ьп = Ьп-\ + bn-2-

Нам остается заметить, что а\ — а2 = 1, и Ь\ = 1, &2 = 2, откуда сразу следует, что ап = ип и bn = ип+\.

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

Рассмотрим следующую игру-состязание в ее традиционной постановке, называемой «цзяньшицзы». Пусть имеются две кучи предметов (например, спичек), и два игрока поочередно берут либо произвольное число предметов из одной кучи, либо поровну из каждой кучи. Выигравшим считается тот, кто забирает последние предметы.

В более математизированной форме эту игру можно представить себе как имеющийся перед игроками ориентированный граф, изображенный на рис. 14. Будем считать, что граф расположен на координатной плоскости, и две целочисленные координаты каждой из его вершин соответствуют числу предметов в первой и второй кучах (например, жирная точка на рис 14 имеет координаты (5,3)). Начальное положение игры может быть отмечено помещением фишки в соответствующую вершину графа. Процесс игры состоит в поочередном уменьшении игроками одной из координат вершины на целое число или обеих координат на одно и то же число, т. е. в передвижении фишки вдоль стрелок на рис. 14 на любое расстояние (т. е. по правилам ходов ферзя). Ясно что за конечное число ходов фишка окажется передвинутой в начало координат (отмеченное на графе кружком), и игрок, поставивший

Рис. 14.

фишку в эту вершину, считается выигравшим. Эту игру будем далее для краткости называть игрой Г, а изображенный на рис. 14 граф — графом игры Г. Вершина графа, в которой находится (или может находиться) фишка, вместе с указанием, какой игрок имеет очередь хода, будет называться позицией игры.

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

Во-первых, сформулируем достаточно точно понятие выигрывающей позиции для игры Г (а фактически и для всех игр такого типа).

Во-вторых, сформулируем некоторую схему описания множества всех выигрывающих позиций.

В-третьих, опишем выигрывающие позиции в терминах фибоначчиевых представлений (в смысле п. 27 § 1) их координат.

Наконец, в-четвертых, мы перейдем от фибоначчиевых представлений координат выигрывающих позиций к их явным описаниям посредством формул.

Приступим к выполнению этой программы.

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

Тривиальным примером выигрывающей позиции в игре Г является вершина (0,0). Игрок, приведший фишку в эту позицию, уже выиграл, и никаких действий противника уже не последует.

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

Более обстоятельно, но не более трудно показывается, что (3, 5) и (5, 3) также суть выигрывающие позиции.

Формально говоря, в приведенное в начале этого пункта определение, а именно в оборот «независимо

от того, как будет вести себя его противник», вкралось новое для нас понятие: «поведение» игрока. Чтобы дальнейшие рассуждения имели смысл, нам надлежит это понятие точно описать.

Представим себе для этого, что каждый из игроков, прежде чем сесть за игру, составил точный план игры, т. е. наметил ход, который он будет делать в каждой позиции, как только он в эту позицию попадет. Такой план принято называть стратегией игрока. Стратегия игрока в игре Г есть таким образом функция, определенная на множестве всех позиций, причем значением ее на данной позиции Р может быть любая позиция, в которую можно из Р перейти. Как только оба игрока выбрали свои стратегии, все развитие игры уже можно считать предопределенным, в какой бы позиции фишка первоначально ни находилась: тот игрок, чья очередь хода, передвигает ее в соответствии со своей стратегией в некоторую вполне определенную позицию; но в новой позиции очередь хода будет принадлежать другому игроку, который согласно своей стратегии также должен будет сделать вполне определенный ход; после этого снова наступит очередь первого игрока и т. д. В результате фишка будет проходить по графу однозначно определенный путь.

Теперь мы можем уточнить понятие выигрывающей позиции в игре Г: позиция называется выигрывающей, если существует такая стратегия пришедшего в нее игрока А, что какова бы пи была стратегия его противника Б, игрок Л приведет фишку в позицию (0,0).

Важно отметить, что достижение игроком выигрывающей позиции еще ни в коей мере не дает ему оснований играть «спустя рукава». Напротив, это означает лишь то, что для него существует некоторая стратегия (ее естественно также назвать выигрывающей) f которую ему еще предстоит точно установить и неукоснительно соблюдать.

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

продолжения, а это противоречит предположению о том, что выбранная им стратегия —выигрывающая.

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

13. Рассмотрим некоторое множество позиций R игры на графе Г (или на любом другом ориентированном графе). Оно может обладать (или не обладать) следующими свойствами:

1°. Любой ход в позиции, принадлежащей /?, выводит за пределы R. По некоторым довольно глубоким причинам, в которые мы здесь не имеем возможности вдаваться, это свойство множества позиций в игре (и в графе) называется его внутренней устойчивостью.

2°. В любой позиции, не принадлежащей R, существует ход, приводящий в позицию из R. Это свойство R называется его внешней устойчивостью.

Множества позиций в играх на ориентированных графах, которые являются одновременно внутренне и внешне устойчивыми, имеют большое значение в играх, связанных с поочередными перемещениями по вершинам графа. Такие множества называются решениями этих игр (а также решениями графов этих игр). Если фишка в ходе игры оказывается в принадлежащей решению позиции, то игрок, чья очередь хода, обречен все последующие ходы «безуспешно пытаться уйти из решения»: какой бы ход он ни сделал, по свойству внутренней устойчивости он выведет фишку за пределы решения; но тогда по свойству внешней устойчивости его противник сумеет следующим ходом фишку в решение вернуть.

В рассматриваемой нами игре Г всякая партия заканчивается приведением фишки в начало координат, и игрок, приведший ее туда, выигрывает. Значит, если решение игры содержит начало координат, то игрок, имеющий очередь хода в одной из принадлежащих этому решению позиций, выигрывает. Следовательно, это решение состоит из выигрывающих позиций.

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

14. Прежде всего установим единственность такого решения.

Лемма. Для игры Г существует не более одного решения, содержащего начало координат.

Доказательство. Предположим, что, вопреки утверждению леммы, имеется два таких решения, R и S, причем некоторая позиция si из 5 не принадлежит R. По внешней устойчивости R из позиции s\ можно перейти в некоторую позицию г\ из R. Но по внутренней устойчивости S позиция г\ не может принадлежать S. Значит, по внешней устойчивости 5 мы можем из г\ перейти в некоторую позицию s2 из 5, которая (в силу внутренней устойчивости R) не может принадлежать R. Повторяя этот процесс достаточно долго, мы получим последовательность позиций S]y гь s2, /2, которая заканчивается началом координат и в которой каждая позиция принадлежит лишь одному из решений R или 5. Значит, и начало координат должно принадлежать только R или только 5, и мы получили противоречие.

15. Определяющее, «характеристическое» свойство решения игры R, содержащего начало координат, описывается следующей теоремой.

Теорема. Пусть R — множество позиций в игре Г, которое обладает следующими свойствами:

1) позиция (0,0) принадлежит /?;

2) если (а, Ь) принадлежит R, то и (ft, а) принадлежит R;

3) для всякого натурального а найдется ровно одно натуральное 6, для которого (а, Ь) принадлежит R\

4) для всякого натурального d найдется ровно одна пара чисел (а, Ь) из /?, для которой а — b — d\

5) если позиции (a,b) и (k,l) принадлежат Rt причем a<b, k<l и b — a<l — kt то а < £ и Ь<1.

Тогда множество R является решением игры Г. Доказательство. Заметим сначала, что, как следует из 3), каждое натуральное число является

координатой ровно в одной симметричной паре (свойство 2) ) позиций из /?.

Перейдем к установлению свойств внутренней и внешней устойчивости множества R.

а) Внутренняя устойчивость. Пусть (а, Ь) принадлежит R. Если уменьшить а или 6, то возникает пара, сочетающая с b (соответственно с а) другое число, и потому по 3) не принадлежащая /?, Если же уменьшить одновременно и одинаково а и ft, то получится отличающаяся от (а, Ь) пара с той же разностью координат и не могущая поэтому в силу 4) принадлежать R.

б) Внешняя устойчивость. Пусть (а, Ь) не принадлежит R.

Если а = by то от этой вершины можно перейти к вершине (0,0), которая по 1) принадлежит R.

Если а Ф Ь, то по 3) найдется такое с, что (а, с) принадлежит /?, а по 4) найдутся такие k и /, что / — k = b — а и (k/l) принадлежит /?. Тогда при с < b от (а,Ь) можно перейти к (а, с), уменьшив 6, a при Ob имеет место с — а>Ь — а = / — k, так что по 5) должно быть с > / и а > é, и уменьшение каждой из координат позиции (а,6) на а — k = b — / дает нам позицию (k, I).

Двойная устойчивость установлена, и R оказывается решением.

16. Теперь нетрудно построить некоторый развертывающийся (а по сути дела — рекуррентный) процесс, порождающий позиции из решения R игры Г, содержащего (0,0).

Начнем с позиции (0,0), а затем, уже выписав набор позиций

{au bi), ...» («л, bn)t (0,0), (4.4)

{bu ...» {bn, an)9 где ai<bi для n, положим an+i равным наименьшему из чисел, не участвовавших в наборах (4.4), и bn+i = a„+i +{п+ 1).

Фактически этот процесс приводит к системе позиций

(1,2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15),... (0, 0),

(2,1), (5, 3), (7, 4), (10, 6), (13, 8), (15,9),...

Позиции, составляющие это множество, расположены «почти» на двух лучах, как это видно из рис. 15.

Непосредственно из описанного построения видно, что полученная система позиций удовлетворяет условиям 1)—5) из доказанной в предыдущем пункте теоремы. Следовательно, она является решением игры, а в соответствии с п. 14 — и единственным решением, содержащим позицию (0, 0). Заметим, что игра Г имеет еще решения, не содержащие этой позиции. Однако это обстоятельство нас интересовать не будет.

В принципе поставленная нами задача отыскания решения игры Г тем самым решена. Однако множество /?, хотя и определено у нас однозначно, но имеет плохо обозримый вид. Изобразим его иначе.

17. Пусть, как в п. 27 § 1, Ф(/) обозначает фибоначчиево представление натурального числа /. Можно считать, что последними фибоначчиевыми цифрами представления каждого из чисел является некоторое количество нулей (если этих нулей нет, то их число, очевидно, равно нулю). Разделим все целые положительные числа на два класса: имеющие в конце своего фибоначчиевого представления четное или нечетное число нулей. Очевидно, каждое число из второго класса может быть получено ровно из одного числа первого класса приписыванием к его фибоначчиеву представлению одного нуля справа. Тем самым натуральные числа объединяются в пары. Покажем, что множество всех таких пар (а, Ь) (и симметричных им пар (&, а)) вместе с парой (0,0) удовлетворяют условиям теоремы из п. 15 и тем самым образуют решение игры Г.

Условия 1)—3) выполняются очевидным образом.

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

Рис. 15.

к высшим, т. е. записывать фибоначчиево представление числа в виде ... Фг (где, естественно, фг есть коэффициент при иг).

Если фибоначчиево представление

Ф{а) = <р/ ... ф2 (4.5)

оканчивается нечетным числом нулей, то возьмем а и b с фибоначчиевыми представлениями

Ф(а) = Ф/...ф20, (46)

Ф{Ь) = ф/ ... ф200.

Мы имеем

Если же Ф(а) оканчивается четным числом нулей:

ф2 = фЗ = ... = ф2т+1 = О И ф2т+2 = 1 (/П ^ 1), то

возьмем

(4.7)

и подсчитаем

или, воспользовавшись формулой (1.2),

Ь — а = (plUl + « • • + ф2т+3^2т+3 + "2т+2 = d.

Проверим единственность пары с заданной разностью d.

Если Ф(а) имеет в конце нечетное число нулей, то при другой паре (а, Ь) и фибоначчиевы представления этих чисел (4.6) были бы иными; но тогда и Ф{а) было бы иным, а в силу единственности фибоначчиева представления иным было бы и d.

Случай, когда Ф{а) имеет в конце четное число нулей, по существу, столь же прост, хотя и требует для своего анализа некоторых подсчетов.

Пусть представление

<b(d)= \ik ... \i2 оканчивается ровно 2m нулями:

1^2 = — I^2m+1 = Of Ц2т+2 = 1, \*2m+3 = О,

и мы имеем

d = + • • • + М<2т-|-4И2т-М + ^2т+2- (4.8)

Представим d в виде разности b— а, где Ф(а) имеет в конце четное число нулей, a Ф(Ь) получается из Ф(а) путем приписывания к Ф(а) еще одного нуля справа.

Пусть

а = (СМ + ф/-1«/-1 + . . , + ф3«3 + ф2«2, Ь = yiUl+i + 4l-\Ul + . . . +фз"4 + Ф2"з-

Тогда

d = 6 — а = Ф/М/-1 + Ф/-1"/_2 + • • • + Фз^2 + Ф2«1- (4.9) Если при этом ф2 = 0, то ф/ф/-1 ... фз является фибоначчиевым представлением d, и по единственности такого представления его цифры должны совпадать с цифрами из (4.8). В том числе должно быть

ф2 = фЗ = ... = ф2т+2 = 0, ф2т+з=1,

т. е. фибоначчиево представление числа а оканчивается нечетным числом нулей, что противоречит выбору чисел а и Ь. Значит, фг = 1. Но тогда

d — 1 = ф/Wj-l + Ф/-1М/-2 + #%•-+■ Фз"2

и

Ф(<4 — 1)= ф/ф,-1 ... фз, (4.10)

а с другой стороны, из (4.8) следует, что

d — 1 = \ikUk + • * « + M-2m+4W2m+4 4" и2т+2— 1 —

= V>kuk + • • • + M-2m+4W2m-M + u2m + l + u2m-\ + • • • + w3» так что

($(d— 1)= \Xk ... H2m+400101 ... 010.

В силу единственности фибоначчиева представления вместе с (4.10) это дает

Кроме того, как уже указывалось, ф2= 1. Следовательно, a, a потому и 6, обязаны иметь вид из формулы (4.7).

Это значит, что соблюдается условие 4).

Наконец, ясно, что в условиях выполненного построения с ростом разности координат позиции должны возрастать и сами координаты. Это значит, что выполняется 5).

Таким образом, построенная система пар чисел является решением игры Г, содержащим (0,0). Ввиду доказанной единственности такого решения она должна совпадать с результатом построения из п. 16.

Фибоначчиевы представления чисел позволяют для каждого натурального числа непосредственно указывать «парное» ему. Найдем, например, «пару» к числу 31. Для этого числа мы имеем Ф(31)= 1010010. Полученное представление оканчивается одним нулем. Значит, представление, парное к нему, получается в результате отбрасывания последнего нуля, т. е. будет 101001; оно является фибоначчиевым представлением числа 13 + 5+1 = 19.

18. Попытаемся изгнать из описания полученного решения игры Г последние заключенные в фибоначчиевых представлениях остатки рекуррентности. Как естественно ожидать (см., например, вывод формулы Бине в п. 16 § 1), это будет связано с использованием

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

Лемма. Пусть у и 6 — положительные иррациональные числа, для которых

(4.11)

Тогда в двойной серии чисел

(4.12)

(где квадратные скобки означают целую часть стоящих внутри них чисел) любое натуральное число встретится ровно по разу.

Доказательство. Заметим прежде всего, что Y, Ô > 1. Возьмем далее произвольное натуральное N и рассмотрим все натуральные значения л, для которых [пу] < N, т.е. пу < N, или п < так что этому неравенству удовлетворяют все натуральные числа п = 1, 2, • ••i[y]-

Аналогично для всех л=*1, 2, • ••»[-y-] будет [по] < N. Значит, среди чисел 1, 2, N будет всего ["7"] + [т"] чисел вида ^4Л2^ Но числа ТИ"Т Не являются целыми. Значит,

Поэтому, складывая эти неравенства и учитывая (4.11), мы получаем

Значит, средняя часть написанного соотношения есть целое число, лежащее строго между N — 2 и N. Таким числом является N— 1:

Таким образом, для любого натурального N среди чисел, меньших N, будет ровно N — 1 чисел вида (4.12): ими будут все натуральные числа, меньшие N4 Нам остается сослаться на произвольность числа N.

19. Пары чисел ([пу], [п&]) удовлетворяют условиям 1)—3) теоремы п. 15. Чтобы они удовлетворяли также условиям 4) и 5) этой теоремы, нужно, чтобы при любом натуральном п было

Ьп — ап= [пЬ] — [пу] =п.

Но так как

это равносильно тому, чтобы при любом п было [/гб] = [л(1 + Y)]. Если теперь 6=^ 1+у, то найдется

столь большое пу что числа по и п( \ -fv) будут отличаться более чем на единицу, так что будет [пЬ]ф Ф [п( 1 + у) ], а это не так. Значит, Ô = 1 -J- у и ввиду (4.11) мы имеем

Отсюда следует, что 2у + 1 = у (у + 1), или у2 — у — 1=0.

Поэтому и ввиду положительности y —

Таким образом, координаты выигрывающих позиций в игре Г поддаются непосредственному вычислению как пары 20. Закончим наше изложение небольшой геометрической шуткой. Сейчас мы наглядно «докажем», что 64 = 65. Возьмем для этого квадрат со стороной 3 и разрежем его на четыре части, как это показано на рис. 16. Эти части мы сложим в прямоугольник (рис. 17) со сторонами 13 и 5, т. е. с площадью, равной 65.

Объяснение этому, на первый взгляд загадочному, явлению найти нетрудно. Все дело в том, что точки

Рис. 16.

Рис. 17

Л, ß, С и D на рис. 17 на самом деле не лежат на одной прямой, а являются вершинами параллелограмма, площадь которого как раз и равна «лишней» единице.

Это правдоподобное, но неверное «доказательство» заведомо ложного высказывания (такие «доказательства» называются софизмами), можно проделать еще более наглядно и «убедительно», если вместо квадрата со стороной 8 взять квадрат со стороной, равной некоторому числу Фибоначчи с достаточно большим четным номером, г/2я. Разобьем этот квадрат на части (рис. 18) и сложим из этих частей прямоугольник (рис. 19). «Пустота» в виде параллелограмма, вытянутого вдоль диагонали прямоугольника, на основании п. 9 § 1 имеет площадь, равную единице. Наибольшая ширина этой щели, т. е. высота параллелограмма, равна, как легко вычислить,

Рис. 18. Рис, 19.

Поэтому если мы возьмем квадрат со стороной 21 см и «превратим» его в прямоугольник со сторонами 34 и 13 см, то наибольшая ширина щели получится

т. е. около 0,4 мм, что почти незаметно для глаза,

§ 5. ЧИСЛА ФИБОНАЧЧИ И ТЕОРИЯ ПОИСКА

1. Известно, что при очень малых скоростях автомобиль расходует на каждый километр пути сравнительно много бензина. Велик его расход и на больших скоростях. Какая-то промежуточная скорость является при этом «оптимальной»: при передвижении с этой скоростью автомобиль расходует на километр пути наименьшее количество горючего. Таким образом, мы можем предполагать, что примерный график зависимости расхода автомобилем горючего на километр пути от скорости автомобиля имеет вид, изображенный на рис. 20: сначала, по мере роста скорости, километровый расход горючего убывает до некоторой минимальной величины, а потом, с дальнейшим ростом скорости, начинает неуклонно (как принято говорить в математике, «монотонно») возрастать.

Хотя общие очертания графика этой зависимости (сначала спуск, а потом подъем) одинаковы практически для всех автомобилей, его точная форма может несколько изменяться даже в пределах автомобилей одного типа, завися от индивидуальных особенностей машины, от степени износа тех или иных ее механизмов и устройств и т. д. В частности, и минимум на нашем графике также может располагаться в довольно широких пределах.

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

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

Рис. 20.

с различными скоростями километровые участки дороги, характер и качество которой типичны для условий предстоящего путешествия, и замеряя каждый раз расход бензина. Так как это занятие не из веселых, естественно задуматься над следующими вопросами: сколько опытов достаточно поставить для того, чтобы определить наиболее экономичную скорость автомобиля с заданной точностью? На каких скоростях следует определять в этих опытах расходы горючего? Близкими к этим вопросам являются следующие два: как организовать данное число опытов, чтобы найти экономичную скорость с наибольшей точностью? Какова эта наибольшая точность?

При этом под определением наиболее экономичной скорости «с точностью до данного е» мы будем понимать указание такой скорости v, что истинное значение наиболее экономичной скорости лежит между v — е и v + е (т. е. что ошибка в определении этой скорости не может превосходить е).

Для определенности будем считать заранее известным, что наиболее экономичная скорость нашего автомобиля лежит между некоторыми пределами v' и v". В качестве v' следует взять скорость, которая заведомо не превосходит наиболее экономичной, а в качестве v" — такую скорость, которая заведомо не меньше ее. (Например, в качестве v' можно взять наименьшую скорость, при которой еще возможна устойчивая работа мотора, а в качестве v" — максимальную скорость данного автомобиля.)

2. Отвлекаясь от описанного только что конкретного примера, рассмотрим следующую математическую задачу.

Пусть нам о функции f(x) известно только то, что она от заданного х' до некоторого неизвестного х убывает, а от этого X до заданного х" возрастает (рис 21). В частности, мы допускаем, что неизвестная точка X в действительности совпадает с одним из концов отрезка, х' или х". Очевидно, в этом случае функция будет все время возрастать (рис. 22) или все время убывать (рис 23). Разумеется, если один из последних двух случаев и имеет место, то мы будем предполагать это обстоятельство заранее не известным. В точке X функция / принимает свое наименьшее

значение f(x), которое называется ее «минимальным» значением или, короче, минимумом. О точке х обычно в таких случаях говорят, что на ней функция достигает минимума. Ее также часто называют «минимизирующей» точкой функции.

Рис. 21. Ркс. 22.

Итак, мы далее будем рассматривать только такие функции, в которых убывание не может следовать за возрастанием. Такие функции мы будем в дальнейшем для краткости называть «функциями с одним минимумом».

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

3. В поставленной проблеме, как и в широком круге аналогичных ей проблем, участвуют три фактора: цели, которые мы перед собой ставим, возмож-

Рис 23.

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

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

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

Наконец, условия определяются величиной области задания функции /, т. е. длиной L отрезка между л' и х".

В соответствии со сказанным каждая конкретная задача поиска может иметь три аспекта.

1) Насколько осуществима поставленная цель при данных возможностях и в данных условиях? Применительно к интересующему нас вопросу это означает следующее.

Пусть мы имеем право совершить п последовательных определений значения /, выбирая каждый раз точку определения по своему усмотрению. В каких точках следует определять значения функции, чтобы точка X определилась с наибольшей точностью, и какова эта точность?

2) Какими возможностями необходимо располагать, чтобы осуществить поставленную цель в данных условиях?

В нашей задаче этот вопрос можно конкретизировать так. Пусть мы хотим определить минимизирующую функцию / точку X с заданной точностью е, т. е. указать такое х, что х расположено между х — 8 и X + е. Сколько определений значений функции / для этого необходимо произвести и как эти определения организовать?

3) В каких условиях данные возможности достаточны для достижения поставленной цели?

В данном случае речь идет о нахождении наибольшего интервала L изменения функции / (т. е. наибольшего значения разности х" — лс'), для которого суще-

ствует способ определения минимизирующей f точки с заданной точностью е за п наблюдений.

4. Строго говоря, нам придется сейчас иметь дело не с одной задачей, а с двумя.

Во-первых, речь может идти о нахождении минимизирующей точки X вместе с тем значением f{x), которое функция в этой точке принимает.

Во-вторых, мы можем интересоваться только самой точкой ху оставаясь равнодушным к значению f(x).

Совершенно ясно, что в первой из этих задач (будем далее ее называть задачей А) наши цели шире, чем во второй (которую мы назовем задачей Б). Поэтому естественно ожидать:

что при заданных возможностях и условиях цели задачи А удастся осуществить в меньшей степени, чем цели задачи Б (при данном числе п и длине L в задаче Б удается получить меньшее е, чем в задаче А)\ что для осуществления в равной мере целей обеих задач при одинаковых условиях в задаче А необходимы большие возможности (при одной и той же погрешности е и одинаковых длинах L интервалов изменения функции в задаче А необходимо, вообще говоря, большее п) ; что одинаковое осуществление целей при равных возможностях требует в задаче А более легких условий (данные е и п в задаче А совместимы лишь с меньшими значениями L, чем в задаче Б).

5. Чтобы сделать сформулированные задачи математически вполне четкими, необходимо разъяснить следующее важное обстоятельство.

Допустим, что мы интересуемся возможностями определения минимизирующей точки X в отрезке длины L (очевидно, мы можем считать началом этого отрезка точку 0 на оси координат, а концом — точку L) с точностью е. Будем считать, что мы решаем задачу Л, т. е. что х интересует нас вместе со значением f{x).

Рис. 24.

Предположим, что мы избрали следующий способ определения х.

Выберем совершенно произвольно некоторое х между 0 и L и определим значения функции / в точках X — е,хих|е, т. е. вычислим величины (рис. 24). Разумеется, при всей произвольности выбора X мы считаем, что все-таки х — е ^ 0, так что значение функции f(x — е) можно фактически вычислить; точно так же мы принимаем, что х + е :g L. Вполне может случиться, что

f(x-e)> f(x)<f(x + B).

Это значит, что функция /, убывающая в х — е, при переходе к х + е начинает возрастать. Но переход от убывания функции к возрастанию неизбежно связан с ее прохождением через наименьшее значение. В данном случае это наименьшее значение функции / должно достигаться на некотором Ху лежащем между X — е и X + е.

Поэтому X будет отстоять от X не более, чем на е, и х окажется как раз тем приближенным значением х, которое мы ищем. В этом случае определение искомого X осуществляется в результате всего-навсего трех наблюдений. Такое, повторяем, может случиться. Однако никакой гарантии того, что это действительно произойдет, мы не имеем. Более того, если длина L отрезка велика, а е мало, то наступление этого явления может показаться довольно неожиданным. Наоборот, в этом случае вполне правдоподобно, что вблизи трех выбранных нами точек функция / будет принимать сравнительно большие значения, а минимума своего она будет достигать где-нибудь совсем в другом месте. Следовательно, трех наблюдений может хватить, а может и не хватить,

Рис. 25.

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

/(0), /(е), /(28), ... (5.1)

до тех пор, пока не дойдем до такого /(re), что (r-f- 1)е будет больше, чем L (рис. 25). Ясно, что то Ае, для которого значение функции будет наименьшим в последовательности (5.1), и окажется искомым.

Смысл решаемых нами задач состоит в том, что мы хотим составить не просто план действий, дающий во всех и в том числе в наименее благоприятных случаях жизни значение х с предписанной точностью, а наиболее экономичный из таких планов, т. е. план, «наилучший в наихудших условиях». Но наихудшими условиями являются те, в которых число вычисляемых значений функции / максимально. Аналогично наиболее экономичным планом является такой план, который осуществляет поставленную цель с минимальным числом вычислений значений функции.

Поэтому наилучший в наихудших условиях план часто называют минимаксимальным планом, или планом минимакса. Мы будем этот план называть оптимальным.

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

6. Важно отметить, что не для всякой задачи поиска существуют оптимальные планы. Так, например, в задаче Б оптимального плана нет.

В самом деле, пусть L = 2 и п = 2. Какую точность определения 8 мы можем при этом гарантировать?

Будем считать концами нашего отрезка числа О и 2. Возьмем произвольно малое положительное е и вычислим значения функции / в точках 1 —ей Если при этом

f(l-e)âf(l+e),

то искомый минимум X должен лежать между нулем и 1 + е, а если

/(l-e)ü£/(l + e),

то X расположено между 1 — ей 2. Положим в первом случае

а во втором —

В наихудшем случае так определяемое х отличается от истинного минимума функции / на —~-.

Приближая е к нулю, мы уменьшаем ошибку. Однако е не может обратиться в нуль (ибо тогда точки 1—е и 1+е совпадут, и сравнение значения функции /(1—г) с заведомо равным ему значением f(l+e), вычисленным в той же точке, не даст нам никакой информации). Поэтому погрешность всегда остается большей, чем половина, хотя и может быть сделана сколь угодно близкой к этому числу.

Каждое положительное значение е определяет здесь некоторый план. Чем ближе е к нулю, тем этот план лучше. Так как для любого е > 0 найдется еще меньшее положительное число, для любого плана найдется еще лучший. Следовательно, оптимального плана для задачи Б нет.

Однако для задачи Б существуют «почти оптимальные» планы, приводящие к таким результатам, которые можно улучшить лишь незначительно. Говоря точнее, каково бы ни было число у > О, существует такой план PY, что никакой другой план не сможет уменьшить даваемую планом PY ошибку больше, чем на у.

7. План, описываемый последовательностью (5.1) при е, достаточно малом по сравнению с длиной L рассматриваемого нами отрезка, оптимальным не яв-

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

Попробуем, однако, поступить несколько иначе. Будем вычислять члены последовательности (5.1) через один:

/(0), /(2е), /(4е),

найдем в полученной последовательности наименьший из членов (пусть им будет f(2ke)) и вычислим два значения функции f((2k — 1)е) и /((2&+1)е). То из трех значений переменной (2k—1)е, 2/ге и (2k + 1)е, при котором значение функции / будет наименьшим из трех:

/((2А-1)е), f(2*e), /((2Ä+l)e),

очевидно, и есть х с точностью до е. Этот новый план приводит в наихудших условиях к цели после выполнения примерно — +2 вычислений. При больших г это существенно меньше, чем число вычислений, требуемых первым планом.

Итак, первый план не является оптимальным. По сходным причинам второй план также нельзя, вообще говоря, считать оптимальным.

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

Естественно в процессе определения местонахождения минимума функции сравнивать каждое вновь получаемое значение функции с теми или иными из ее значений, полученных при предыдущих наблюдениях. Выбор точки, в которой будет производиться следующее измерение (или решение о прекращении дальнейших измерений), будет поэтому как-то

зависеть, во-первых, от тех точек, в которых значения функции нами вычислены, а во-вторых, от самих вычисленных значений функции.

Очевидно, такой процесс последовательного вычисления значений функции / вполне определяется некоторым законом, ставящим в соответствие для любого k ^ О произвольным наборам точек А'ь *2, ..., Xk и значении функции f в этих точках ту или иную точку Xk+i или же решение закончить наблюдения над функцией /, приняв ту или иную точку в качестве х. Этот закон соответствия принято называть решающей функцией.

Каждый план определяет некоторую решающую функцию. Точно так же и всякая решающая функция определяет некоторый план. В сущности, решающая функция — это и есть четкое и формализованное описание плана. Например, решающая функция, определяющая первый из рассмотренных в предыдущем пункте планов, ставит в соответствие каждому числу 0 ^ k < г точку (k + 1)е, а числу г — окончание процесса.

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

8. Пусть цель плана Р состоит в определении с наименьшей погрешностью точки х, минимизирующей функцию f на отрезке длины L на основе п наблюдений. Такой план мы далее будем называть п-шаговым.

Пусть в условиях некоторого я-шагового плана Р удается определить х на отрезке длины L с точностью до е. Эта точность зависит от самого плана Р, а также от п и от L. Поэтому мы можем считать ее функцией от Р, п и L и обозначать для задачи А через тр(п9 L), а для задачи Б — через тр(п, L). Под тя(л, L) далее будет подниматься любое (но, конечно, в пределах одного рассуждения одно и то же) из выражений *p{n,L) и 4(n,L).

я-шаговый план Р0 определения минимума / на отрезке длины L является оптимальным в задаче Л, если тр0(м, L) не более, чем ip{ntL) для любого другого плана Р, т. е.

тр.(п, L)^4{n, L). Это можно также записать как

%р9 {п, L) =min хр (я, L). (5.2)

Число tp0(nfL), таким образом, оказывается характеристикой уже не плана, а самой задачи (именно, задачи нахождения за п шагов минимизирующей точки функции / на отрезке длины L). Поэтому оно не зависит от какого-либо плана, а зависит только от п и L и может быть просто обозначено через хА(п, L).

В условиях задачи Б дело обстоит несколько сложнее. Здесь, как мы уже видели, нет оптимального плана, гарантирующего в наихудших условиях наименьшую погрешность. Однако существует такая погрешность, к которой можно подойти сколь угодно близко, если только выбрать подходящий план. Эта погрешность, которую естественно называть предельной погрешностью, также зависит только от условий задачи. Поэтому ее естественно обозначить через тБ(пуЬ). Любой план приводит к большей погрешности:

TB(n,L)<4(n,L),

и поэтому мы не можем написать здесь равенство, аналогичное (5.2).

Забегая несколько вперед, скажем, что итог всех рассуждений этого параграфа, подчас довольно сложных, состоит в получении явных выражений для тА(п, L) и хБ (п, L). Как окажется, в эти выражения входят числа Фибоначчи:

*A(n>v=iâr> <5-3>

-Б^^=ъЬ- <5-4>

Таким образом, отказ от нахождения минимального значения функции позволяет увеличить точность определения ее минимизирующей точки в 2^n*J раз.

Для достаточно больших п это отношение согласно п. 26 § 1 близко к — = 1,236, что соответствует увеet ^

личению точности примерно на 23%.

9. Совершенно ясно, что для всех дальнейших рассуждений важны не каждое из чисел L и е само по себе, а отношение L и е. Это отношение является

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

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

Изменение масштаба вдоль оси х изменяет как численное выражение длины отрезка L, так и ошибку в определении положения искомой точки любым планом Р в одно и то же число раз. Другими словами, для любого положительного X должно быть

rr(n>lL)=XTp(nfL). (5.5)

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

Отсюда непосредственно следует, что равномерное растяжение (или сжатие) интервала изменения функции / в любое число раз осуществляет лишь «подобное преобразование» оптимального плана, не нарушая при этом его оптимальности.

Значит, ошибки тр(п,ХЦ и тр(я, L), фигурирующие в равенстве (5.5), достигаются не просто в результате осуществления тех или иных планов, а могут быть достигнуты в результате применения одного и того же плана, различным образом «подобно преобразованного».

10. После всех этих достаточно затянувшихся предварительных рассмотрений перейдем к нахождению оптимального плана для задачи Лик доказательству формул (5.3) и (5.4).

Лемма. Каковы бы ни были п ^ 1 и L, существует пошаговый план поиска точки х, минимизирующей значение функции f (с одним минимумом) на отрезке длины L за п шагов, обладающий следующими свойствами:

1) на каждом шаге рассматривается некоторый отрезок х'х"\

2) на первом шаге вычисляется значение функции f в одной из точек: Пп L или -^£Î±J- L;

"rt+2 Un+2

3) к началу каждого из последующих шагов с номером k (т. е. при 1 <С k =g п) известно значение f в одной из следующих точек:

хЛ = х' + -^—(х" - х') и хо = х' + -т2±1 _ ху9

(5.6)

4) на k'm (1 < k шаге вычисляется значение в другой из точек (5.6);

5) на k'm (1 < k g* л) шаге производится сравнение чисел f(xi) и f(x2)\ при этом, если окажется, что ff(хъ), то на (k+l)-m шаге рассматривается отрезок х'х2, а если f(x\)^.f(x%)t то отрезок х\х".

Доказательство ведется индукцией по п. Если п—\, то, очевидно, мы имеем дело с отрезком от 0 до L; значение функции ( вычисляется в точке — L=-7p; последующих же шагов в этом случае вообще нет.

Предположим теперь, что существование некоторого /2-шагового плана с требуемыми в условиях леммы свойствами нами уже установлено для любого отрезка. Займемся построением интересующего нас (п + 1) -шагового плана, проверяя параллельно соблюдение условий леммы. Будем на каждом шаге рассматривать некоторый отрезок х'х".

Возьмем в качестве первого шага выбор точки X —ln±L.i 2l в качестве второго—выбор точки х2 = "п*2 L и сравнение значений, функции f(x\) и f{x2). В случае, когда f(x\)^f{x2)t мы приходим к рассмотрению отрезка между 0 и х2 (здесь 0 играет роль х\ а х2 — роль я"), а в случае /(*i)>/(*2)— к рассмотрению отрезка между х\ и L (здесь х\ выступает в роли х', a L в роли х"). Длина рассматриваемого отрезка в обоих случаях равна иип'*2 L.

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

Именно, на отрезке длины Ufl*2 L известно значение функции / в точке, отстоящей на Un+l L от одного из его концов. Поэтому мы можем «перейти» на этот я-шаговый процесс и довести его до конца. На основании индуктивного предположения мы можем считать, что для последних п шагов выполняются условия 3), 4) и 5). Следовательно, нам остается рассмотреть условия начала второго шага и его проведения. Но, очевидно, точка "n+ï L имеет вид первого из выражений (5.6) для случая k — 2, если вместо п в него подставить а роль второго выражения в соответствующей ситуации играет выбираемая нами точка L.

Этим индуктивный переход обоснован и лемма доказана.

II. Будем называть /г-шаговый план, существование которого было доказано в предыдущей лемме, пошаговым фибоначчиевым планом, или, короче, планом Ф„.

Теорема. 1 ) План Фп является единственным оптимальным п-шаговым планом,

2) 4 („,*,) =.

"r + 2

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

Рассмотрим сначала одношаговый план, состоящий в выборе в качестве х некоторой точки х из интервала от х' до х". Очевидно, в наименее благоприятных условиях ошибка может достигнуть здесь наибольшего из чисел х" — х и х — х'. Если эти числа различны, то эта максимальная ошибка превосходит •у, если же они равны, то максимальная ошибка L равна -у.

Таким образом, план Фх является оптимальным одношаговым планом, а

При п — 2 мы имеем дело с планом Фг, состоящим в вычислении и сравнении значений функции /(yL) и / (у^) и выбора в качестве х точки

Максимальная ошибка в определении истинного значения а* здесь, как легко видеть, достигает -ô- =— :

Любой иной выбор точки будет приводить к большим возможным ошибкам.

Основание индукции, таким образом, доказано.

Предположим теперь, что фибоначчиев план Фп обладает требуемым в условиях теоремы свойством, и рассмотрим (n+ 1)-шаговые планы.

Произведя в плане Ф,г+1 первые два наблюдения над функцией /, мы в результате сравнения двух ее найденных значений сведем дело к применению к отрезку длины 11/1+2 I, в котором известно значение в одной из точек, плана Ф,ь что даст нам в наименее благоприятном случае ошибку

Следовательно,

Нам остается показать, что план Фл+1 оптимален.

Возьмем с этой целью наблюдения над функцией / в двух произвольных точках, х\ и х2 (для определенности будем считать, что х\ < х2). Сопоставление значения f(xi) с f(x2) приводит к поискам точки х либо на отрезке от 0 до х2у либо на отрезке от Х[ до L.

Если

то в случае f(*i)>f(-V2) нам придется искать по некоторому «-шаговому плану минимизирующую / точку

на отрезке длины L — х\, т. е. большей, чем

Даже если положение точки х2 на этом отрезке наиболее благоприятно, то ошибка в определении окажется на основании индуктивного предположения

большей, чем —-—.

Симметричные рассуждения показывают, что план, начинающийся выбором некоторой точки также может при соответствующих неблагоприятных условиях привести к большей ошибке в определении X, чем план Ф,г+ь Пусть теперь

Если в действительности х находится между 0 и х\, то на поиски местоположения этой точки нам остается п — 1 наблюдение, а длина отрезка, заключающего эту точку, больше, чем Un+] L. Значит, даже план Фп-1 (который, по предположению, в этих условиях оптимален) приведет нас к ошибке, большей, чем

Симметрично разбирается случай, когда

Следовательно, план ФЛ+1 является оптимальным, и теорема доказана.

Итак, единственная минимизирующая функцию / точка может быть с помощью п наблюдений определена на отрезке длины L с ошибкой, не превосходяшй -.

Поэтому п наблюдений позволяют определить точку, минимизирующую /, с ошибкой е или меньше, на отрезке, длина которого не превосходит е««+2-

Наконец, чтобы быть уверенным в том, что точка, минимизирующая функцию /, определена на отрезке длины L с ошибкой, не превосходящей е, необходимо произвести такое число п наблюдений, что

Таким образом, мы ответили на все вопросы п. 3.

12. Решение задачи Б можно получить из описанного выше решения задачи А без особого труда.

Пусть нам дан отрезок длины L. Проделаем на этом отрезке первые п — 2 шага фибоначчиева плана Фп-i. В результате мы придем к отрезку длины ^L с концами х' и х" и с известным значением / в одной из точек х\ — х' H--— или х2 — х' H--—. Ограничимся рассмотрением первого из этих случаев (второй рассматривается симметрично).

Итак, пусть f(x\) нам уже известно. Выберем произвольное число у, по абсолютной величине меньшее, чем L ; вычислим f(x2— у) (это есть (п—1)-е вычисленное значение функции f) и сравним f(x\) и f(x2 — y).

Если f{xi)^f(x2 — у) (случай о на рис. 26), то, очевидно, X находится между х' и х2—7. Вычислим

(это — последнее, я-е вычисленное значение функции f).

Если при этом

Рис. 26.

(случай X на Рис- 26), то X расположено между х' и Х\. Положим х=—у—2-- Ошибка в определении х не превосходит половины длины отрезка от х* до хи т. е. ~~—. Если

2l„-L.

(случай о на рис. 26), то х находится между хх —j и х2— y- Положив X = y ^jc, — + (х% — y)) » мы совершим ошибку, не большую, чем

Пусть теперь f(x\)>f(x2 — y) (рис. 27). Тогда £ находится между х\ и

Вычислим /(jt2) (последнее вычисленное значение /). Если

f(x2-y)^f(x2)

(случай « на рис. 27), то л: расположено между х{ и х2; беря x = у (х! + jc2), мы допустим ошибку, достигающую разве лишь -~ \х2 — *i) = и-•

Если, наконец,

(случай Х на рис. 27), то х расположено между х2—у и х"\ положив X = у (х" + (х2 — у)), мы совершаем ошибку, не превосходящую

Рис. 27.

В наихудшем для нас случае при y > 0 ошибка может таким образом достигнуть величины + -£,a при y<0 — величины-^---— .Поскольку,

однако, число y находится в нашем распоряжении, мы можем сделать ошибку, сколь угодно близкой L

Нам остается убедиться в том, что ошибку ^г—— уменьшить нельзя.

В самом деле, отклонения от описанного плана на каком-либо из первых п — 2 шагов могут привести, как видно из теоремы п. 11, только к увеличению длины отрезка, в котором местоположение минимизирующей точки определяется последующими измерениями, и тем самым к заведомому увеличению максимальной ошибки. Остается проверить оптимальность действий, совершаемых на последних двух шагах.

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

Далее, мы могли бы выбрать для последнего определения / точку, не близкую к точке х\ (или соответственно к л'2). Но тогда возможная ошибка увеличилась бы и притом пропорционально расстоянию между этими точками.

Наконец, к таким же последствиям привел бы выбор точки для предпоследнего определения /, далекой от а*2 (соответственно от х\).

Итак, ни одно из отклонений от описанного плана не может повлечь за собой уменьшения возможной ошибки до числа, меньшего, чем —. Это показывает, что задача Б нами решена.

Мы предоставляем читателю сформулировать в случае задачи Б ответы на остальные вопросы, перечисленные в п. 3.

13. В предыдущих пунктах описание самого плана поиска сопровождалось уточнениями постановки

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

План наиболее точных поисков на отрезке от х' до х" точки X, минимизирующей функцию / в условиях задачи Л, в изложении, преследующем только что описанные, так сказать, «практические» цели, напоминает план установления вида растения по ботаническому определителю (заметим, что определение растения есть тоже поиск!). Он принимает следующий вид (если в конце пункта не указывается, к какому пункту следует переходить, то нужно переходить к следующему пункту) :

Г. Сравнить 1 и п:

а) если п = 1, то перейти к п. 2°;

б) если п > 1, то перейти к п. 4°.

2°. Вычислить X = х ~х .

3°. Вычислить 1(х)\ на этом процесс кончается, 4°. Вычислить

5°. Вычислить/(xi) иДхг). 6°. Сравнить 2 и п:

а) если п = 2, то перейти к п. 7°;

б) если п > 2, то перейти к п. 10°.

7°. Сравнить f(X{) и f(x2):

а) если f(x\) ^ f{x2), то перейти к п. 8°; б) если f(xi) > f(x2), то перейти к п. 9°.

8°. Положить X = х\ и закончить процесс.

9°. Положить X = х2 и закончить процесс. 10°. Сравнить и/(х2):

а) если /(ati)^ /U'2), то перейти к п. 11°;

б) если /(a'i) > f(x2), то перейти к п. 14°. 11°. Переобозначить х2 через х"> Xi через лг2, п — 1 через п.

12°. Вычислить

13°. Вычислить /(xi) и перейти к п. 6°. 14°. Переобозначить

15°. Вычислить

16°. Вычислить f(x2) и перейти к п. 6°

14. Хотя сформулированное описание оптимального плана поисков минимума функции / абсолютно четкое, не оставляющее места какому-либо произволу, и в применении к каждой конкретной функции /, отрезку от х' до х" и числу п предписывает совершенно точную последовательность действий, оно является довольно запутанным и трудно обозримым.

Приведем поэтому для наглядности еще одно описание этого же плана в виде некоторой графической схемы (рис. 28).

Схемы такого рода обычно называются блок-схемами. Составление блок-схемы вычислительного процесса обычно является первым этапом при составлении программы проведения вычислений на электронных цифровых вычислительных машинах.

15. Приведем в заключение пример использования описанного в пп, 13 и 14 плана для нахождения

Рис. 28.

с помощью пяти вычислений на отрезке от 1 до 2 точки х, минимизирующей функцию

Предварительно сделаем важное замечание.

Нахождение точки, минимизирующей (или максимизирующей) функцию, которая задана аналитически (т. е. в виде формулы, позволяющей вычислять ее значения), обычно удобнее проводить не методами теории поиска, а другими, более приспособленными для этого приемами, которые относятся к дифференциальному исчислению. Поэтому следует иметь в виду, что приводимый далее пример носит чисто иллюстративный характер. Дифференциальное исчисление позволяет без труда показать, что в этом случае л' = ^4= 1,5874011 ...Нам же удастся найти значительно более грубое приближение. Однако в тех случаях, когда заранее о функции нам неизвестно ничего (кроме того, что она не может переходить от возрастания к убыванию) или же выражения, которыми она задается, чересчур сложны, методика дифференциального исчисления неприменима, и теория поиска оказывается полезным инструментом.

1°. Сравнение п = 5 и 1 дает нам, что пф\\ поэтому переходим к п. 4°.

4°. Вычисляем:

5е. Вычисляем:

6°. Сравнение п = 5 и 2 дает, что пф2\ поэтому переходим к п. 10°,

10°. Сравнение

дает нам f(x{) > /(х2) ; поэтому переходим к п. 14°.

14°. Переобозначаем:

15°. Вычисляем:

16°. Вычисляем:

и переходим к п. 6°.

6°. Сравниваем п — 4 и 2; поскольку п ф 2, переходим к п. 10°.

10°. Сравниваем f(x{)= 1,89003 и f(x2) = 1,89534; поскольку f(x\)^ f{x2), переходим к п. 11°.

11°. Переобозначаем:

12°. Вычисляем:

13°. Вычисляем:

и переходим к п. 6°.

6°. Сравниваем п = 3 и 2; поскольку пф2% переходим к п. 10°.

10?. Сравниваем

поскольку /(xi)> f(x2)y переходим к п. 14°, 14°. Переобозначаем:

15°. Вычисляем:

16°. Вычисляем

и переходим к п. 6°.

6°. Сравнение п и 2 дает нам, что п = 2; переходим к п. 7°.

7°. Сравниваем

f(xi)= 1,89003 и f{x2) = 1,89170;

/(a'i)S=ê /(#2); поэтому переходим к п. 8. 8°. Полагаем х = 1,61538.

На основании теоремы п. 11 найденное нами, х может отличаться от истинного положения минимизирующей точки не более чем на -= — = — = 0, 077. Фактически эта ошибка оказывается меньшей; она равна 0,028. Заметим, что принимаемое нами за наименьшее значение функции /, т. е. f(x), равно 1,89003 и отличается от истинного наименьшего значения /, равного

лишь на 0,00015. Это показывает, что значения х можно было в ходе наших вычислений определять с меньшей точностью, чем значения f<

Сам по себе такой вывод не содержит ничего удивительного. В самом деле, значения х мы должны находить с той предельной точностью, с какой мы можем в наших условиях найти минимизирующую точку л: (мы знаем, что эта точность равна—-—V

Значения же функции f должны вычисляться с точностью, обеспечивающей сравнение пар значений этой функции и выделение из каждой такой пары наименьшего и наибольшего значения. Поэтому если в действительности какие-нибудь f(a) и f(b) сильно отличаются друг от друга, и это отличие заметно уже при грубом определении f(a) и f(b), то мы можем вычислять эти значения с малой точностью. Наоборот, если эти f(a) и f(b) в действительности близки, то для выяснения того, какое из них больше другого, приходится вести вычисление с большей точностью. Так как мы наперед (до фактического выполнения вычислений) не знаем, насколько отличаются друг от друга сравниваемые значения функции, мы можем «промахнуться» и вычислить их с недостаточной точностью, которая не даст возможности решить, какое из этих значений больше. В этом случае придется произвести повторные, более точные вычисления, затратив на это дополнительные усилия.

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

СОДЕРЖАНИЕ

Предисловие к первому изданию...........3

Предисловие к четвертому изданию.......... 5

Введение .................... 7

§ 1. Простейшие свойства чисел Фибоначчи.......11

§ 2. Теоретико-числовые свойства чисел Фибоначчи ... .39

§ 3. Числа Фибоначчи и непрерывные дроби.......71

§ 4. Числа Фибоначчи и геометрия..........94

§ 5. Числа Фибоначчи и теория поиска.........115

Николай Николаевич Воробьев

ЧИСЛА ФИБОНАЧЧИ

(Серия «Популярные лекции по математике»)

Редактор В. В. Донченко Техн. редактор И. Ш. Аксельрод Корректоры Н. Д. Дорохова, О. М. Кривенко

И Б Ni 12356

Сдано в набор 07.02.83. Подписано к печати 29.12.83. Формат 84Х103'/32. Бумага книжно-журнальная. Литературная гарнитура. Высокая печать. Условн. печ. л. 7,56. Условн. кр.-отт. 7,76. Уч.-изд. л. 7,07. Тираж 100 000 экз. Заказ №г 632. Цена 20 к.

Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15

Ленинградская типография № 2 головное предприятие ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 193052, г. Ленинград, Л-52, Измайловский проспект, 29.

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

Вып. 1. А. И. Маркушевич. Возвратные последовательности.

Вып. 2. И. П. Натансон. Простейшие задачи на максимум и минимум.

Вып. 3. И. С. Соминский. Метод математической индукции.

Вып. 4. А. И. Mаркушевич. Замечательные кривые.

Вып. 5. П. П. Коровки н. Неравенства,

Вып. 6. H. Н. Воробьев. Числа Фибоначчи.

Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных степеней.

Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.

Вып. 9. А. И. Маркушевич. Площади и логарифмы.

Вып. 10. А. С. Смогоржевский. Метод координат.

Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.

Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.

Вып. 13. А. И. Маркушевич. Комплексные числа и конформные отображения.

Вып. 14. А. И. Фетисов. О доказательствах в геометрии.

Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней.

Вып. 16. В. Г. Шерватов. Гиперболические функции.

Вып. 17. В. Г. Болтянский. Что такое дифференцирование?

Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.

Вып. 19. Л. А. Люстерник. Кратчайшие линии.

Вып. 20. А. М. Лопшиц. Вычисление площадей ориентированных фигур.

Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрии.

Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры.

Вып. 23. А. С. Смогоржевский. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные теоремы.

Вып. 25. А. С. Смогоржевский. Линейка в геометрических построениях.

Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач.

Вып. 27. В. А. Успенский, Некоторые приложения механики к математике.

Вып. 28. H. А. Архангельский и Б. И. Зайцев. Автоматические цифровые машины.

Вып. 29. А. Н. Костовский. Геометрические построения одним циркулем.

Вып. 30. Г. Е. Шилов. Как строить графики.

Вып. 31. А. Г. Дорфман. Оптика конических сечений.

Вып. 32. Е. С. Вентцель. Элементы теории игр.

Вып. 33. А. С. Барсов. Что такое линейное программирование.

Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.

Вып. 35. Н. Я. Виленкин. Метод последовательных приближении.

Вып. 36. В. Г. Болтянский. Огибающая.

Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной шкалы).

Вып. 38. Ю. А. Шрейдер. Что такое расстояние.

Вып. 39. H. Н. Воробьев. Признаки делимости.

Вып. 40. С. В. Фомин. Системы счисления.

Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.

Вып. 42. Ю. И. Любич и Л. А. Шор. Кинематический метод в геометрических задачах.

Вып. 43. В. А. Успенский. Треугольник Паскаля.

Вып. 44. И. Я. Бакельман. Инверсия.

Вып. 45. И. М. Яглом. Необыкновенная алгебра.

Вып. 46. И. М. Соболь. Метод Монте-Карло.

Вып. 47. Л. А. Калужнин. Основная теорема арифметики.

Вып. 48. А. С. Солодовников. Системы линейных неравенств.

Вып. 49. Г. Е. Шилов. Математический анализ в области рациональных функций.

Вып. 50. В. Г. Болтянский, И. Ц. Гохберг. Разбиение фигур на меньшие части.

Вып. 51. H. М. Бескин. Изображения пространственных фигур.

Вып. 52. H. М. Бескин. Деление отрезка в данном отношении.

Вып. 53. Б. А. Розенфельд и Н. Д. Сергеева. Стереографическая проекция.

Вып. 54. В. А. Успенский. Машина Поста.

Вып. 55. Л. Беран. Упорядоченные множества.

Вып. 56. С. А. Абрамов. Элементы программирования.

Вып. 57. В, А. Успенский. Теорема Гёделя о неполноте.