ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК 6
Н. Н. ВОРОБЬЕВ
ЧИСЛА ФИБОНАЧЧИ
ИЗДАНИЕ ЧЕТВЕРТОЕ, ДОПОЛНЕННОЕ
МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1978

Б17.1
В75
УДК 51192
©	Главная редакция
„ 20202 — 146 _. „	физико-математической литературн
В neQ,AO, -о ¦ 76-78	издательства «Наука»,
053@2)-78	1978, с изменениями.

ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ
В элементарной математике существует много
задач, часто трудных и интересных, которые не свя-
связаны с чьим-либо именем, а скорее носят характер
своего рода «математического фольклора». Такие
задачи рассыпаны по обширной популярной или про-
просто развлекательной математической литературе, и
часто бывает очень трудно установить, в каком имен-
именно сборнике появилась впервые та или иная задача.
Эти задачи нередко имеют хождение в нескольких
вариантах; иногда несколько таких задач объединяют
в одну, более сложную; иногда, наоборот, одна задача
распадается на несколько более простых; словом, ча-
часто оказывается трудно указать, где кончается одна
задача и где начинается другая. Правильнее всего
было бы считать, что в каждой из таких задач мы
имеем дело с маленькими математическими теориям»,
имеющими свою историю, свою проблематику и свои
методы, — все это, разумеется, тесно связанное с исто-
историей, проблематикой и методами «большой мате-
математики».
Такой теорией является и теория чисел Фибоначчи.
Выросшие из знаменитой «задачи о кроликах», имею-
имеющей почти семисотпятидесятилетнюю давность*), чис-
числа Фибоначчи до сих пор остаются одной из самых
увлекательных глав элементарной математики. Зада-
Задачи, связанные с числами Фибоначчи, приводятся во
многих популярных изданиях по математике, рассмат-
•) А сейчас, к моменту очередного издания данной брошю-
брошюры, — ровно семнсотпятидесятилетнюю давность.
3

риваются на занятиях школьных математических
кружков, предлагаются на математических олим-
олимпиадах.
Предлагаемая книжка содержит круг вопросов,
послуживших темой нескольких занятий матема-
математического кружка школьников при Ленинградском
государственном ордена Ленина университете
им. А. А. Жданова в 1949/50 учебном году. В соответ-
соответствии с желаниями участников кружка на этих заня-
занятиях рассматривалась преимущественно теоретико-
числовая сторона вопроса, которая развита более по-
подробно и в настоящей брошюре.
Книжка рассчитана в основном на школьников
9—10 классов. Понятие предела встречается здесь
только в пп. 8 и 9 § 3. Читатель, не знакомый с этим
понятием, может без ущерба для понимания дальней-
дальнейшего эти пункты при чтении пропустить. Сказанное
относится также к биномиальным коэффициентам
(пп. 11 —15 § 1) и к тригонометрии (пп. 3 и 4 § 4).
Излагаемые в брошюре элементы теории делимости
и теории непрерывных дробей никаких предваритель-
предварительных знаний, выходящих за рамки школьного курса,
у читателя не предполагают.
Читателям, которые заинтересуются самим прин-
принципом построения рекуррентных рядов, можно реко-
рекомендовать небольшую, но содержательную книжку
А. И. Маркушевича «Возвратные последовательно-
последовательности», «Наука», М, 1975. Тех же, кого заинтересуют
факты, относящиеся к теории чисел, можно отослать
к серьезным курсам по этой дисциплине.

ПРЕДИСЛОВИЕ К ЧЕТВЕРТОМУ ИЗДАНИЮ
Первый вариант текста этой книжки писался почти
тридцать лет тому назад. С тех пор изменилось очень
многое.
Прежде всего, и это главное, изменился математи-
математический уровень основного круга читателей популяр-
популярных математических книг: интересующихся матема-
математикой школьников старших классов и их преподавате-
преподавателей. Созданная сеть специализированных математиче-
математических и физико-математических школ и классов
предопределила существенное расширение математи-
математического кругозора соответствующего контингента
учащихся, которых теперь можно заинтересовать ско-
скорее не забавными элементарными фактами, а уже
достаточно глубокими и сложными результатами.
Кроме того, и это является фундаментальным
фактом истории математики нашего времени, суще-
существенно сместился центр тяжести математических ис-
исследований в целом. В частности, утратила свои до-
доминирующие позиции теория чисел, и резко повысился
удельный вес экстремальных задач. В самостоятель-
самостоятельную отрасль математики сложилась теория игр. По
существу возникла вычислительная математика. Все
это не могло не сказаться и на содержании научно-
популярной литературы по математике.
Далее, числа Фибоначчи проявили себя еще в не-
нескольких математических вопросах, среди которых в
первую очередь следует назвать решение Ю. В. Ма-
тиясевичем десятой проблемы Гильберта и далеко
не столь глубокую, но приобретшую широкую изве-
известность теорию поиска экстремума унимодальной
функции, построенную впервые, по-видимому, Р. Белл-
маном.

Наконец, было установлено довольно большое ко-
количество ранее неизвестных свойств чисел Фибоначчи,
а к самим числам существенно возрос интерес. Зна-
Значительное число связанных с математикой людей в
различных странах приобщились к благородному хоб-
хобби «фибоначчизма». Наиболее убедительным свиде-
свидетельством этому может служить журнал The Fibo-
Fibonacci Quarterly, издаваемый в США с 1963 г.
Все сказанное определило изменения содержания
книги от издания к изданию и тот вид, в котором она
предлагается читателю сейчас. Во втором издании был
добавлен параграф о фибоначчиевых планах поиска
экстремума унимодальной функции вместе с возни-
возникающими при этом общематематическими и вычисли-
вычислительными вопросами. В третьем издании была расши-
расширена теоретико-числовая тематика, и этот материал
из § 2 оказался полезной информацией при решении
десятой проблемы Гильберта. Наконец, в настоящем
издании «подтягиваются» до общего уровня и объема
§ 3 и 4. В § 3 приводятся ставшие классическими тео-
теоремы о точности приближений подходящими дробями
и описывается роль чисел Фибоначчи в этих фактах,
а в § 4 рассматривается игра «цзяньшицзы», теорети-
теоретико-игровой анализ которой опирается на детальное
рассмотрение фибоначчиевых представлений нату-
натуральных чисел.
Книга по-прежнему не требует от читателя знаний,
выходящих за пределы школьного курса. Более труд-
трудные ее места выделены мелким шрифтом и могут быть
при чтении пропущены без ущерба для понимания
остального материала.
Вырица 1	И. Н. Воробьев
1978 г.

ВВЕДЕНИЕ
1. Древняя история богата выдающимися матема-
математиками. Многие достижения древней математической
науки до сих пор вызывают восхищение остротой ума
их авторов, а имена Евклида, Архимеда, Герона из-
известны каждому образованному человеку.
Иначе обстоит дело с математикой средневековья.
Кроме Виеты, жившего, впрочем, уже в шестнадцатом
столетии, и математиков более близких нам времен
школьный курс математики не называет ни одного
имени, относящегося к средним векам. Это, конечно,
не случайно. Математика в эту этоху развивалась
чрезвычайно медленно, и крупных математиков тогда
было очень мало.
Тем больший интерес представляет для нас сочи-
сочинение «Liber abacci» («Книга об абаке»), написанная
знаменитым итальянским математиком Леонардо из
Пизы, который известен больше по своему прозвищу
Фибоначчи (Fibonacci-—сокращенное filius Bonacci,
т. е. сын Боиаччи). Эта книга, написанная в 1202 г.,
дошла до нас во втором своем варианте, который
относится к 1228 г.
«Liber abacci» представляет собой объемистый
труд, содержащий почти все арифметические и алге-
алгебраические сведения того времени и сыгравший за-
заметную роль в развитии математики в Западной
Европе в течение нескольких следующих столетий.
В частности, именно по этой книге европейцы позна-
познакомились с индусскими («арабскими») цифрами.
Сообщаемый в «Liber abacci» материал поясняется
на большом числе задач, составляющих значительную
часть этого трактата.

Рассмотрим одну такую зада-
задачу, помещенную на стр. 123—
124 рукописи 1228 г.
«Сколько пар кроликов в один
год от одной пары рождается?»
«Некто поместил пару кроли-
„ .	ков в некоем месте, огороженном
.ервыи	со всех СТОрОН стеНой, чтобы
2	узнать, сколько пар кроликов ро-
Пара
1
Второй
3
Третий
5
Четвертый
8
в этом месяце окажутся 2 пары;
Пятый	из них одна пара, а именно пер-
13
Шестой
21
Седьмой
34
Восьмой
55
Девятый
89
Десятый
144
Одиннадцатый
Двенадцатый
377
дится при этом в течение года,
если природа кроликов такова,
что через месяц пара кроликов
производит на свет другую пару,
а рождают кролики со второго
месяца после своего рождения.
Так как первая пара в первом
месяце дает потомство, удвой, и
вая, рождает и в следующем ме-
месяце, так что во втором месяце
оказывается 3 пары; из них в
следующем месяце 2 пары будут
давать потомство, так что в тре-
третьем месяце родятся еще 2 пары
кроликов, и число пар кроликов
в этом месяце достигнет 5; из
них в этом же месяце будут да-
давать потомство 3 пары, и число
пар кроликов в четвертом месяце
достигнет 8; из них 5 пар произ-
произведут другие 5 пар, которые, сло-
сложенные с 8 парами, дадут в пя-
пятом месяце 13 пар; из них 5 пар,
рожденных в этом месяце, не
дают в том же месяце потомства,
233	а остальные 8 пар рождают, так
что в шестом месяце оказывается
21 пара; сложенные с 13 парами,
которые родятся в седьмом ме-
месяце, они дают 34 пары; сложен-
сложенные с 21 парой, рожденной в
восьмом месяце, они дают в этом

месяце 55 пар; сложенные с 34 парами, рожденными
в девятом месяце, они дают 89 пар; сложенные вновь
с 55 парами, которые рождаются в десятом месяце,
они дают в этом месяце 144 пары; снова сложенные
с 89 парами, которые рождаются в одиннадцатом
месяце, они дают в этом месяце 233 пары; сложен-
сложенные вновь с 144 парами, рожденными в последнем
месяце, они дают 377 пар; столько пар произвела
первая пара в данном месте к концу одного года. Дейн
ствительно, на этих полях ты можешь увидеть, как
мы это делаем; именно, мы складываем первое число
со вторым, т. е. 1 и 2; и второе с третьим; и третье
с. четвертым; и четвертое с пятым; и так одно за дру-
другим, пока не сложим десятое с одиннадцатым, т. е.
144 с 233; и мы получим общее число упомянутых
кроликов, т. е. 377; и так можно делать по порядку до
бесконечного числа месяцев».
2. Перейдем теперь от кроликов к числам и рас-
рассмотрим следующую числовую последовательность:
щ, н2, ..., «„,	A)
в которой каждый член равен сумме двух предыду-
предыдущих членов, т. е. при всяком я > 2
"п = «»-1 + "»-2-	B)
, Такие последовательности, в которых каждый член
определяется как некоторая функция предыдущих,
часто встречаются в математике и называются рекур-
рекуррентными или, по-русски, возвратными последова-
последовательностями. Сам процесс последовательного опреде-
определения элементов таких последовательностей назы-
называется рекуррентным процессом, а равенство B) —
возвратным (рекуррентным) уравнением. Элементы
общей теории возвратных последовательностей чита-
читатель может найти в уже упоминавшейся книжке
А. И. Маркушевича (см. стр. 4).
Заметим прежде всего, что по одному только усло-
условию B) члены последовательности A) вычислять
нельзя. Можно составить сколько угодно различ-
различных числовых последовательностей, удовлетворяющих

этому условие; например, :	•
2, 5, 7, 12, 19, 31, 50, ...,
1, 3, 4, 7, И, 18, 29
-1, -5, -6, -11, -17
и т. д.
Значит, для однозначного построения последова-
последовательности A) условия B) явно недостаточно, и нам
следует указать некоторые дополнительные условия.
Например, мы можем задать несколько первых членов
последовательности A). Сколько же первых членов
последовательности A) мы должны задать, чтобы
можно было вычислять все следующие ее члены, поль-
пользуясь при этом только условием B)?
Начнем с того, что не всякий член последователь-
последовательности A) может быть получен при помощи B) уже
хотя бы потому, что не у каждого члена A) имеется
дна предшествующих; например, перед первым чле-
членом последовательности вообще не стоит ни одного
члена, а перед вторым ее членом стоит только один.
Значит, вместе с условием B) для определения после-
последовательности A) нам нужно знать два ее первых
члена.
Этого, очевидно, уже достаточно для того, чтобы
им1чь возможность вычислить любой член последова-
последовательности A). В самом деле, «3 можно вычислить
как сумму заданных нам и\ и нг; «4— как сумму и2 и
уже вычисленного ранее н3; «5 — как сумму уже вы-
вычисленных из и м4 и т. д. «по порядку до бесконечного
числа членов». Переходя таким образом от двух со-
с?дних членов последовательности к непосредственно
следующему за ними члену, мы можем дойти до члена
с любым наперед заданным номером и вычислить его.
3. Обратимся теперь к важному частному случаю
последовательности A), когда и\ = 1 и «2= 1- Усло-
Условие B), как было только что отмечено, дает нам
возможность вычислять последовательно один за дру-
другим все члены этого ряда. Нетрудно проверить, что
в этом случае первыми четырнадцатью его членами
будут числа
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
которые уже встречались нам в задаче о кроликах.
10

В честь автора этой задачи вся последовательность
A) при и\ = u2 = 1 называется рядом Фибоначчи,
а члены ее — числами Фибоначчи.
Числа Фибоначчи обладают целым рядом интерес-
интересных и важных свойств, рассмотрению которых и по-
посвящена вся эта книжка.
§ I. ПРОСТЕЙШИЕ СВОЙСТВА ЧИСЕЛ ФИБОНАЧЧИ
1. Вычислим сначала сумму первых п чисел Фи-
Фибоначчи. Именно, докажем, что
«1 + «2+ ••• +"и = «п+2— 1Т	0-1)
В самом деле, мы имеем:
и, = и3 — и2,
и2 = ы4 — щ,
=«5 —,
ыл-1 — ип+1 Чп,
"n=Un + 2 — Un + 1.
Сложив все эти равенства почленно, мы получим
«1 + «2+ ••• И- Un = Un+2 — U2,
и нам остается вспомнить, что и2 = 1.
2. Сумма чисел Фибоначчи с нечетными номерами:
Щ + Ы:, + «5+ ••• +п-1 = «-	A-2)
Для доказательства этого равенства напишем
«1 = «2.
«з =  — «2»
«5 = "б — ,
ы2я-1 — и2п — u2rt-2-
Сложив эти равенства почленно, мы и получим тре-
требуемое.
3. Сумма чисел Фибоначчи с четными номерами:
«2+«4+ ••• +П = 1 + 1 — I-	' A-3)

На основании п. 1 мы имеем
«1 + «2 + «3 + • • • + «2rt = «2rt + 2 — U
вычтя почленно из этого равенства равенство A.2),
мы получим
«2 И- «4 + • • • + «2» = «2/»+2 — 1 — «2„ = «2П+1 ~~ *•
а это нам и требовалось.
Вычитая, далее, почленно A.3) из A.2), получаем
«1 — И2 +  — «4+.-- + «2п-1 — «2п= — «2П-1+ 1- (I-4)
Прибавим теперь к обеим частям A.4) по и2п+\'
«1— «2 + «3— + ••• — «2/. Ч- «2«+1 = «2/. + 1- A-5)
Объединяя A.4) и A.5), получаем выражение для
знакопеременной суммы чисел Фибоначчи:
tti — «а + и3 — и4 + ... + (—1)я+1и„ =
= (-1)"+Ч_1+-1. A-6)
4. Формулы A.1) и A.2) были выведены при по-
помощи почленного сложения целой серии очевидных
равенств. Еще одним примером применения этого
приема может служить вывод формулы для суммы
квадратов первых п чисел Фибоначчи:
Ы2 + Ы2+ ... +И2=НяИ„+1.	A.7)
Заметим для этого, что
Сложив равенства
и\ = и{и2,
и\ = и2и3 — ихи2.
почленно, мы получаем формулу A.7).
5. Многие соотношения между числами Фибоначчи
удобно доказывать при помощи метода полной инч
дукции%
12

Сущность метода полной индукции (называемого часто так-
также методом математической индукции) состоит в следующем:
для доказательства, что некоторое утверждение справедливо для
всякого натурального числа, достаточно установить, что:
а)	оно имеет место для числа 1;
б)	из справедливости доказываемого утверждения для ка-
какого-либо произвольно выбранного натурального числа п следует
его справедливость для числа п + 1.
Всякое индуктивное доказательство утверждения, справедли-
справедливого для любого натурального числа, состоит поэтому из двух
частей.
В первой части (обычно сравнительно простой) устанавли-
устанавливается справедливость доказываемого утверждения для единицы.
Справедливость доказываемого утверждения для единицы назы-
называют иногда основанием индукции. Во второй части доказатель-
доказательства (как правило, более сложной) делается предположение о
справедливости доказываемого утверждения для некоторого про-
произвольного (но фиксированного) числа п, и из этого предположе-
предположения, которое часто называют индуктивным предположением, вы-
выводится, что и для числа п + I доказываемое утверждение имеет
место. Вторая часть доказательсчша называется индуктивным пе-
переходом.
Подробное изложение метода полной индукции и многочис-
многочисленные примеры применения различных вариантов этого метода
можно иайти в брошюре И. С. Сомииского «Метод математиче-
математической индукции» (серия «Популярные лекции по математике»,
вып. 3, М., «Наука», 1974). Так, в частности, иеодиократио при-
применяемый нами далее вариант метода полной индукции с основа-
основанием индукции, состоящим в доказательстве утверждения при
п = 1 и п = 2, и индуктивным переходом «от я и я + 1 к/г + 2»
приводится в брошюре И. С. Сомииского на стр. 13 и иллюстри-
иллюстрируется на стр. 21—22 примером 7 и задачей 12.
Иногда применяется индуктивное рассуждение, которое мож-
можно назвать переходом «от всех чисел, меньших п, к п». При этом
необходимость в специальном доказательстве основания индук-
индукции отпадает, так как, говоря формально, доказательство для
случая п = 1 и есть переход от «всех» целых положительных чи-
чисел, меньших единицы (которых просто нет), к единице.
Именно таким является доказательство возможности разло-
разложения любого натурального числа иа простые множители.
Предположим, что каждое из чисел, меньших некоторого п,
разложимо в произведение простых множителей. Если число п
оказывается простым, то оно само и является своим разложением.
Если же число п составное, то его, по определению, можно пред-
етавить в виде произведения хотя бы двух сомножителей: п —
— П[П2, где П\Ф \ и щ ф 1. Но тогда щ < п и щ < п, а по
индуктивному предположению как пи так и п2 разлагаются на
простые множители. Тем самым и п разложимо на простые мно-
множители.
Более сложные варианты индуктивного рассуждения лежат в
основе доказательства теоремы п. 36 § 2 и в построении из п. 16 § 4.
6. Простейшей реализацией идеи индукции в
применении к числам Фибоначчи является само
13

определение чисел Фибоначчи. Оно* как разъяснялось
во Введении, состоит в указании двух первых чисел
Фибоначчи: и\ = I и ы2 = 1 и в индуктивном перс-
ходе от ип и «,!+1 к ип+2, даваемым рекуррентным со-
соотношением
В частности, отсюда автоматически следует, что
если некоторая последовательность чисел начинается
с двух единиц, а каждое из следующих получается
сложением двух предыдущих, то эта последователь-
последовательность является последовательностью чисел Фибо-
Фибоначчи.
В качестве примера рассмотрим так называемую
«задачу о прыгуне». Она состоит в следующем.
Прыгун может прыгать в одном направлений
вдоль разделенной на клетки полосы, перемещаясь
при каждом прыжке либо в соседнюю клетку, либо
через клетку. Сколькими способами может он сдви-
сдвинуться на п — 1 клетку и, в частности, переместиться
из первой клетки в п-ю? (Способы прыгания счи-
считаются одинаковыми, если в ходе каждого из них
прыгун побывает в одних и тех же клетках.)
Обозначим искомое число через х„. Очевидно,
х\ — 1 (ибо переход из первой клетки в первую же
осуществляется только одним способом — отсутствием
прыжков) и хг = I (переход из первой клетки во вто-
вторую также единствен: он состоит в одном непосред-
непосредственном прыжке на соседнюю клетку). Пусть целью
прыгуна является достижение п + 2-й клетки. Общее
число способов осуществления этой цели в наших
обозначениях равно хп+2- Но с самого начала эти
способы разбиваются на два класса: начинающиеся
с прыжка во вторую клетку и начинающиеся с прыж-
прыжка в третью клетку. Из второй клетки прыгун может
переместиться в п + 2-ю хп+\ способами, а из третьей
хп способами. Таким образом, последовательность чи-
чисел X], х-1	хп, ... удовлетворяет рекуррентному
соотношению
Хп -j- Xn+\ = Хп + 2
и поэтому совпадает с последовательностью чисел
Фибоначчи: хп — ип.
14

7. Докажем по индукции следующую важную фор-
формулу:
Доказательство этой формулы будем вести индук-
индукцией по т. При т = 1 эта формула принимает вид
«ли = Un-iUi + Мп«2, что очевидно. При т = 2 фор-
формула A.8) также верна, потому что
"«+2 = «»_ 1«2 + "««3 = «»-1 + 2«„ =
= "»-1 + «» + «„ = «„ + 1 + «„•
Основание индукции, таким образом, доказано.
Индуктивный переход докажем в следующей форме:
предполагая, что формула A.8) справедлива при
т = k и при т = k-\-\, докажем, что она имеет место
и при т = k + 2.
Итак, пусть
"я+2 = «п+1 + «п = «п-1 + «п + Un =
Сложив последние два равенства почленно, мы
получим
un+k+2 = un-luk+2 ~\- unuk+3>
а это и требовалось.
Формулу A.8) легко интерпретировать (и даже
доказать) в терминах задачи о прыгуне.
Именно, общее число способов перемещения пры-
прыгуна из первой клетки в п-{-т-ю равно ип+т. Среди
этих способов будут как те, при которых прыгун пере-
перепрыгнет через п-ю клетку, так и те, при которых он
побывает в ней.
При способах первого класса прыгун обязан до-
достичь п—1-й клетки (он может сделать это ип-\
способами), затем совершить прыжок на п-\-\-ю
клетку и, наконец, сместиться на оставшиеся
(п-\-т) — \п-\-\) = т—1 клеток (это осуществимо
ит способами). Следовательно, первый класс насчи-
насчитывает Un—itim способов. Аналогично, при способах
второго класса прыгун достигает п-п клетки (это воз-
возможно ип способами), после чего переходит в n -f- т-ю
клетку (одним из um+i способов). Поэтому во втором
15

классе имеется unum+i способов, и формула A.8) до-	\
казана.
8. Полагая в формуле A.8) т = п, мы получаем	t
ИЛИ
Из написанного равенства видно, что ищ делится
на ип. В следующем параграфе мы докажем значи-
значительно более общее утверждение.
Так как
формулу A.9) можно переписать так:
«2» = ("/»+! — "«-О (««+i + "п
или
т. е. разность квадратов двух чисел Фибоначчи, номе-
номера которых отличаются на два, есть снова число Фи-
Фибоначчи.
Аналогично (полагая т = 2п) можно показать,
что
»== "n + t +"«-"»-!•
9. В дальнейшем нам пригодится следующая фор-
формула:
ul=*Un-lUn + l+{-\)n + l'	A.10)
Докажем ее индукцией по п. Для п — 2 A.10) прини-
принимает вид
что очевидно.
Предположим теперь формулу A.10) доказанной
для некоторого п. Прибавим к эбеим частям ее по
u,,Un+i. Мы получим
ul + «/.«*+1 = «п-1"п+1 + ИпИп+1 + (— l)"+1t
или
«« К + Un+l) — ««+1 (««-1 + Un) + (-1)"+I,
16

или
UnUn+2=Un+\ + (— I
ИЛИ
Этим индуктивный переход обоснован, и формула
A.10) доказана для любого п.
10. Аналогично только что доказанным свойствам
чисел Фибоначчи можно установить еще и такие свой-
свойства этих чисел:
пщ + (п — 1) и2 + (п — 2) ы3 + • • • + 2ы„_1 + ип =
= "« + 4 — (« + 3),
«, + 2м2 + 3н3+ ... +пип = пип+2 — ип+3 + 2.
Доказательство предоставляется провести читателю.
11. Не менее замечательными, чем числа Фибо-
Фибоначчи, являются другие числа, называемые биноми-
биномиальными коэффициентами.
Биномиальными коэффициентами называются ко-
коэффициенты при степенях х в разложениях степеней
A+х)":
(\+х)п = Сп„-\-С]пХ + С1х2+ ... +Сппхп. A.11)
Очевидно, числа Ckn однозначно определены при всех
целых неотрицательных п и всех целых неотрицатель-
неотрицательных k, не превосходящих п.
Использование биномиальных коэффициентов ока-
оказывается весьма удобным во многих математических
рассуждениях. Пригодятся они нам и при изучении
свойств чисел Фибоначчи. Кроме того, биномиальные
коэффициенты связаны с числами Фибоначчи и непо-
непосредственно, и мы выявим некоторые закономерности,
связывающие эти два класса чисел.
Предварительно установим некоторые свойства би-
биномиальных коэффициентов.
Положив в A.11) п=\, мы сразу видим, что
C?=CJ = 1;
кроме того, имеет место следующая лемма.
17

Лемма. Ckn + Ckn+l = CknX\'
Доказательство. Мы имеем
или, пользуясь определением биномиальных коэффи-
коэффициентов,
Но слева и справа в этом равенстве стоит один и тот
же полином. Поэтому и коэффициенты при одинако-
одинаковых степенях х слева и справа должны быть равны,
В частности, должно быть
CHI nk . /-.ft + 1
n+1 = ьге -f- Cre ,
а это и требовалось.
Из доказанной леммы следует, что биномиальные
коэффициенты можно вычислять при помощи некото-
некоторого рекуррентного процесса, подобного процессу по-
получения чисел Фибоначчи, только значительно более
сложной природы. Это же обстоятельство дает нам
возможность доказывать по индукции разного рода
утверждения о биномиальных коэффициентах.
12. Расположим биномиальные коэффициенты в
виде следующей таблицы, называемой треугольником
Паскаля:
С%
с\с\
Ci С'2 С'2
18

т. е.
1
11
12	1
13	3 1
14	6 4 1
1 5 10 10 5 1
1 б 15 20 15 6 1
Подробное изложение основных свойств треуголь-
треугольника Паскаля и составляющих его биномиальных
коэффициентов содержится в брошюре В. А. Успен-
Успенского «Треугольник Паскаля» (серия «Популярные
лекции по математике», вып. 43, «Наука», 1966).
Строки треугольника Паскаля принято нумеровать
сверху вниз, причем верхняя строка, состоящая из
единственной единицы, считается нулевой.	- ;
Из предыдущего вытекает, что крайние члены в
каждой из строк треугольника Паскаля равны еди-
единице, а каждый из остальных членов таблицы полу-
получается путем сложения двух других, стоящих непо-
непосредственно над ним.
13.	Формула A.11) позволяет нам сразу вывести
два важных соотношения, связывающих биномиаль-
биномиальные коэффициенты, составляющие одну строку тре-
треугольника Паскаля.
Полагая в A.11) х= 1, мы получаем
2п = с1 + с1п + с2п + ... +спп.
Если же принять х = —1, то мы получим
0 = С0„-С'+С^+ ... +(-\)пСпп.
14.	Докажем индукцией по п, что
rk	 я(я — 1) ... (я — fe+ 1)	п ]9.
Эта формула часто принимается за определение би-
биномиальных коэффициентов. Она характеризует би-
биномиальный коэффициент Сп как число сочетаний из
п элементов по k. Мы пошли здесь по иному, более
19

формальному пути, который в данном случае предпо-
предпочтительнее.
Если согласиться считать, что произведение нуле-
нулевого числа сомножителей всегда равно единице, то
при k = 0 мы из A.12) получаем уже известное нам
С„= 1.Имея это в виду, мы можем ограничиться слу-
случаем k 2g 1.
При п — 1 мы имеем
\_
1
Пусть теперь при некотором данном п формула
A.12) справедлива при любом значении k = 0, 1, ...
..., п.
Рассмотрим число Сп+и Так как k ^ 1, мы можем
написать
га+1 — Ьп ~f {->ni
или, воспользовавшись индуктивным предположением
A.12),
_п(п — 1) ...(п— fe + 2) . п(п—\) ...(и—fe + 2)(»—fe+1)
1-2- ... -(й- 1) "г	1 - 2 ¦ ... - (ft — 1) Л
п (п — \)...(п — fe + 2)
1-2- ... -(ft— 1)
_ я (n— 1) ... (я —fe + 2) k + n — k + 1 _
1-2. ... -(k- 1)	Л	~
= (»+ l)w(ra-l)... (»-fe + 2) _cft
Последнее равенство является формулой A.12)
для биномиальных коэффициентов из следующей,
п-\- 1-й строки треугольника Паскаля.
15. Проведем через числа треугольника Паскаля липни, иду-
шие под углом 45 градусов к его строкам, и назовем их восходя-
восходящими диагоналями треугольника Паскаля. Восходящими диаго-
диагоналями будут, например, прямые, проходящие через числа 1, 4, 3
или 1, 5, 6, 1.
Покажем, что сумма чисел, лежащих на некоторой восходя-
восходящей диагонали, есть число Фибоначчи.
В самом деле, первая, самая верхняя восходящая диагональ
треугольника Паскаля состоит только из единицы. Только из еди-
единицы состоит и вторая его диагональ. Для доказательства инте-
20

ресующего нас предложения нам достаточно показать, что сумма
всех чисел, составляющих п-ю и п + 1-ю диагонали треугольника
Паскаля, равна сумме чисел, составляющих его п + 2-ю диаго-
диагональ.
Но на гс-й диагонали расположены числа
а па п + 1-й — числа
^п> ^л —1> ^п-21 • ••
Сумму всех этих чисел запишем так:
с°„ + (с°_, + с' _,) + (с'_2 + с
или, принимая во внимание лемму в п. 11,
Последнее выражение есть сумма чисел, лежащих иа п + 2-й вос-
восходящей диагонали треугольника.
Из только что доказанного на основании формулы A.1) мы
сразу получаем: сумма всех биномиальных коэффициентов, лежа-
лежащих выше гс-й восходящей диагонали треугольника Паскаля
(включая саму эту диагональ), равна ип+г— 1.
Используя формулы A.2), A.3), A.4) и подобные им, чита-
читатель без труда может получить дальнейшие тождества, связы-
связывающие числа Фибоначчи с биномиальными коэффициентами.
16. До сих пор мы определяли число Фибоначчи
рекуррентно, т. е. индуктивно, по их номеру. Оказы-
Оказывается, однако, что любое число Фибоначчи можно
определить и непосредственно, как некоторую функ-
функцию его номера.
Исследуем для этого различные последовательно-
последовательности U[, и2, ..., ип, ..., удовлетворяющие соотношению
«п = ип-2 + Ид-1-	A-13)
Все такие последовательности мы будем называть
решениями уравнения A.13).
Будем обозначать буквами V, V и V" соответствен-
соответственно последовательности
оь v2, и3, ...
v[, v'2, v'a, ...
1)" Г>" 1)"
Сначала докажем две простые леммы,
21

¦ Лемма I. Если V есть решение уравнения A.13),
й с— произвольное число, то последовательность cV
(т. е. последовательность cv\, си2, cv%, ...) есть также
решение уравнения A.13).
Доказательство. Умножив соотношение
¦почленно на с, мы получаем
CVn=CVn_2 + CVn_i,
а это и требовалось.
Лемма 2. Если последовательности V и V" яв-
являются решениями уравнения A.13), то и их сумма
V-\-V" (г. е. последовательность v[-\-v", v'2-\- v",
v'^ + v", ...) также является решением уравнения
A.13).
Доказательство. Из условия леммы мы имеем
Сложив эти два равенства почленно, мы получим
< + < = (Са + <-*) + (С + <-)•
Этим лемма доказана.
Пусть теперь V и V" — два непропорциональных
решения уравнения A.13) (т. е. два таких решения
уравнения A.13), что при любом постоянном с най-
найдется такой номер п, для которого -?¦ ф с). Пока-
жем, что всякую последовательность V, являющуюся
решением уравнения A.13), можно представить в
виде
CtV' + CtV,	A.14)
где С\ н Сч — некоторые постоянные. Поэтому принято
говорить, что A.14) является общим решением урав-
уравнения A.13).
Предварительно докажем, что если решения V и
V" уравнения A.13) непропорциональны, то
¦4*4	(Мб)
22

(т.е. что эта непропорциональность обнаруживается
уже, в первых, двух членах, последовательностей V
и V").	. . . :
Доказательство A.15) ведется от противного.
Пусть для непропорциональных решений V и V"
уравнения A.13)
"
v.
A.16)
Написав производную пропорцию, мы получаем
ff , ft	ff
vx + v2	v2
или, принимая во внимание,	что V и V" являются
решениями уравнения A.13),
Аналогично убеждаемся (индукция!) в том, что
Таким образом, из A.16) следует, что последова-
последовательности V и V" пропорциональны, а это противо-
противоречит предположению. Значит, справедливо A.15)'.
Возьмем теперь некоторую последовательность V,
являющуюся решением уравнения A.13). Эта после-
последовательность, как уже было выяснено в п. 2 Введе-
Введения, вполне определена, если заданы два ее первых
члена, v\ и и2.
Найдем такие С\ и с2, чтобы имело место
Тогда на основании лемм 1 и 2 c{V' -f c2V" даст
нам последовательность V.
23

Ввиду условия A.1,5) система уравнений A.17)
разрешима относительно С\ и с2, каковы бы ни были
числа i>i и v2:
|2	2|
ci == / // 7ГТ > C2 ==
V^V.2 — Vi V2	И|У., — Vl V2
(Условие A.15) означает, что общий знаменатель
этих дробей отличен от нуля.) Подставив вычислен-
вычисленные значения Ci и Сг в A.14), мы и получим требуемое
представление последовательности V.
Значит, для описания всех решений уравнения
A.13) нам достаточно найти какие-нибудь два его
непропорциональных решения.
Будем искать эти решения среди геометрических
прогрессий. В соответствии с леммой 1 достаточно
ограничиться рассмотрением только таких прогрес-
прогрессий, у которых первый член равен единице. Итак,
возьмем прогрессию
1, q, q2, ...
Чтобы она была решением уравнения A.13), необхо-
необходимо, чтобы при всяком п выполнялось
дП-i __
или, сокращая на qn~2,
l+q = q2.	A.18)
Корни этого квадратного уравнения, т. е.
	~— и 	y—, и будут искомыми знаменателями
прогрессий. Мы будем их обозначать соответственно
чере^ а и р. Подчеркнем, что для чисел аир, как для
корней уравнения A.18), должно иметь место
1 + « = а2, 1 + Р = Р2 и ар = — 1.
Мы получили, таким образом, две геометрические
прогрессии, являющиеся решениями уравнения A.13).
Поэтому все последовательности вида
С\ + съ с,а + с2р, c,as + с#, ... A.19)
являются решениями уравнения A.13). Так как най-
найденные нами прогрессии имеют разные знаменатели
и потому непропорциональны, формула A.19) при

различных с\ и с2 дает нам все решения уравнения
A.13).
В частности, при некоторых С\ и с2 формула A.19JI
должна дать нам и ряд Фибоначчи. Для этого, как
указывалось выше, нужно определить С\ и с2 из урав-
уравнений
т. е. из системы
Решив эту систему, мы получаем
_ J+VjT	_ 1 — д/5"
с'	TJT' °2~~ 2VB"
откуда
__ 1 4- V5 / 1 + л/5 Л" ' 1 — л/5 ( 1 — V5 у '
~2У5"Ч2У	2У<Г Ч 2 / '
т. е.
¦	A-20)
Формула A.20) называется формулой Бине (по
имени математика, который ее вывел).
Очевидно, подобные формулы можно указать и
для других решений A.13). Пусть читатель сделает
это для последовательностей, приведенных в п. 2 Вве-
Введения.
17. Мы видели, что а2 = а + 1- Ясно поэтому, что
любую целую положительную степень числа а можно
представить в виде аа + Ь с целыми коэффициентами
а и Ь. Так,
а3 = аа2 = а(а+ 1) = а2 + а = а+ 1 +а = 2а+ 1>
а4 = аа3 = а Bа + 1) = 2а2 + а = 2а + 2 + а = За + 2
и т. д.
25

Покажем (по индукции), что ........
а" = ы„<х+ «„_,.
Действительно, для «=2, 3 это справедливо. Пред-
Предположим, что
ак = ика + ик_и
Сложив эти равенства, мы получим
а* + ak+l = (uk + uk+i) a + (ufc_, + uk),
или
и индуктивный переход обоснован.
Аналогично из р2 = р+1 следует
18. При помощи формулы Бине удобно суммировать многие
ряды, связанные с числами Фибоначчи.
Найдем, например, чему равна сумма
«з + «о + «э + • • • + uin.
Мы имеем
	!= (a3 + ae + ... +a3«_p1_pS_ ... _
или, суммируя встретившиеся нам геометрические прогрессии,
Но
а3— 1=а + а2— 1 = а + а + 1 — 1 = 2а,
и аналогично Р3 — 1 = 2р. Поэтому
Ul"~ УЁГ Ч 2а	2р
или, произведя сокращения,
	1 / аЗ"+2 _ а2 _ рЗ«+2 + р2 ч
 ' ' ' " ~ V5" Ч	2	У
2 Ч	V^	V5" / 2 3"+2
26

19. В качестве следующего примера применения фбрМулы
Бине вычислим сумму кубов первых п чисел Фибоначчи.
Заметим предварительно, что
За*р2* -
3a^J
(«, - ("»)* 3"ft) = J
Поэтому
1	= т("з* -<-Dft 3«4)-д" («3ft + <-
- - ((«з + «e + • • • + «s») + 3(«,
или, пользуясь формулой A.6) и результатами предыдущего
пункта,
~	10
20. Уместно поставить вопрос о том, как быстро
растут числа Фибоначчи при увеличении их номеров.
Формула Бине дает нам достаточно исчерпывающий
ответ и на этот вопрос.
Нетрудно доказать следующую теорему.
Теорема. Число Фибоначчи ип есть ближайшее
а11
целое число к —т=, т. е. к п-му члену ап геометриче-
V5
ской прогрессии, первый член которой есть
менатель равен а.
Доказательство. Очевидно, нам достаточно
установить, что абсолютная величина разности между
ип и ап всегда меньше -j • Но
«и — an =
V5
1РГ
V5
Так как р = —0,618 .... то |р|<1, а значит,
|Р|"< 1 при любом п, и тем более (так как
д/5 > 2) должно быть .—- < — . Теорема доказан;!.
V5 2
¦Л

Читатель, знакомый с теорией пределов, легко
сможет, несколько видоизменив доказательство этой
теоремы, показать, что
lim | ип — ап | = 0.
Пользуясь доказанной теоремой, можно вычислять
числа Фибоначчи при помощи таблиц логарифмов.
Вычислим, например, иц (иц, как легко сообра-
сообразить, должно являться ответом задачи Фибоначчи о
кроликах):
= 2,2361, IgV5 =0,34949;
а==1±_л/5_=1>6180>	lg a = 0,20898;
lg-^Д- = 14 • 0,20898 - 0,34949 = 2,5762,
-2^ = 376,9.
Ближайшим целым числом к 376,9 является 377;
это и есть u\i.
При вычислении чисел Фибоначчи с большими
номерами мы уже не сможем по таблицам логариф-
логарифмов определить все цифры числа, а сможем указать
только несколько первых цифр его, так что вычисле-
вычисление оказывается приближенным.
В виде упражнения читатель может доказать, что
в десятичной системе счисления и„ при п ^ 17 имеет
не более -j и не менее -j цифр. А из скольких цифр
состоит аюоо?
21. Результат предыдущего пункта можно уточнить. Следую-
Следующая теорема пригодится нам в дальнейшем.
Теорема.
п		пл—
V5" = "= V5
Доказательство. Мы ограничимся доказательством ле-
левой стороны неравенства: правая доказывается аналогично.
Поскольку согласно формуле Бине
«„--j=r(a»-p»),
V5

a dfl =—1, для наших целей будет достаточно показать, что
It		j
или, возводя в степень п,
а!вЧ^(аг»-1Г.	A.21)
Будем доказывать это неравенство по индукции. При п = 1
оно превращается в
a^ a2— 1,
что действительно имеет место (именно, со знаком равенства).
При п = 2 A.21) означает
a7^(a4-lJ.	A.22)
Это неравенство можно проверить и прямым вычислением. Од-
Однако его можно и доказать, воспользовавшись соотношением, вы-
выведенным в п. 17. В данном случае мы имеем
а* = За + 2,
(а* - IJ = (За + IJ = 9а2 + 6а + 1 = 15а + 10,
и A.22) переписывается как
a7=13a + 8^ 15а + 10,
что очевидно. Наконец, прн «==3 A.21) переписывается как
a17g (a6 — IK,
что проверяется аналогично предыдущему.
Предположим теперь, что п>2 и A.21) имеет место, и до-
докажем, что
Для этого достаточно показать, что при увеличении п на единицу
правая часть A.21) растет быстрее левой части. Но левая часть,
очевидно, возрастает в а4я+2 раз. Оценим увеличение правой
части.
Мы имеем
п+1
(„2 (»+!)_ J)
(а2" - 1)"
Последняя дробь больше, чем а2, и притом на
а2'"+|>-1	g _ а2"+2 _ 1 _ а2и+2 + а2 _ а2 _ I
aM-l	a ~	а2ге-1	~а2'г-1
„2Я-1 '
29

Следовательно, 'пользуясь' формулой бинома (см., например,
п. 11 § 1),
B(п+1)
где точки стоят вместо положительных слагаемых.
Ввиду того, что п > 2, написанное выражение больше, чем
а2" + I. Значит,
/„2(п+1) i\n+[
(а. 2п ",'! > («2 <«+1> - о wn + о -
1
и теорема доказана.
22. Рассмотрим еще один класс последовательно^
стей, основанных на числах Фибоначчи. Пусть х —
произвольное число. Вычислим сумму
sn (х) = «ix + щх2 + ... +ипхп.
Для этого воспользуемся прежде всего формулой
Б и не:
а — р
I а F
1 vr
1 2 1
-Х2 +
1 а"-р" А-»
... +<xV) —
	У (рх + р2л:2 + ... + РУ). A.23)
V5
Здесь в скобках написаны суммы двух геометри-
геометрических прогрессий со знаменателями ах и р*. Извест-
Известная формула, выражающая сумму геометрической
прогрессии, справедлива в том случае, когда знаме-
знаменатель прогрессии отличен от единицы. Если же он
равен единице, то все члены прогрессии равны друг
другу, и их сумма вычисляется совсем просто.
В соответствии со сказанным рассмотрим сначала
случай, когда ах ф 1 и fix Ф 1, т. е. когда х Ф — =
*= — $ихф-гг = — а. В этих случаях, суммируя в
30

, . (si.23) геометрические прогрессии, мы получаем :
1 g"+lx"+1 — ах	1 Р"+'х"+1 — Р*

Sn{X)~ /W ах-\	л/5"	Рх-1
или, выполняя естественные преобразования,
1 (ад+|х"+| - ах) (рх- 1) - (р*+У+1 -
у5	(ах — 1) (рх —
и далее —
, ^	 I I о, рх — а х -f- ctx
- (а + р) л + 1
Вспоминая, что сф=— 1, а + Р=1. a o-p=
мы имеем
, 1 х л/5~ - (а" - р") х"+2 - (а"+1 - р"+') хп+]
д/5	1 — х — х2
и окончательно
В частности, полагая в этой формуле х—\, мы
получим
что соответствует сказанному в п. 1.
При л; = — 1 имеем
в	==(_1)Цп_1 + 1
(ср. формулу A.6)).
Рассмотрим теперь оставшиеся «особые» случаи.
Пусть х = — =—р. Тогда в A.23) каждый член
первой прогрессии равен единице, и сумма этой про-
прогрессии равна п. Во второй же прогрессии знамена-
знаменатель оказывается равным — Ji2.

Таким образом,
= 1 /	р2-(_1)"р2П+2ч
л/б" V	1 + Г ) ~
Замечая, что
1_|_р2_2-)-й = 2+ ' ~ V5 _ 5 — V 5
2
^3-V5"_C- л/5") E + V5")
^	_
1 + Р2 2 + р 5 - л/5 E - л/5") E + л/5") ~~
10 — 2
~ 20
мы получаем окончательно
Наконец, пусть * = -ц-. В этом случае в A.23)
единице равен знаменатель второй прогрессии, а зна-
знаменатель первой прогрессии равен — а2. Мы имеем
Аналогично предыдущему получаем
и в итоге
l±^*4-i±^-^. (..26,
23. Посмотрим, как ведет себя сумма 5п(лг) при
фиксированном х и неограниченно возрастающем ««
32	1

Переходя в равенстве A.23) к пределу по п, мы
получаем
lim sn (x) = lim -J=r ((ax + а2*2 + ... + апхп) -
-(Р* + РУ+ ... + pV)) =
—-W Пт (ах+ а2*2 + ... + aV) -
5
Здесь под знаками двух последних пределов стоят
суммы геометрических прогрессий. Поэтому сами пре-
пределы являются суммами соответствующих бесконеч-
бесконечных геометрических прогрессий. Но, как известно, для
того, чтобы можно было говорить о сумме бесконеч-
бесконечной геометрической прогрессии, необходимо и доста-
достаточно, чтобы ее знаменатель по абсолютной величине
был меньше единицы. В имеющихся у нас прогрес-
прогрессиях знаменатели равны ах и $х. Здесь |<х|>|р|.
Поэтому из |ax|<l следует |px|<l. Таким обра-
образом, выполнение неравенства |ax|<l будет обес-
обеспечивать существование всех интересующих нас в
данный момент пределов.
Итак, предел
Ax)	A.27)
существует, если 1*1 <—. Обозначим этот предел
через s(x). Для его вычисления мы можем воспользо-
воспользоваться формулой A.24).
Заметим для этого, что на основании сказанного
в п. 20
Поэтому
lim unxn+2^ lim
,*+2
= Jj=- lim (eu)n+ lim xn
2 H, H, Воробьев	33

Ввиду |ах|< 1 должно быть и \х\<. 1, так что оба
написанных предела равны нулю. По тем же причи^
нам и
Jim
Следовательно, переходя в формуле A.24)' к пре«
делу по п при неограниченном возрастании п, мы
получаем
s (х) = lim sn (x) = lim x ~ "",
]
=1	^(лг— lim и„хп+2 -
Найденный результат можно переписать в развер-
развернутом виде как
щх+и2х2+ ... +ипхп+ ..¦=!_ Хх_ х> ¦ A.28)
Придавая переменной л: те или иные значения, мы
будем получать различные конкретные формулы. На-
Например, полагая х=-^> обнаружим, что
f f+ ...+-§-+ ... =2.
24. Формулу A.28) можно получить также при по-
помощи несколько иных рассуждений.
Напишем
щх + и2хг+ ... +ипхп+ ... =s(x) A.2Э)
Гпомня при этом, что выражение s(x) имеет смысл
лишь при | jc | < — J и умножим это равенство по-
почленно на х и на х2:
щх2 + щха+ ... Jrunxn+1+ ... =xs(x), A.30)
щх3 + щх4 + ... +ипх"+2+ ... =x2s(x). A.31)
Вычитая из равенства A.29) оба равенства A.30) и
A.31), мы после приведения подобных членов по-
получим
щх + (м2 — Mi) х2 + (и3 — Щ — Щ) х3 +
+ (ui — u3 — u2)x'i+...+ (ип — un_i — м„_2) х"+... =
34

Все заключенные в скобках выражения в левой части
равенства, кроме первого, очевидно, равны нулю, и
это равенство превращается в
х = (\ — х — x2)s(x),
откуда и следует A.28).
25. Говоря о числе Фибоначчи «„, мы пока все
время предполагали, что его номер п является целым
положительным числом. Однако основное рекуррент-
рекуррентное соотношение, определяющее числа Фибоначчи,
может быть записано и как
ИП-2 = И/1 —И/1-I-	О-32)
При этом оно будет служить для выражения чисел
Фибоначчи с меньшими номерами через числа с боль-
большими.
Полагая последовательно в A.32) я = 2, 1, О,
— I	мы можем вычислить
И0 = 0,	И_1 = 1,	Ы_2= — 1,	«_3=2, ...
и вообще, как легко убедиться (пусть читатель убе-
убедится сам!),
и_„ = (-1)п+Ч.	A.33)
Это простое выражение числа Фибоначчи с произ-
произвольным целым номером позволяет сводить все за-
задачи о таких числах Фибоначчи к задачам об обыч-
обычных числах Фибоначчи с натуральными номерами.
Например, для вычисления суммы п «первых на-
назад» чисел Фибоначчи
М_1 + М_2+ ... +U_n
достаточно переписать ее в соответствии с A.33):
и вспомнить формулу A.6):
ы_, + и_2 + ... + и_„ = (-1)"+| и„_, + 1 = -и_п+1 + 1.
Опирающееся на основное рекуррентное соотно-
соотношение индуктивное рассуждение о числах Фибоначчи
типа переходов «от п и п + 1 к п + 2» можно в связи
с соотношением A.32) проводить по схеме «от п и
2*	35

п— 1 к n — 2». В частности, таким образом без труда
доказывается для любых целых пит важная фор-
формула A.8)
26. Основные уравнения для чисел а и р:
справедливы не только для положительных, но и для
любых целых значений п (для дробных значений п
эти равенства тоже в известном смысле остаются в
силе, но мы на этом не будем останавливаться). От-
Отсюда легко получить, что формула Бине
имеет место для любого целого п.
Заметим в заключение, что и результат п. 17
можно (по индукции «назад») перенести па отрица-
отрицательные значения номера:
а-» = и_„а+ «_„_,.	A.34)
Это равенство переписывается как
т. е.
Pn+1==«n+iP + «n-
Кроме того, A.34) можно представить в виде
т. е.
(— 1)"а-" = н„+1 — ы„а,
или, иначе,
if«±i-«.a = (_i)»a-n —.	A.35)
27. Числа Фибоначчи могут составить основу свое-
своеобразной «фибоначчисвой» системы счисления, т. е.,
представления любого натурального числа а в виде
некоторой последовательности «цифр» ф1ф2 .. .qv. Эта
последовательность может быть получена следующим
(индуктивным!) образом.
36

Отнимем от заданного числа а = а0 наибольшее из
не превосходящих его чисел Фибоначчи ип и, написав
цифру ф! = 1 и разность а\ = а0 — ип, будем считать
это первым шагом нашего построения.
Предположим, что k шагов построения уже вы-
выполнены, в результате чего появилась последователь-
последовательность цифр
Ф1 ... Фь	A.36)
состоящая из нулей и единиц, а также некоторое чис-
число пк. Тогда 6+1-й шаг построения будет состоять
в следующем: сравним число аь с числом Фибоначчи
un-k, и если окажется а*. << un-k, то припишем к по-
последовательности A.36) фб+i = 0 и фиксируем число
uk+i — an, а если будет аи ==5 ип-к, то припишем к
A.36) Ф/-.+1 = 1 И ПОЛОЖИМ пк+l = йк — Un-k. Мы ВЫ-
ВЫПОЛНИМ п—1 шагов этого процесса, в результате
чего, очевидно, придем к п—I-членной последова-
последовательности A.36) и числу an-i = 0.
Фактически описанный процесс является последо-
последовательным выделением из числа а слагаемых, рав-
равных наибольшим возможным числам Фибоначчи, т. е.
представлением а в виде суммы различных чисел
Фибоначчи.
Окончательную соответствующую числу а после-
последовательность A.36) будем называть его фибонач-
чиевой записью и обозначать через Ф(а). Составляю-
Составляющие Ф(а) нули и единицы назовем фибоначчиевыми
цифрами числа а. Ясно, что если Ф (а) = ф1 ... фл-1,то
а= илф1 + ил-1ф2+ ••• +«2Ф/1-1- A-37)
Поясним сказанное на примере. Пусть а = 19.
Тогда
Ив_13(л = 7),	Ф1 = 1,	а, = 19—13 = 6;
«6 = 8>а1|	ф2 = 0,	a2 = ai = 6;
м5 = 5^а2,	фз=1>	а3 = 6 — 5 = 1;
щ = 3 > а3,	ф4 = 0,	а4 = а3 = 1:
и3 = 2 > а4,	ф5 = 0,	а5 = at = 1;
и2=1^а5,	Ф6=1,	«6= 1 — 1=0.
Таким образом, ФA9)= 101001, и 19 = и7 + «s"+"«2.
37

- Ясно, что каждое число а имеет единственную фи-
боначчиеву запись Ф(а). Однако не всякая начинаю-
начинающаяся с единицы последовательность нулей и единиц
обязана быть фибоначчиевой записью Ф(а) для не-
некоторого числа а. Например, в Ф(а) не могут стоять
две единицы подряд.
Действительно, пусть в Ф(а) две единицы встре-
встречаются подряд после некоторого нуля: (рк = 0, <fk+i =
= фй+2 == I. Это значит, что
а»-1 < и„_*+1,	A.38)
ak_i = ak, ак — ип..к = ак+и ай+1^и„_Л_1.
По почленное сложение всех составляющих вторую
строку соотношений дает нам
a*_i Ш ип_к + ип_к_х = «„_*+(,
что противоречит A.38).
Значит, две единицы подряд могли бы встретиться
в Ф(а) разве лишь в том случае, когда впереди них
вовсе не было бы нулей, т. е. было бы <pi = q>2 = 1.
Mo тогда по определению процесса а\ = а0—««=§?
2г и„_1, так что
и ип не является наибольшим числом Фибоначчи, не
превосходящим а.
Вместе с тем ограничение, заключающееся в от-
отсутствии двух стоящих рядом единиц, оказывается
уже достаточным: всякая последовательность из га— 1
пулей и единиц, начинающаяся с единицы и не содер-
содержащая двух единиц подряд, есть фибоначчиева запись
Ф(а) некоторого числа а, для которого
»»ЙЖ«,1+1.	A-39)
В этом можно убедиться, воспользовавшись, на-
например, результатом задачи о прыгуне из п. 6. Пусть
имеется п — 1 клетка, по которым прыгун прыгает
доступными для него способами (т. е. на соседнюю
клетку или через клетку). После выполнения прыж-
коз все клетки, в которых прыгун побывал, поме-
помечаются нулями, а остальные клетки — единицами. Так
как всего возможно ип-\ способов выполнения прыж-
прыжков, различных способов пометок будет тоже ип-и
38

Если к каждой из них приписать впереди единицу,
то мы получим запись, которая может быть фибонач-
чиевым значением для числа а, удовлетворяющего
A.38). Но таких чисел ровно ип-\, и каждое из них
должно иметь свою запись; поэтому каждой записи
соответствует хотя бы одно число.
§ 2. ТЕОРЕТИКО-ЧИСЛОВЫЕ СВОЙСТВА
ЧИСЕЛ ФИБОНАЧЧИ
1.	Рассмотрим теперь некоторые свойства чисел
Фибоначчи, касающиеся их делимости.
Теорема. Если п делится на т, то и и„ делится
на ит.
Доказательство. Пусть п делится на т, т. е.
п = mk. Будем вести доказательство индукцией по k.
Для k = 1 п = т, так что в этом случае ип де-
делится на ит очевидным образом. Предположим те-
теперь, что Umk делится на ит, и рассмотрим um{k+\). Но
Um(k+l) = Umk+m И НЭ ОСНОВЭНИИ A.8)
Um (ft + 1) = Umk-\Um + Umk.Utn+1-
Первое слагаемое правой части написанного равен-
равенства, очевидно, делится на ит. Второе же ее слагае-
слагаемое кратно umk, т. е., по индуктивному предположе-
предположению, тоже делится на ит. Значит, на ит делится и их
сумма, т. е. tinnk+i). Этим теорема доказана.
2.	Возьмем теперь некоторое число т. Если суще-
существует хотя бы одно число Фибоначчи иПу делящееся
на т, то таких делящихся на т чисел Фибоначчи
можно найти сколь угодно много. Ими будут, кроме
ип, например, числа и2гс. «зп, uin, ...
Интересно поэтому выяснить, можно ли по за-
заданному числу т. найти хотя бы одно делящееся на
него число Фибоначчи. Оказывается, это сделать
можно.
Пусть /г обозначает остаток от деления k на т.
Будем выписывать последовательность пар таких
остатков от деления чисел Фибоначчи на т:
(пи м2), (п2, п3), (п3, п4)	<м„, м„+1>, ... B.1)
Если считать пары <яь 6t> и <а2, Ь2У равными
при а\ = а2 и Ь\ = 62» то число всех различных пар
39

остатков от деления на т равно т2. Поэтому если
в последовательности B.1) взять т2+ первых чле-
членов, то среди них обязательно окажутся равные.
Пусть {пк, пк+\> — первая пара, которая повто-
повторится в последовательности B.1). Покажем, что этой
парой является пара <1, 1>. В самом деле, предполо-
предположим обратное, т. е. что первой повторившейся парой
окажется пара {uk, uk+i}, где k > I. Найдем в B.1)
пару {щ, ui+i) (/>&), равную паре {uk, uk+i}. Так
как щ-\ = ui+i — и; и Uk-i — uk+i — Uk, a щ+i = пк+\
и Гц = ilk, остатки от деления ui~i и Uk-i на т также
должны быть равны, т. е. п;_| = пи-\. Однако из этого
следует, что и {пк-и пк} — <«/-i, й;>, а пара <«ft_i, пи)
встречается в последовательности B.1) раньше, чем
{пи, пк+i}, и поэтому {uk, пк+i} не является первой
повторившейся парой, что противоречит нашему пред-
предположению. Значит, предположение, что k > 1, не-
неверно, а это означает, что k = I.
Итак, <1, 1> есть первая повторившаяся в после-
последовательности B.1) пара. Пусть она повторилась на
?-м месте (в соответствии с установленным ранее мы
/. ... _... можем считать, что 1 < t < m2 + 1), т. е.
Это значит, что и щ и ut+i при делении на т дают
в остатках единицы. Значит, их разность делится на
т нацело. Но
Щ+i ~~ Щ — Щ-и
так что на т делится t— 1-е число Фибоначчи.
Мы доказали, таким образом, следующую теорему.
Теорема. Каково бы ни было целое число т,
среди первых т2—I чисел Фибоначчи найдется хотя
бы одно, делящееся на т.
Заметим, что доказанная теорема не утверждает
ничего о том, какое именно число Фибоначчи раз-
разделится на т. Она говорит только, что первое число
Фибоначчи, делящееся на т, не должно быть осо-
особенно большим. Далее мы еще вернемся к этому
вопросу.
Из того, что <1, 1> есть первая повторившаяся пара
в последовательности B.1), вытекает, что начиная с
40

ut, последовательность остатков повторяется как бы
сначала. Это значит, что последовательность остатков
оказывается периодической. Например, при т = 4
этот период в последовательности остатков будет
следующим:
1, 1, 2, 3, 1, 0.	B.2)
Длина периода в данном случае равна 6. Таким обра-
образом, если число п имеет вид 6&+1, 6k + 2 или
bk + 5, то ип при делении на 4 дает в остатке еди-
единицу, если п имеет вид 6k + 3, то 2, а если 6k + 4,
то 3.
3.	Большой интерес представляет вопрос об ариф-
арифметической природе чисел Фибоначчи, об их делите-
делителях. Докажем, что при п составном и отличном от 4
ип есть составное число.
Действительно, для такого п можно написать
п = П\П2, где 1 < п.\ < п, 1 < п2 < п и либо п\ >• 2,
либо «2 > 2. Пусть для определенности п\ > 2. Тогда
ввиду только что доказанной теоремы ип делится на
иП1> причем 1 < ит < ип, а это и означает, что ип —
составное число.
4.	Прежде чем продолжать изучение чисел Фибо-
Фибоначчи, напомним читателю несколько простейших све-
сведений из теории чисел.
Сначала укажем процесс нахождения наибольшего
общего делителя чисел а и Ь.
Разделим а на b с остатком. Пусть при этом
частное равно q0, а остаток г\. Очевидно,
о = bq0 + Г\ и 0 ^ Г] < Ь.
Заметим, что при а <.Ь будет q0 = 0.
Разделим, далее, b на г\ и обозначим частное че-
рез^<7ь а остаток через r-i. Очевидно, b = r\q\-\- гч и
0^г2<Г1. Так как r\<Lb, должно быть qi^=Q.
Затем, разделив г\ на г2, найдем такие q2 ф 0 и г3, что
П = <?2/ + Н и 0 =? гъ < г2. Будем поступать так до
тех пор, пока этот процесс можно продолжать.
Рано или поздно наш процесс должен оборваться,
так как все целые положительные числа п, г2, н, ...>
различны, и каждое из них меньше Ь. Значит, число
41

их не превосходит Ь, и процесс должен закончиться
не позднее 6-го шага. Оборваться же он может лишь
на том, что некоторое деление окажется произведен-
произведенным нацело, т. е. остаток окажется равным нулю, а
д?лыпе делить на него будет уже нельзя.
Описанный процесс носит название алгорифма
Евклида. В результате его применения к числам а и b
мы получаем такую последовательность равенств:
r\ = r,q2 + Г).
• _L. . . .	B.3)
-2 — rn_{qn_\ -f- rn,
Рассмотрим последний отличный от нуля член в
последовательности а, Ь, г\, г2, ..., гп и именно его
впзьмем в качестве /¦„. Разумеется, в частности,
им может оказаться и число b (для единообразия
можно положить b — го). Очевидно, гп-\ делится на
г„. Возьмем теперь в B.3) предпоследнее равенство.
Е правой его части оба слагаемых делятся на rn, a
потому и /-„_2 делится на г„. Аналогичным образом
, убеждаемся последовательно (индукция!) в том, что
. на гп делятся гп-г, Гп-ь ... и, наконец, b и а. Итак, г„
является общим делителем а и Ь. Покажем, что гч
есть наибольший общий делитель а и Ь. Для этого
нам достаточно показать, что всякий общий делитель
а и b будет делить и гп-
Пусть d—некоторый общий делитель а и Ь. Из
первого равенства B.3) усматриваем, что d должно
делить г\. Но тогда на основании второго равенства
B.3) d делит г2. Аналогично (индукция!) доказы-
доказываем, что d делит г3, ..., гп-\ и, наконец, г„.
Мы доказали, таким образом, что алгорифм Ев-
Евклида, примененный к натуральным числам а и Ь,
действительно приводит к наибольшему общему де-
делителю этих чисел. Этот наибольший делитель чисел
а и b мы будем обозначать через (а,Ь).
Очевидно, а делится на b тогда и только тогда,
когда (a, b) = b.
42

В качестве примера найдем (ы2о, «is) = F765, 610):
6765 = 610-11+55,
610= 55-11+5,
55= 5-11.
Итак,
(«20, «15) = 5 = Ы5.
То, что наибольшим общим делителем двух чисел
Фибоначчи вновь оказалось число Фибоначчи, не
случайно. В дальнейшем будет доказано, что так
бывает всегда.
5.	Процесс, аналогичным алгорифму Евклида, встречается
в геометрии при нахождении общей меры двух соизмеримых от-
отрезков. В самом деле, рассмотрим два отрезка: один длиной а и
другой длиной Ь. Вычтем из первого отрезка второй столько раз,
сколько это возможно (если b > а, то, очевидно, мы этого не
сможем сделать ни разу), и обозначим длину остатка через т\.
Очевидно, г\ < Ь. Вычтем теперь из отрезка длиной Ь отрезок
длиной Г\ столько раз, сколько возможно, и обозначим получив-
получившийся вновь остаток через г?. Поступая таким же образом даль-
дальше, мы получим последовательность остатков, длины которых,
очевидно, убывают. До этого места сходство с алгорифмом Ев-
Евклида, как мы видим, полное.
Далее, однако, обнаруживается важное отличие описываемого
геометрического процесса от алгорифма Евклида для натуральных
чисел: последовательность остатков, получаемых при вычитании
отрезков, может и не оборваться, так как процесс такого вычита-
вычитания окажется возможным вести неопределенно долго. Это будет,
очевидно, в случае несоизмеримости взятых первоначально от-
отрезков.
6.	Установим несколько простых свойств наиболь-
наибольшего общего делителя двух чисел.
(a, be) делится на (а,Ь). Действительно, Ь, а по-
потому и be, делится на (а,Ь); а делится па (а,Ь)
очевидным образом. Значит, по доказанному в п. 4 и
(a,be) делятся на (а,Ь).
7.	(ас, be) = (a, b) с.
Доказательство. Пусть равенства B.3) опи-
описывают процесс нахождения (а,Ь). Умножив почлен-
почленно каждое из этих равенств на с, мы, как легко
проверить, получим систему равенств, соответствую-
соответствующую алгорифму Евклида, примененному к числам ас
и be. Последний ненулевой остаток при этом будет
равен гпс, т. е. (а, Ь)с.
43

8.	Если (а, с)'= 1, то (a, be) — (a, b). В самом
деле, (a, be) на основании п. 6 является делителем
,(ab, be). Но
(ab, Ьс) = (а, c)b=\-b = b
ввиду п. 7. Таким образом, b делится на (a, be).
С другой стороны, (a, be) есть делитель а. Значит,
(a, be) ввиду доказанного в п. 4 делит и (а, Ь). А так
как по п. 6 и (а,Ь) делит (a,be), мы получаем
(a,b) = (a,bc).
Пусть be делится на а. Это значит, что (a, be) = a.
Если при этом (а, с) = 1, то по предыдущему (а, Ь) =;
= а, т. е. й делится на а.
Если /7 — простое число, то любое а либо делится
на р, либо взаимно просто с ним. Следовательно, по
предыдущему, если произведение двух чисел делится
на простое р, то хотя бы один из сомножителей дол-
должен делиться на это р. Очевидным образом по индук-
индукции это утверждение распространяется на случай
произведения произвольного числа множителей.
9.	В качестве примера, который будет полезен в дальнейшем,
рассмотрим один из вопросов о делимости биномиальных коэф-
коэффициентов.
Теорема. Если р — простое, акфЪикфр, то С* де-
делится на р.
Доказательство. Согласно сказанному в п. 14 § 1
k _ p(p-\)...(p-k+\)
ЬР~	1-2- ... -к
Так как в действительности эта дробь равна целому числу, ее чис-
числитель должен делиться на знаменатель. Но каждый из сомно-
сомножителей знаменателя меньше, чем р, и потому на р не делится.
Следовательно, так как р — простое, по предыдущему на р не де-
делится и их произведение, т. е. весь знаменатель. Значит, знамена-
знаменатель взаимно прост с р.
Рассмотрим числитель дроби как произведение двух чисел р
и (р—1) ... (р — fe+1). Это произведение делится на знаме-
знаменатель. Так как р взаимно просто со знаменателем, на него
делится второй сомножитель: (р—1) ... (р — к + 1). Пусть
(р— 1) ... (р— к + 1) = /-1-2- ... -к. Тогда Ckp — tp, а это и
требовалось.
10.	Если с делится на Ь, то (а, Ь) = (а + с, Ь).
Доказательство. Пусть применение алгориф-
алгорифма Евклида к числам а и b приводит к системе ра-
равенств B.3). Применим этот алгорифм к числам
44

а + с и Ь. Так как с делится на Ь по условию, то мы
можем положить с = С\Ъ\ первый шаг алгорифма дает
нам равенство
Все дальнейшие шаги этого алгорифма дадут нам
последовательно второе, третье и т. д. равенства си-
системы B.3). Последним отличным от нуля остатком
по-прежнему является гп, а это и значит, что (а, Ь) =
= (а + с,Ь).
Полезным упражнением для читателя будет дока-
доказательство этой теоремы только на основании резуль-
результатов пп. 6—8, т. е. без повторного обращения к по-
понятию алгорифма Евклида и системе B.3).
П. Теорема. Соседние числа Фибоначчи взаим-
взаимно просты.
Доказательство. Пусть вопреки утверждению
теоремы ип и un+i имеют некоторый общий делитель
d~> 1. Тогда и их разность ип+\ — ип будет делиться
на d. А так как и„+1 — un = un-i, на d должно де-
делиться и iin-i. Аналогично показываем (индукция!),
что на d будут делиться и ип-2, и ип-з, и т. д. и, нако-
наконец, и\. Но «1 = 1, и поэтому на d > 1 делиться не
может. Полученное противоречие доказывает теорему.
12. Теорема. Имеет место равенство
Доказательство. Пусть для определенности
т > п. Применим к числам тип алгорифм Евклида:
m = nqu-\-ru	где 0 si Г\ < п,
п = rxq\ + г2,	где 0 ^ г2 < гь
где 0^
Как нам уже известно, ri есть наибольший общий
делитель т и п.
Итак, т — nqo + г\\ значит,
("т> "„) = (««„+,,. "„),
45

или
или, на основании пп. 1 и 10,
или ввиду пп. 11 и 8
("m.u») = K. О-
Аналогично доказываем, что
Сопоставляя все эти равенства, получаем
а так как r*_i делится на о, так что и мГ/-1 делится
на иГ{, должно быть (иГ{, иГ{_^ = игг Замечая, нако-
наконец, что rt = (т, п), мы получаем требуемое.
В частности, из только что доказанного следует
теорема, обратная теореме п. 1: если ип делится на
ит, то п делится на т. В самом деле, если ип делится
на ит, то, как отмечалось в п. 4,
{ип,ит) = ит.	B.4)
Но, по доказанному,
Сопоставляя формулы B.4) и B.5), мы получаем
и — и
ит и(п, т)>
т. е. т= (п, т), а это и означает, что п делится на т.
13. Объединяя теорему п. 1 и следствие теоремы
п. 12, мы имеем: ип делится на ит тогда и только тог-
тогда, когда п делится на т.
Ввиду этого о делимости чисел Фибоначчи можно
судить, рассматривая делимость их номеров.

Найдем, например, несколько «признаков дели-
мосги» чисел Фибоначчи. Под признаком делимости
мы понимаем здесь признак, по которому можно опре-
определить, делится или нет то или иное число Фибоначчи
на некоторое данное число.
Число Фибоначчи четно тогда и только тогда,
когда его номер делится на 3.
Число Фибоначчи делится на 3 тогда и только
тогда, когда его номер делится на 4.
Число Фибоначчи делится на 4 тогда и только
тогда, когда его номер делится на 6.
Число Фибоначчи делится на 5 тогда и только
тогда, когда его номер делится на 5.
Число Фибоначчи делится на 7 тогда и только
тогда, когда его номер делится на 8.
Число Фибоначчи делится на 16 тогда и только
тогда, когда его номер делится на 12.
Доказательства всех этих признаков делимости и
всех других, подобных им, легко могут быть прове-
проведены читателем при помощи предложения, приведен-
приведенного в начале этого пункта, и рассмотрения соответ-
соответственно третьего, четвертого, пятого, шестого, вось-
восьмого, двенадцатого и т. д. чисел Фибоначчи.
Пусть заодно читатель докажет, что не сущест-
существует чисел Фибоначчи, дающих при делении на 8 в
остатке 4, а также, что нет нечетных чисел Фибонач-
Фибоначчи, делящихся на 17.
14. На протяжении этого параграфа нам часто придется вы-
высказывать суждения типа «числа а и b при делении на т дают
один и тот же остаток», или, что, в сущности, то же самое, «раз-
«разность а — Ь делится на /и».
Нам нужно иметь возможность легко и уверенно опериро-
оперировать с этими суждениями и переходить от одних суждений та-
такого типа к другим. Поэтому мы будем, как это принято в тео-
теории чисел, записывать такие суждения формально, сделав их
тем самым предметом некоторого «исчисления».
Определение. Числа а и b называются сравнимыми по
модулю т, если при делении на т числа а и b дают один и тот
же остаток, или если а — b делится на т. Сравнимость а и b по
модулю т записывается как
o = S (mod /и).
Очевидно, если о делится на /и, то
а з= 0 (mod /и),
и наоборот.
47

15. Сравнения по одному и тому же модулю можно подобно
равенствам почленно складывать.
Лемма. Если
п\ = &i (mod /и),
а% Э5 Ь% (mod /и),
о-п = Ьп (mod m),
то
о.\ + fl2 -f- ... -f- on = 61 -f- 6j -f- ... ~\~ bn (mod w).
Доказательство. Из условия следует, что на т делит-
делится каждая из разностей
а потому и их сумма:
(ai — 61) + (а2 — 62) + ... + (ап — Ьп).
т. е.
а это и означает требуемое сравнение.
16. В п. 9 мы установили, что при простом р и 0 < k < р
C* = 0(modp).	B.6)
Это можно записать также как
при 0 gi k < р — 1.
Значит, при 0 < k •< р— 1 справедливы оба сравнения B.6)
и B.7). Сложив их, мы получим
или
Иными словами, при простом р в р+ 1-й строке треугольника
Паскаля все члены, кроме четырех (по два крайних справа и
слева), делятся на р.
Нетрудно проверить также, что
17. Сравнение B.6) можно переписать как
или
Cjl!--C*_,(modp).
48

Это имеет место при любом k — \, 2	р — 1. Значит,
С°р_!^ - С^.^С2^!^ - Cj_,- ... -CJI' (mod р).
Так как С® \ = 1, последнее сравнение означает, что члены
р— 1-й строки треугольника Паскаля с нечетными номерами срав-
сравнимы по модулю р с 1, а члены с четными номерами с —1.
18. Сравнения по одному и тому же модулю можно не только
почленно складывать, но и почленно перемножать.
Лемма. Если
a(s=6| (mod tn),
аг^Ьг (mod tn),	B.8)
an = bn (mod tn),
то
... are = 6i62 ... bn (mod «).	B.9)
Доказательство будем вести индукцией по п.
При п = 1 лемма тривиальна.
Предположим, что для некоторого п лемма верна (т. е. что
из B.8) следует B.9)) и присоединим к ее условиям сравнение
are+i?=&n+i (mod m).	B.10)
Сравнения B.9) и B.10) соответственно означают, что раз-,
ности а^г • • • ап — &i&2 ¦ • • Ьп и ап+\ — bn+i делятся на т. Следовав
тельно,
.. ап = 61&2 ... &„ + «*2\
где Т и ^ — целые числа. Перемножая полученные равенства, мы
имеем
...апап+\ = Ьф2 ... ЬпЬ„ + 1 + m F,62 ... bnt+bn+[T+mTt).
Справа в скобках стоит целое число, поэтому
... bnbn+i (mod m),
а это и требовалось.
Из доказанной леммы вытекает, что обе части сравнения мо-
можно возводить в любую целую неотрицательную степень.
Как тривиальный частный случай можно получить следующий
факт: произведение чисел вида At + 1 тоже имеет вид 4t + 1.
В самом деле, пусть аь аг, ..., ап — данные числа.
По условию,
а! = 1 (mod 4), аг=\ (mod 4), ..., а„г=1 (mod 4).
Перемножая эти сравнения, мы получим, что
... а„з=1 (mod 4).
49

19.	Правила сокращения сравнений также подобны правилам
сокращения равенств: равенства можно сокращать на любое чис-
число, отличное от нуля, а сравнения — на любое число, взаимно
простое с модулем.
Лемма. Если
асн=6с (mod m),	B.11)
причем (с, т) = 1, то
а = 6 (mod m).	B.12)
Доказательство. Сравнение B.11) означает, что раз-
разность ас — be делится на т. Но
ас — be — (а — Ь) с,
а так как (с, т) = 1, на т должна делиться разность а — Ь, что
и означает B.12).
20.	Во многих вопросах оказывается полезным следующее ут-
утверждение, называемое «малой теоремой ферма».
Теорема. Если р — простое число, и а не делится на р,
то
ар-' = 1 (modp).
Доказательство. Рассмотрим числа
а, 2а	(р — \)а.	B.13)
Никакие два из них не сравнимы по модулю р. Действи-
Действительно, из
ka^la (mod p)
ввиду (а, р) = 1 по п. 19 следовало бы, что
k == / (mod p),
т. е. что k — / делится на р, чего при 0 <L k, I < р -я k Ф I быть
не может.
Кроме того, ни одно из рассматриваемых чисел не делится
на />.
Значит, все числа B.13) при делении на р дают различные
остатки Ль г2	Гр-i, каждый из которых отличен от нуля. Но
чисел B.13) р—1 штук, а ненулевых остатков от деления на р
тоже р—1 штук, и все они различны. Следовательно, при деле-
делении чисел B.13) на р с остатком (т. е. среди чисел гь г^ ...
.... Гр-\) каждый из остатков 1, 2, ..., р—1 встретится ровно
по одному разу. Итак, мы имеем
a^srj (mod p),
2аз=Л2 (mod p),
(р — 1) a^rp-\ (modp).
Перемножая все эти сравнения почленно, мы получаем
1-2. ... ¦(p-\)ap-l = rlr2...rp-l{modp). B.14)
Б0

Но, как уже было замечено, числа Г\, г2, ..., rp-i— это те
же числа 1, 2, ..., р—1, только выписанные в каком-то ином
порядке. Следовательно, сравнение B.14) можно переписать как
1-2- ... •(р-\)а"-1^\-2- ... • (р - \) {той р). B.15)
Заметим, наконец, что произведение 1-2-...- (р—1) взаим-
взаимно просто с р, и потому в сравнении B.15) можно произвести
сокращение:
ар-' = 1 (modp),
что и требовалось.
21. Из сказанного в п. 2 следует, что среди делителей чисел
Фибоначчи имеются все вообще числа. Сейчас мы убедимся в том,
что можно выделить некоторые классы чисел Фибоначчи, обла-
обладающие делителями довольно конкретного вида.
Например, имеет место следующая теорема*):
Теорема. Если число Фибоначчи имеет нечетный номер, го
все его нечетные делители имеют вид 4^+1.
Доказательство. Формула A.10) (см. п. 9 § 1) в слу-
случае нечетного п дает нам
откуда
«„_,«„+, - и2п = «„_, («„_, + «„) - и\ =
= "Li +«„-!«„- «п = -!• B.16)
Пусть р — простой делитель ип, причем р # 2. Из B.16)
следует, чтои^_1+1 делится иа и„, и потому на р. Следовательно,
ttn-i = ~ ' (mod p).
Возводя почленно это сравнение в степень —-—, мы по-
получим
р-1	р-1
("n-l) 2 ==ttn-l=(~l) 2 (mod р).
Далее, (ип-\, ип) = 1, так что «я— i не делится на р, и мы ока-
оказываемся в условиях «малой теоремы Ферма», согласно которой
Но тогда и
р-1
(-1) 2 =l(modp),
*) Автор признателен ленинградскому любителю чисел Фибо-
Фибоначчи тов. Фрейштадту, обратившему его внимание на этот факт.
51

т. е. (—I) 2 = I. Следовательно, число —	четное, а это
означает, что р имеет вид 4/ + 1.
Итак, все простые нечетные делители ип имеют вид 4/ + 1.
Следовательно, ввиду сказанного в конце п. 18, такой же вид дол-
должны иметь и все их произведения, т. е. все вообще (см. п. 5
§ 1) нечетные делители и„.
22. Согласно определению сравнения все числа, дающие при
делении на т один и тот же остаток, сравнимы между собой по
модулю т. Наоборот, если числа при делении иа т дают различ-
различные остатки, то они несравнимы.
Остатком от деления на т может быть одно из т чисел:
1, 2	т—1. Следовательно, несравнимых друг с другом по
модулю т чисел может быть не более, чем т.
Пусть т нечетно; возьмем числа
т — 1	т — 3	into	т — 3 т — '
B.17)
Этих чисел т штук, и никакие два из них не сравнимы по мо-
модулю m (иначе их разность, которая по абсолютной величине
меньше, чем т, и отлична от нуля, делилась бы иа т). Следова-
Следовательно, каждое число сравнимо по модулю т с одним из чисел
списка B.17). Числа B.17) называются абсолютно наименьшими
вычетами по модулю т. Очевидно, абсолютная величина каждого
из абсолютно наименьших вычетов меньше половины модуля.
Заметим, что систему абсолютно наименьших вычетов можно
построить и для четного т. Она будет выглядеть несколько иначе,
чем B.17):
т — 2 т — 4	. « i	т — 2т
	—'	~	-I.°. I—- —2—, Т.
Система абсолютно наименьших вычетов для четных т нам
ие будет нужна.
23. Пусть т — нечетное число, не делящееся иа 5. Составим
последовательность абсолютно наименьших вычетов по модулю т
чисел 5, 2-5, 3-5		=	5. Например, при т = 21 этой по-
последовательностью будет
5, 10, -6, -I, 4, 9, -7, -2, 3, 8.
Выясним чередование положительных и отрицательных аб-
абсолютно наименьших вычетов в последовательностях такого рода
при различных т. Оказывается, что оно будет зависеть от послед-
последней цифры числа т (в десятичной записи).
Лемм а. Если т = \Qt -\- 1, то последовательность абсолют-
абсолютно наименьших вычетов устроена следующим образом:
t положительных, t отрицательных, t положительных, t отри-
отрицательных, t положительных.
52

\
Если т = 10/ + 3, то схема чередования знаков будет
такой:
t положительных, t отрицательных, t положительных, / + 1
отрицательных, t положительных.
Если m = 10/ + 7, то в последовательности будет t положи-
положительных, t -f- 1 отрицательных, / + 1 положительных, t отрица-
отрицательных, / + 1 положительных.
Если m = 10/ + 9, то мы получим t положительных, t + 1
отрицательных, t + 1 положительных, / + 1 отрицательных, / + 1
положительных.
Доказательство проводится непосредственным подсче-
подсчетом порознь для каждого из четырех сформулированных утвер-
утверждений. Мы ограничимся доказательством первого из них, предо-
предоставив читателю разбор остальных.
Итак, пусть m = 10/ + 1- Очевидно, при k ^ / будет
5ft < —г—, так что все такие числа 5k уже являются абсо-
абсолютно наименьшими вычетами по модулю т. Количество их равно
/, а последним будет 5/. Так как 5 (/+ 1) >	—, следующий
абсолютно наименьший вычет будет отрицательным (ои будет ра-
равен —5/+ 4). Прибавляя к нему последовательно одну за дру-
другой / — 1 пятерок, мы получим всего серию из / отрицательных
чисел, которая заканчивается на —1. Затем будет положительное
4, а за ним — еще t — 1 положительных чисел (т. е. до 4 + (/ —
— 1)-5 = 5/— 1 включительно), после чего снова появляются от-
отрицательные числа (от —5/+ 3 до —2; всего / штук). Наконец,
от 3 до 5/ — 2 мы получаем завершающие / положительных чле-
членов последовательности.
Этим требуемое доказано.
В сущности, основным итогом этой леммы для нас будет
то обстоятельство, что при т = 10/ ± 1 в последовательности
абсолютно наименьших вычетов имеется четное число отрицатель-
отрицательных членов, а при т = 10/ ± 3 — нечетное.
24. Лемма. Если р — простое число вида 5/±1, то
Р-1
5 2 — 1 делится на р.
р-1
Если р — простое число вида 5/ ±2, то 5 2 +1 делится
на р.
Доказательство. Мы имеем
5а=е,Г[ (mod p),
2-5=Е2Г2 (mod p),
Ep-irp-i
где ZtSk — абсолютно наименьший вычет k-5 по модулю р, при-
причем гн > 0, а е* = ±1 и указывает на знак вычета.
53

Перемножая все эти сравнения, мы получаем
р-1
1-2- ... -^--5 2 ^eIe2...e?_Lr1r2...r?_, (mod p).
2	2
12.18)
Дальше ведется рассуждение, напоминающее то, которое
было проведено в ходе доказательства малой теоремы Ферма.
Каждое из положительных чисел г^, г2, ..., г _j не прево-
2
р-1
сходит числа ———.
Если бы среди этих чисел нашлись одинаковые: гк = п
[ 1 sg k, I sS —-—), то было бы 5k == ±5/(mod р), а ввиду
того, что E, р) = 1, и k s= ±/(modp). Но этого не может быть,
так как —р <. k — /<4+1</) и i — / ф 0. Следовательно, все
числа /"j, /'2,..., /¦,,_! различны. Значит, этими числами будут
1, 2	 —-—, расположенные в некотором порядке. Все они
взаимно просты с модулем, и поэтому мы можем сравнение B.18)
сократить на произведение 1-2- ... ¦ ~-—. В результате мы
р-1
получаем 5 1 ?=8]В2 ... е р_: (mod p).
Согласно лемме п. 23 в произведении е^ ... ер_| число со-
множителей, равных —1, четно при р = \0t + 1 (ввиду нечетно-
нечетности р это равносильно тому, что р имеет вид 5^ ± 1) и нечетно
при р = 1СМ ± 3 (т. е. р имеет вид bt ± 2).
Отсюда непосредственно получаются оба утверждения леммы.
25. Теперь мы можем доказать основное свойство делимости
чиссч Фибоначчи на простое число.
Теорема. Если простое число р имеет вид Ы ± 1, то up_i
делится на р. Если р имеет вид bt ± 2, то up+i делится на р.
Доказательство. Пусть р имеет вид 5^ ± 1. По фор-
формуле Бпне мы имеем
si

или, после очевидных упрощении,
Р-з
В силу сказанного в п. 17 все перечисленные здесь биномиальные
коэффициенты сравнимы по модулю р с —1. Поэтому
4- 5 + ... +5 ) (mod p).
Суммируя встретившуюся нам геометрическую прогрессию и учи-
учитывая, что 2"~i по модулю р сравнимо с единицей, получим
р-1
2 -1

(mod р).
Но по предыдущему числитель стоящей справа дроби делится на
р. Так как (р, 2) = 1, и вся дробь делится на р. Значит, и uv-\
делится на р, так что первое утверждение теоремы доказано.
Обратимся к случаю, когда р имеет вид Ы ± 2. Тогда, приме-
применяя, как и выше, формулу Биие, мы получим
'' )
modp).
По п. 16 все члены в скобках, кроме двух крайних, делятся на р, а
Ci+i = Ср+1 при делении иа р дает в остатке единицу. Поэтому
(	р~х\
^Y +5 2
Применение в данном случае предыдущей леммы дает нам, что
Ыр.ц делится на р.
26.	Пусть ип делится на некоторое простое число р, причем
ин одно из чисел Фибоначчи, меньших и„, не делится иа р. В этом
случае мы будем называть число р собственным делителем ип.
Например, 11 есть собственный делитель ui0, 17 — собственный
делитель ы9 и т. д.
Оказывается, что всякое число Фибоначчи, кроме ии и2, us и
U|2, обладает хотя бы одним собственным делителем.
Доказательство этого факта потребует довольно сложных рас-
рассуждений и займет всю оставшуюся часть этого параграфа. При
этом мы попутно установим ряд дальнейших свойств чисел Фибо-
Фибоначчи, связанных с их делимостью.
27.	Начнем с некоторых общих теоретико-числовых сообра-
соображений.
Установленный нами в п. 8 важный факт о делимости про-
произведения на простое число позволяет доказать теорему, которая
иногда называется «основной теоремой арифметики».
55

Теорема. Всякое натуральное число разлагается на про-
простые множители лишь одним способом.
Доказательство. Заметим прежде всего, что возмож*
ность такого разложения является весьма простым фактом и была
установлена нами еще в п. 5 § 1 при помощи непосредственного
индуктивного рассуждения.
Для доказательства единственности разложения рассмотрим
два возможных разложения числа a via простые множители:
Будем для определенности считать, что k :? /. Здесь правая
часть должна делиться на pi. Поэтому согласно сказанному в'
п. 8 иа Pi должен делиться хотя бы один из входящих в нее со-
сомножителей. Пусть, для определенности, <7i делится на р\. Так
как число Ц\ простое, это возможно лишь при pt = q^. Произведя
сокращение, мы получим
Повторяя это рассуждение k раз (индукция!), т. е. до исчерпания
всех сомножителей слева, мы придем в итоге к равенству
1 =
Но последнее возможно лишь при q/t+i = ... = qi = 1, т. е. про-
простые сомножители q^+i	qi должны отсутствовать.
Теорема доказана.
28.	Объединяя в разложении а иа простые сомножители все
одинаковые сомножители в степени, мы получим
	 I 2	k	/п 1Л\
a = Pl P2 ••' Рк •	B.19)
Это представление натурального числа а называется его канони-
каноническим разложением.
Иногда ради формальных удобств мы будем приписывать к
каноническому разложению числа еще произвольные новые про-
простые сомножители с нулевыми показателями.
29.	Как легко проверить, для того чтобы число а с канониче-
каноническим разложением B.19) делилось на
b=p^pl2 ...plh,	B.20)
необходимо и достаточно, чтобы было
(В частности, если некоторое а/ = 0, то должно быть и Рг = 0.)
Теперь мы можем по-новому описать наибольший общий де-
делитель двух или нескольких чисел.
Пусть Я], а2, •••, о.п — произвольный набор натуральных чи-
чисел, и р{	pk — все такие простые числа, что каждое из них
56

является делителем хотя бы одного из чисел а,, а2	ап. На-
Напишем канонические разложения для аь а.2 ..., ап:
	 _а21па22	na2k
~Pi Рч •••Рк >
а _ патпап2 nank
"п — Pi Рг ••• Рк
(здесь все показатели ац Ss 0). Очевидно, всякий общий дели-
делитель d чисел аь • • •, о.п может иметь в своем каноническом раз-
разложении лишь простые множители из числа plt ..., р%-
При этом каждый показатель б< не должен превосходить каждого
из соответствующих ему показателей ак, аи	ам, входящих
в разложения аи а^, ..., ап при рс.
б^а,., 6;^a2i	6^«„г.	B.22)
Если этот общий делитель d является наибольшим общим
делителем, то показатели 6< должны быть наибольшими из всех
чисел, удовлетворяющих соответствующим неравенствам B.22).
Но это значит, что каждое bi должно быть просто наименьшим
из соответствующего набора чисел аи, a-ii	o-ni. Это можно
записать так:
6; = гтпп{аи, a2i	ani).
Наибольший общий делитель чисел аи аг, .. •, ап обозначается,
как и в случае двух чисел, через (аь а2, ..., а„).
30. В некотором смысле двойственным к понятию наиболь-
наибольшего общего делителя является понятие наименьшего общего
кратного.
Очевидно, всякое число, делящееся на числа ait аг, •.., ап
с каноническими разложениями B.21), должно иметь в своем ка-
каноническом разложении все простые сомножители, входящие хотя
бы в одно из разложений B,21), т. е. числа pi, p%, ..,, р*. Кроме
того, в каноническое разложение общего кратного могут входить
еще какие-либо «посторонние» множители. Таким образом, кано-
каноническое разложение всякого общего кратного т чисел аи а% ...
..., ап должно иметь вид
т = р, 'р22 ... pkKQ,
где через Q обозначено произведение всех «посторонних» простых
множителей. При этом, очевидно, для любого i= 1, ..., k дол-
должно быть
Цг^а,г, H?Sa2i	V-i^v-m-	B-23)
Если т является наименьшим общим кратным чисел аи а2, ...
..., а„, то, очевидно, множитель Q должен отсутствовать совсем
(т. е. он должен быть равен единице), а все показатели Ц' долж-
57

ны быть наименьшими из тех, которые удовлетворяют неравен-
неравенствам B.23). Но последнее означает, что каждое ц< должно быть
просто наибольшим числом среди аи, аг<, • ¦ ¦. ЧпС
,л,. = тах{аи, a2i	ani).
Наименьшее общее кратное чисел alt а2, • • •. а.п обозначается
через [аь аг, ¦¦ ¦, а,,}-
.51. Докажем вспомогательную лемму.
Лемма. Каковы бы ни были числа аь аг, .... а„,
max {а,, а2	а„} == ах + а2 + ... + ап —
— min {аь а2} — min (а,, а3} — ... — min {а„_ь а,г} +
4- min {аь а2, а3} + min {аь а2, сц} + ...
± min {ai. a2	ап)	B.24)
'(здесь во второй строке стоят все минимумы из двух чисел, в
третьей — все минимумы из трех и т. д.).
Доказательство. Не нарушая общности, мы можем с
самого начала считать, что числа ai, a2	а„ расположены
в порядке невозрастания:
«I ^ a2 S: ... S: ап.
Тогда
max (а,, а2, ..., а„} =О|.
Вычислим значение левой части B.24). Подсчитаем для этого,
сколько раз (алгебраически) входит в нее каждое из чисел ai,
<хг, .... а.п- При этом в случае равенства двух чисел at и а/ мы
будем в качестве минимального писать то, какое имеет больший
номер (очевидно, это чисто формальное соглашение не влияет на
величины рассматриваемых нами выражений).
Заметим сначала, что а, является самым большим из рассма-
рассматриваемых нами чисел. Поэтому оио входит только в первую
строку правой части B.24) и притом ровно один раз. Значит, в
правой части B.24) коэффициент при ai равен единице.
Рассмотрим теперь вхождение в правую честь B.24) некото-
некоторого ai(i > 1). В первую строку оно войдет один раз. Во вто-
вторую и последующие строки до t'-й включительно оно войдет лишь
от тех минимумов, в которых вместе с щ стоит сочетание чисел
с номерами, меньшими, чем и Для каждой /-й строки (/ 2S i)
число таких вхождений будет равно числу сочетаний из I — 1 чи-
чисел ai, ..., а;-, по /' — 1 т. е. С{~{ (см. п. 14 § 1). Общее число
вхождений ш, таким образом, будет равно
На основании п. 13 § 1 это выражение равно нулю.
Следовательно, правая часть B.24) равна аь т. е. левой ча-
части, и лемма доказана.
32. Воспользуемся доказанным для удобного описания наи-
наименьшего общего кратного нескольких чисел.
Б8

Теорема.
[аи «а, ..., ап] =
=	а'"г ¦ ¦¦ ап (fli,
(а,, а2) (ai, а3) ... {ап-и ап) (аь а2, аз, at) ... '
B.25)
(Здесь в числителе стоит произведение исходных чисел, наи-
наибольших общих делителей всевозможных их троек, пятерок и т. д.,
а в знаменателе — произведение всех наибольших общих делите-
делителей пар исходных чисел, их четверок и т. д.)
Доказательство. Пусть р— произвольный простой со-
сомножитель, входящий в канонические разложения некоторых из
а\, пъ, ..,, а„- Обозначим через а< показатель, с которым р вхо-
входит в каноническое разложение аи Тогда в левую часть B.25) он
согласно п. 30 войдет с показателем
max {(*!, а2, ..., а,г},	B.26)
а в правую согласно п. 29 — с показателем
а2 + ••• + а«
— min{ai, aj) — min {аь а3) — ... — min {а,,--ь о,,} +
+ min {aj, а2, а3} + min {а,, а^, а4) + ...
±min {ai, a2, ..., а„).	B.27)
На основании же предыдущей леммы выражения B.26) и B.27)
равны друг другу.
Таким образом, в канонических разложениях правой и левой
частей B.25) имеются одни и те же простые сомножители и вхо-
входят они с одними и теми же показателями.
33. Вернемся к изучению делимости чисел Фибоначчи.
Лемма.
итп-\ ~ и™-\ делится на и\.	B.28)
Доказательство ведется индукцией но т.
При т = 1 делимое обращается в нуль, и потому делится па
trn. Предположим теперь, что делимость B.28) справедлива, и
рассмотрим
«<m + l)«-l - «я-/ = («m»-l«»-l + итпип) ~ "«-/•
Но по индуктивному предположению
Следовательно,
«(т+,)Я-1 ~ С-/ ^ <-1«я-| + "т„"п - С-/ (mod u\). B.29)
Как вытекает из п. 1, итп делится на ип; поэтому
59

и B.29) превращается в
«-1 ~ «Т-/ =¦ 0 (mod и*).
Индуктивный переход обоснован; теорема доказана.
34. Лемма.
итп — «7+1 + -1 делится на и\.	B.30)
Доказательство ведется индукцией по т.
При т = 1 делимое обращается в нуль и поэтому делится
на и\.
Предположим, что делимость B.30) имеет место, и рассмотрим
«Си+0/. - -И + "«-I1 = ««»-!«« + ««„«„-и - «7н + «ТА'-
Но по индуктивному предположению
««»-«"+!-«7-1 (mod в» >
Следовательно,
«(m+l)nj"~ "n+i + "«-i ^
-«mi.-!4». + "« + 1 («7+1 - «7-l) - «ТА' + «7-11 (mod U%),
ИЛИ
«(«+!)« -«7-и + «ТА1 s"m«-i"«--i («»+i-«B-0 (mod «3„)
или
- +.1 + "ТА1 - «„ (««„-1 - «7-0 (mod «Л).
По предыдущему стоящая справа разность делится на и2п. По-
Поэтому вся правая часть делится на и^, т. е. сравнима с нулем но
модулю v?n, а это и требовалось.
35. Пусть р — простое число. Как показано в п. 1, и,1р де-
делится на ип. Поэтому при переходе от ип к и„р, во-первых, могут
появиться новые простые делители, а во-вторых, могут повы-
повышаться показатели при старых простых делителях члена ип. Мы
докажем сейчас теорему, из которой будет следовать, что из всех
простых делителей мя показатель может повыситься разве лишь
у р. Если рф2, то показатель при р увеличивается лишь на еди-
единицу, а если р = 2, то не более, чем на 2.
Теорема. Если q — простой делитель ип, отличный от рг
то	 не делится на q.
ип
60

Если р — простой нечетный делитель ип, то 	 делится на
р, но не делится на р2.
Если и„ делится на 4, то —— делится на 2, но не делится
ип
на 4.
Если ип делится на 2, но не делится на 4. то —— делится
ип
на 4, но не делится на 8.
Доказательство. Полагая в предыдущей лемме m = р,
мы получим, что
ипр - ип+\ + "п-1 Делится на и%
Но и„р делится на ип согласно п. 1, а
«S+1 - «5-1 = ("я+1 - "«->) «+\ + «?ни»-1 + • • • + <=0 =
Следовательно, разность
^ -«;! + <-«„-!+...+«-!) B.3D
делится на ы^.
Во-первых, отсюда следует, что разность B.31) делится на
ип- Это значит, что
^7 " "»+' + "»+'"«-' + • • • + <-\ (mod «»)• B-32)
Но, очевидно,
«n+i = «n-i (modun).
Поэтому из B.32) следует, что
Так как справа имеется р слагаемых, должно быть
	 == ри^\ (mod un).
Следовательно, всякий общий делитель чисел — н ип должен
ип
делить также р, и наоборот. Это значит, что
~^~-, ип)=(р, ип).
Ufl	S
Если теперь q — простой делитель и„, отличный от р, то
(р,и„), равный 1 или р, не делится на q.
61

Следовательно, и I 	, ип \, равный 1 или р, тоже не де-
делится на q. Но так как ип делится на q, на него не может де-
литься 	, и первая часть теоремы доказана.
ип
Во-вторых, если р — делитель ип, то из делимости разности
B.31) на и1п следует, что
Разделим un+1 и ип-\ дважды последовательно иа р с остат-
остатком. Пусть
«n+i = rip + r' (mod p2),
ип-\ = г2р + г" (mod р2),
где 0 ^ Г[, г2, г', г" < р (поскольку разность «„+i — un-i равна
(;„, т. е. делится на р, остатки г' и г" должны быть равны; поло-
положим поэтому т' = г" = г); при этом г ф 0, так как ни ил-и ни
a,,+i иа р не делятся).
Тогда
г) + ...
"'1
... +(r,p+r)P-fc(r2p + r)ft-1 + ... + (Г2Р + г)"'1 (mod p2^
Раскроем справа скобки и отбросим слагаемые, делящиеся на р2.
k и член
даст нам при этом
Cl^krxpr"-k-lrk~l + г"-^^,^-2 +
или
(р - к) рпг"-2 + (ft - 1)	2
Суммируя это выражение по всем членам, т. е. по k = 1, ..,, р,
мы получим
ъ
B 33)
Если р ?= 2, то -^-5— является целым числом. Поэтому
первые два слагаемых в B.33) справа делятся на р2, и мы полу-
получаем
62

Наконец, по малой теореме Ферма (см. п. 20J г" — 1 делится
на р, и, значит, рп>-1 — р делится на р2. Учитывая это, мы окон-
окончательно получаем
—— «и р (mod рг).
ип
Таким образом, 	 при делении на рг дает в остатке р,
"п	а
т. е. делится на р, ио не делится на р', и мы доказали вторую
часть теоремы.
Пусть теперь р = 2. Тогда B.33) можно переписать как
212. s 2 (п + r2 + r) (mod 4).	B.34)
"я
Если ип делится на 4, то из последовательности остатков
B.2) видно, что в этом случае как ип-\, так и un+i при делении
на 4 дают в остатке 1. Следовательно, в этом случае г\ = г% = 0.
а г = 1, и B.34) превращается в
2UL щ, 2 (mcd 4).
ип
Это доказывает третью часть теоремы.
Наконец, пусть и„ не делится на 4. Последовательность B.2)
показывает, что теперь п = 1, г2 = 0 и г = 1. Поэтому B.34)
превращается в
^- 0 (mod 4).
Нам остается показать, что in не делится на 8. Но если
ип
бы это было так, то член и2п делился бы на 16. Но тогда соглас-
согласно сказанному в п. 13 2п должно делиться на 12, т. е. п должно
делиться на 6. Но отсюда в свою очередь следует, что ип должно
делиться на ив, т. е. на 8, а это противоречит предположенному
(именно тому, что ип не делится даже на 4).
Теорема доказана полностью.
36. Теперь мы можем непосредственно заняться доказатель-
доказательством существования собственных делителей у чисел Фибоначчи.
Теорема. Всякое число Фибоначчи, за исключением ии иг,
ие и н12, имеет хотя бы один собственный делитель.
Доказательство. Рассмотрим число Фибоначчи и„.
Пусть каноническое разложение числа п будет
а, а„	afe
Возьмем все числа Фибоначчи
«?, Ujl,...,Ujl	B.35)
63

и составим их наименьшее общее кратное М. Согласно п. 32
М _	Pl P2	Pft V Pl
и_п_> и п у • • ("¦ п • и_пЛ(ил: ил: ujl' ujl] ••' '
Pi Р2/ Ч Pft-i Pft/V Pi Pj Рз Р4/
Но при любых г и различных t'i, h	«V
и_Л_< u_nj •••' u_n_\==u(_IL- -JL-. -Л-
"/, РН	р'гУ ЧРН ' »h 	 pir
i ft,-Pi,
Поэтому
м
и
п
Р\Рг
и
и
пи п
Р\ Рг
п
P\Pi
,,.
.. и
и
р,
п
Pk
п
k—
и
\Р
п
Р[Р2Рз
и „
k PIP2P3P4
Ho «rt делится па все числа и п , и п , ..., и п , а потому и на
~р~\ "р7	"р7
их наименьшее общее кратное М:
й„ = ML
Всякий простой делитель М делит одно нз чисел B.35) и по-
потому является несобственным делителем ип. Следовательно, все
собственные делители ип должны делить t. Согласно теореме п. 35
из простых несобственных делителей ип в t могут входить разве
лишь р\, р2, . ¦ •, Pk, причем каждое из этих чисел входит в t с по-
показателем, не большим единицы, за исключением двойки, которая
может входить с показателем 2.
Доказав неравенство
(крестик под двойкой здесь и далее означает, что эта двойка фак-
фактически присутствует лишь в том случае, когда среди чисел pi,
р2	Pk уже имеется одна двойка), мы установим существова-
существование собственных делителей у числа Фибоначчи ип.
Итак, докажем, что
„ ¦ ¦.	х
Pi Рг	Pk P1P2P3
64

В п. 21 § 1 было показано, что
П
¦у5	¦у о
Поэтому если все числа Фибоначчи в числителе дроби заме-
[	Я- —	j	П-\
нить иа —т=^а . а в знаменателе — на —— а " ,
V5	У 5
то дробь только уменьшится. Доказав требуемое неравенство
для новой дроби, мы установим даже несколько больше, чем
нужно.
Выполнив указанные замены и произведя сокращение на
/ 1 у*-1
[ —рг } , мы получим
\
п
р. П Рп П	Ри П
ИЛИ
м.-' ' 1 . 1 . . 1 1
а
„A_^_JL_...__L4
г* \	1	2	в
. +Pft+P,Pj+ ... +РЛ_,Р6+Р1Р2Рз+ .
или
или, логарифмируя,
-ТA
3 На Н. Воробьев	65

Еспоминая каноническое разложение числа п, мы можем
это йеравенство переписать как
Pi'"'
р, + 1 Р2+
а,
Р-2
Выражение Р[' (Р| — 1) ... pfcft (pfe — 1) принято обозна-
обозначать через <p(i). Эта функция называется функцией Эйлера. Она
обладает многими важными и интересными свойствами.
Введя обозначение функции Эйлера, мы .получим
B.36)
V	Р'2	Рк
Нам осталось проверить, для каких целых положительных
значений п написанное неравенство выполняется. Мы будем эти
значения называть «хорошими», в отличие от «плохих», для кото-
которых B.36) не имеет места. Очевидно, для хороших значений п
числа Фибоначчи ип будут иметь собственные делители. Подчерк-
Подчеркнем, что обратное может и не иметь места: справедливость нера-
неравенства B.36) есть лишь достаточное, но отнюдь не не-
необходимое условие наличия у ип собственных делителей. По-
Поэтому числа Фибоначчи с плохими номерами (а их наберется
10 штук) будут подлежать дополнительной проверке на наличие
собственных делителей. В результате этой проверки окажется,
что шесть чисел нз этого десятка обладают собственными дели-
делителями, а четыре (перечисленные в условии теоремы) -— нет.
«На глаз» видно, что левая часть B.36) увеличивается с ро-
ростом п существенно быстрее, чем правая. Поэтому с самого на-
начала следует предполагать, что нарушения неравенства B.36) бу-
будут происходить лишь при небольших значениях п. Однако обе
части неравенства при общей тенденции к возрастанию изменяют-
изменяются при увеличении п весьма неправильным образом, и какие-либо
непосредственные индуктивные рассуждения едва ли применимы.
Следовательно, представляется естественной следующая про-
программа действий. Наметим некоторую схему последовательного
перечисления (выписывания) натуральных чисел, при которой от
хорошего числа можно переходить только к хорошему. Если на
некотором шаге применения этой схемы все получаемые числа бу-
будут хорошими, то тогда и все дальнейшие числа также будут хо-
хорошими. Следовательно, все плохие числа должны быть перечис-
перечислены уже до этого шага. Читатель может заметить, что такой
способ рассуждений также является одним из вариантов доказа-
доказательства по индукции.
Докажем предварительно следующие три утверждения.
1. Пусть р^ pi, ..., Рь, ... — все простые числа, перечислен-
перечисленные в порядке их возрастания (т. е. pi = 2, р2 = 3 и т. д.). Тогда,
если число n = pip2...pk хорошее и pii+i > 3, то число
... pkpk+i также хорошее.
66

Действительно, в данном случае мы имеем
... pk,
и по условию должно быть
B-з7)
Для того чтобы написать соответствующее неравенство для
произведения pip2. • • P*P*+i, нужно первое слагаемое правой ча-
части B.37) умножить на 1 -\	, что меньше двух, а ко вто-
+
рому добавить loga p*+i. Но число pip2 ¦ • -Р*-1 взаимно просто
с каждым из простых чисел ри р2, ..., Pk- Следовательно, ка-
каждый его простой делитель q больше любого из этих чисел и по-
потому пе меньше, чем р*+1. Значит,
и тем более
поэтому
Следовательно, прибавление ко второму слагаемому loga
увеличивает это слагаемое менее, чем вдвое.
Итак, правая часть не может увеличиваться более, чем в два
раза. Но левая часть умножается на p*+i— 1, что больше 2. Зна-
Значит, из B.37) следует
и требуемое доказано.
2. Если п — ptp2... рь, где рх, р2	 р* — произвольные
различные простые числа, п — хорошее число, а q — произвольное
простое число, отличное от р\, рг	р* и большее, чем рь то
qp2...pk также является хорошим числом.
В самом деле, в этом случае неравенство B.36) снова имеет
вид B.37). Произвести здесь замену р\ на q — все равно, что
прибавить клевой части B.37) произведение (q — р\) (рг—1) ••¦
... (Рк — 1), а в правой умножить первое слагаемое на
3*	67

¦	т— и прибавить ко второму loga ——. Ввиду того, что
li	Р1
Pi
q > Pi, первое слагаемое от такого умножения может лишь
уменьшиться.
Значит, для сохранения в силе неравенства достаточно, чтобы
было
(q — pi) (p2 — 1) ... (рп — 1) > loga	>
и тем более достаточно, чтобы было
q— pi > Ioga—•	B.33)
Однако при п =г 3 мы имеем a > 	р, так что
1 > loga	г i
и суммирование неравенств такого вида по л от п = р, + 1 до
n — q дает иам B.38).
a. a,	cu	a. + l a,	ak
3. Если р{ 'р22 ... pkR — хорошее число, то р,' р2 .. .pk —
также хорошее число.
Для доказательства достаточно заметить, что при замене
в неравенстве
Р, + 1 Р2+ '	Pk+
Р{	Р-2	Pk
показателя ai на большее число «i + 1, левая часть увеличи-
увеличивается, а правая уменьшается. Следовательно, в результате та-
такого преобразования хорошее число может перейти также лишь
в хорошее.
Таким образом, в нашем распоряжении оказываются три опе-
операции над числами, три способа переходить от одних чисел к дру-
другим, причем от хороших чисел возможен переход только к хоро-
хорошим же.
Первая из этих операций состоит в построении последова-
последовательности 1, 2, 6, 30, 210, ...; вторая заменяет в числе, канони-
каноническое разложение которого содержит только первые степени про-
простых, любой простой делитель на больший (для определенности
мы будем считать, что замена производится на ближайшее «свер-
«сверху» простое число), не входящий в каноническое разложение;
третья операция увеличивает на единицу некоторый показатель
в канонических разложениях. В результате применения этих опе-
операций мы, исходя из единицы, перечислим все натуральные числа.
Некоторые числа в таком перечислении встретятся более одного
68

раза, но это обстоятельство не играет для нас никакой роли.
Важно, что каждое число хотя бы один раз будет учтено.
Начнем в соответствии со сказанным перечислять натураль-
натуральные числа. Сначала воспользуемся первой операцией.
Число 1 является плохим, так как для него неравенство B.36)
приобретает вид
1 > 1 + loga 2 = 1 + loga I = 1
(произведение натуральных чисел, содержащее нулевое число со-
сомножителей, мы по-прежнему принимаем равным единице), что
неверно.
Первая операция в применении к 1 дает 2. Для него нера-
неравенство
1 > -| + loga 2 = -|-f- loffa 4
неверно, и потому число 2 также плохое.
Плохими будут н следующие числа 6 и 30; для них:
ф F) = 2 < -| • -i + loga 12 = 2+ Ioga 12,
Ф C0) - 8 < -| • i- • J- + loga 60 et 2,4 + 8,5.
Наоборот, число 2-3-5-7 = 210 уже оказывается хорошим, ибо
<р B10) = 48>-|--i--|-y + l°Sa 420 et 2,7 + 12,5.
Поэтому все дальнейшие числа, получаемые применением первой
операции, будут хорошими. Будем применять теперь вторую и
третью операции.
Применение их к числу 2 дает нам 3 и 4, также плохие числа:
ф C) = 2 < у + loga 3 s* 1,3 + 2,3,
ф D) = 2 < -| 4- lo?a 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 (третья операция).
69

Третья операция, применяемая к 6, дает плохое 12 и хорошее
18. Но за 12 следуют по третьей операции хорошие 24 и 36, а
вторая операция к числу 12 не применяется, так как 12 делится
на квадрат простого числа 2.
Наконец, все получаемые из 30 числа (соответственно 210, 42
и 60) хорошие.
Все проведенные рассуждения наглядно описываются следую-
следующей схемой (рнс. 1).
7к
ffx
В результате мы получили следующий список плохих чисел!
1, 2, 3, 4, 5, 6, 10, 12, 14, 30.
Соответствующими числами Фибоначчи будут
1, 1, 2, 3, 5, 8, 55, 144, 377, 832040.
Очевидно, собственными делителями и3, ut, «5, «ю и и и будут со-
соответственно числа 2, 3, 5, 11 и 29. Можно было бы, выписав все
числа Фибоначчи до «зо и их разложения на множители, непо-
непосредственно убедиться в наличии собственного делителя у и30. Од-
Однако в этом нет нужды. Из теоремы п. 25 следует, что «зо де-
делится на 31 (ибо 31 есть простое число вида 5^+1)- С другой
стороны, ни us = 8, ни «ю = 55, ни «is = 610 на 31 не делятся;
Следовательно, 31 есть собственный делитель «зо-
Остались числа щ = 1, и2 = 1, и6 = 8 и «i2 = 144, которые,
очевидно, собственных делителей не имеют.
Теорема доказана.
37. В «противовес» тем четырем числам Фибоначчи, которые
не имеют собственных делителей, существуют числа Фибоначчи,
обладающие несколькими собственными делителями. Например,
70

для «is такими делителями будут числа 37 и 113, для и2? — числа
53 и 109 и т. д. Много ли чисел Фибоначчи с двумя и более соб-
собственными делителями — совершенно не ясно.
Встает естественный вопрос, каков же номер п числа Фибо-
Фибоначчи, собственным делителем которого является заданное про-
простое р?
Из п. 25 следует, что п g р — 1, если р имеет вид 5/ ± 1, и
ngf+1, если р имеет вид Ы + 2. Однако никакой формулы,
позволяющей непосредственно вычислять номера членов с наперед
заданным собственным делителем р, пока не известно.
Нами в п. 3 было доказано, что все числа Фибоначчи с со-
составными номерами, кроме щ, сами составные. Обратное неверно,
так как, например, г/19 = 4181 = 37¦ 113. Возникает вопрос, ко-
конечно или бесконечно число всех простых чисел Фибоначчи, иными
словами, существует или нет среди простых чисел Фибоначчи наи-
наибольшее? Вопрос этот сейчас еще далек от своего решения.
§ 3. ЧИСЛА ФИБОНАЧЧИ И НЕПРЕРЫВНЫЕ ДРОБИ
1. Рассмотрим выражение
<7оН	j	 ,
<72 Н	т-
*»+.	C.1)
где <7ь q2, ..., Яп — целые положительные числа, а
<?о—целое неотрицательное число. Таким образом, в
отличие от чисел q\, q% ..., qn, число qQ может рав-
равняться нулю. Это несколько особое положение числа
<?о мы всегда будем иметь в виду и поэтому не будем
его каждый раз оговаривать.
Выражение C.1) называется непрерывной дробью,
числа q0, q\, ..., qn — неполными частными этой дро-
дроби, а все непрерывные дроби вида
C.2)
— полными частными.
71

Иногда непрерывные дроби называются также
цепными дробями. Непрерывные дроби находят при-
применение в самых разнообразных вопросах матема-
математики. Читателю, желающему ознакомиться с ними
подробнее, можно порекомендовать книгу А. Я. Хин-
чнна «Цепные дроби», «Наука», 1978.
Процесс превращения -некоторого числа в непре-
непрерывную дробь называется разложением этого числа
в непрерывную дробь.
Посмотрим, как находятся неполные частные та-
такого разложения обыкновенной дроби у.
Рассмотрим для этого алгорифм Евклида, приме-
примененный к числам а и Ь:
C.3)
Первое из этих равенств дает нам
а 	 ¦ Г\ 	 ¦ 1
г,
Но из второго равенства системы C.3) следует
ь	, г2	,1
—— r= Q | -4— 	= Qt ~т~ 	,
Т\	Т\	fI
так что
"¦+7Г
Из третьего равенства C.3) мы выводим
72

; и потому
i	T = <7о + ¦
Гг
Гз
Продолжая этот процесс до конца (индукция!),
мы, как легко видеть, придем к равенству
а	,	1
•г — 9о i	j— •
U	,1
+
По самому смыслу алгорифма Евклида qn > 1.
(Если бы qn равнялось единице, то гп-\ было бы равно
гп и Гп-2 разделилось бы на гп-\ нацело, т. е. весь
алгорифм оборвался бы одним шагом раньше.) Зна-
Значит, мы можем вместо qn рассматривать выражение
(9л—0 +у. т. е. считать (qn—1) предпоследним
неполным частным и 1—последним. Такое соглаше-
соглашение оказывается удобным для дальнейшего.
2. Мы видим, что всякую рациональную дробь ~
можно разложить в непрерывную. Покажем, что это
разложение единственГнб, т. е. что у двух равных не-
непрерывных дробей должны быть равны соответствую-
соответствующие неполные частные.
Для того чтобы это доказать, возьмем две непре-
непрерывные дроби, о) и о)'. Пусть qo, q\, qi, ... и
q'Q, q\, q'2, ...—соответственно их неполные частные.
Покажем, что из равенства со = ы' следует, что
qQ = q'Q, ql = q[, q,2 —q'2 и т. д. В самом деле, q есть
целая часть числа о>, a q'o — целая часть со'; поэтому
qo=zq'Q, Далее, непрерывные дроби со и со' можно
представить соответственно в виде
73

где to, и <о[ — снова непрерывные дроби. Из со = с/
и qa = q'Q следует, что и со( = к>\. Значит, равны и целые
части чисел (л{ и со^, т. е. q{ и <?[. Продолжая эти
рассуждения (индукция!), убеждаемся в том, что
92 = G2' ЯЛ = Я'3 и т- Д-
3. Пусть
ю = <7<Н	j—
C.4)
— некоторая непрерывная дробь. Рассмотрим сле-
следующие числа:
<7о, <?о + —. 9оН	—. ...
qi + —-
Эти числа, записанные в виде обычных несокра-
несократимых дробей
Рр	д0
Qo ~ 1 '
называются подходящими дробями непрерывной дро-
дроби со. Заметим, что переход от —¦ к ,А!+' осуще-
ствляется заменой последнего неполного частного из
числа участвовавших в построении этой подходящей
дроби, т. е. <7й, на qk~\	. Точно в том же самом
Рк
смысле переход от подходящей дроби -— ко всей
непрерывной дроби со осуществляется заменой послед-
последнего неполного частного аи на qk~\	, т. е. на
соответствующее полное частное (о
74

4. Важную роль в теории непрерывных дробей
играет следующая лемма.
Лемма. Для всякой непрерывной дроби C.4)
имеют место следующие соотношения:
Pk-i.	C-5)
Q*-i,	C-6)
Pft+iQft-^Qft+i = (-l)*.	C-7)
Будем доказывать все эти равенства одновременно
индукцией по k.
Докажем их сначала для k = 1:
Так как числа qoqi + 1 и #i взаимно просты, дробь
несократима. Дробь же -^у несократима по
определению, а у равных несократимых дробей равны
числители и знаменатели. Значит, Pi = qoqi + 1 и
Qi = q\. Далее,
т—• C-8)
Яг
Наибольший общий делитель чисел qo{q\q2-\-\)-\-,
+ q2 и ^1^2+1 на основании п. 10 § 2 равен
(<?2> 9192+1) и па основании того же предложения
равен (<?2, 1), т. е. 1. Значит, дробь, стоящая в C.8)
справа, несократима, и потому
Л> = <7о (<7i<72 + 0 + q-2 = (qoqi + О Я2 + 9о = -Pi<?2 + /'о
Равенство
проверяется без труда.
Этим основание индукции доказано.
75

Предположим теперь, что равенства C.5), C.6) и
C.7) справедливы, и рассмотрим подходящую дробь
Pk-\	C 9)
^ '
Переход от Qk+i к -Qk+i- по сделанному ранее заме-
замей
чанию осуществляется заменой Qk+i B выражении
для пк+[' на qk+i H	", так как в выражения для
Vft+1	qk+2
Pk> Qb Pk-i> Qk-i величина qk+\ не входит, мы имеем
или, вспоминая индуктивные предположения C.5)
и C.G),
Pk+2	Pk+^k+2 + Pk	/о ,пч
Докажем несократимость дроби, стоящей в C.10)
справа. Для этого достаточно показать, что ее числи-
числитель и знаменатель взаимно просты.
Предположим, что числа Pk+iqk+2 + Pk и Qk+\qk+i +
+ Qk имеют некоторый общий делитель d > 1. Тогда
выражение
{Pk+iqk+2 + Рц) Qn+i — (Qk+iqk+2 + Qft) ^ft+i
тоже должно разделиться на d. По по индуктивному
предположению C.7) это выражение равно (—1)*+1
и делиться на d не может.
Итак, правая часть C.10) несократима, и C.10)
есть, таким образом, равенство двух несократимых
дробей. Значит,
Рк+2 = Pk+tfk+2 + Pk
II
Qk+2 — Qk+iQk+2 + Qk-
76

Для завершения доказательства индуктивного пе-
перехода нам остается показать, что
/W2*+i-^+iQft+2 = (-l)A+1. C.11)
Но ввиду только что доказанного
Pk+uQk+i — P/t+iQk+2 —
и C.11) вытекает непосредственно из индуктивного
предположения C.7). Этим индуктивный переход обо-
обоснован и вся лемма доказана.
Следствие.
Ph+l Pk (-1)"
-Q~k+1 ~0Г= QkQk+Г	FAZ)
Доказательство очевидно.
Так как неполные частные непрерывных дробей
являются целыми положительными числами, из дока-
доказанной леммы следует, что
Ро < Pi < Р-2 < ¦¦¦,
Qo<Q,<Q2< •••	(ЗЛЗ)
Это простое, но важное замечание мы в дальней-
дальнейшем еще уточним.
5. В ходе доказательства леммы предыдущего
пункта мы осуществляли переход от равенства C.10)
к равенству C.11). Если, однако, заменить в C.10)
неполное частное qu на полное частное coft, то, как
тоже было оговорено в конце п. 4, мы получим
дробь со:
Кв.,, + р. ,
== О—i—	Т~П	'	^ ' '
Теперь мы можем несколько дополнить сформулиро-
сформулированное в п. 2 утверждение о единственности разложе-
разложения числа в непрерывную дробь.
Лемма. Пусть в C.14) дробь ^~х является
Р
предпоследней, k — \-u подходящей дробью к -^-,
77

р
a (oa+i =5- 1. Тогда ~- является подходящей дробью
к (а, а со/г+1 — соответствующим полным частным.
Р
Доказ
прерывную:
Р
Доказательство. Разложим дробь -тр в не-
^
По условию мы имеем
+
p	p
где nfe~2—третья от конца подходящая дробь к ;~
^ft-2	Vn
Замена здесь ак на <7* + ——¦ приведет нас справа к
что по C.14) равно со. Следовательно,
+	Ц-, C.15)
и требуемое получено. Здесь в ходе доказательства
не было упомянуто условие co^+i ^ 1. В действитель-
действительности оно используется в самом написании выражения
C.15): в случае co^+i < 1 неполное частное qu следо^
вало бы заменить на большее число,
78

6. Применим теперь лемму п. 4 для описания всех
непрерывных дробей с неполными частными, равными
единице. Для таких дробей имеет место следующая
интересная теорема.
Теорема. Если непрерывная дробь имеет п не-
неполных частных и каждое из этих неполных частных
равно единице, то дробь равна ""+1 .
Доказательство. Обозначим непрерывную
дробь с п единичными неполными частными через ап.
Очевидно,
а1( а2, ..., а„
являются последовательными подходящими дробя-
дробями ап.
Пусть
Так как
. . 1 2
<Х2 = 1 -t-у — у,
должно быть Pi = l, Р2 = 2. Далее, Pn+l = Pnqn+i +
+ Pn-i = Pn+Pn-i- Поэтому (сравни п. 6 § 1) Рп=ип+1.
Аналогично Qi = 1, Q2= 1 и Qn+l =Qnqn+\ + Qn-i=
— Qn + Qn-\, так что Qn = un. Значит,
а„=^±1.	C.16)
Предоставляем читателю сопоставить этот резуль-
результат с формулами A.10) и C.7).
7. Пусть нам даны две непрерывные дроби со и со':
ш = 9оН	j	, со =<?0-t-—	j	,
q2 + • ¦ •	я'-г + ¦ • •
причем
?0 = 9о> Я\ ё <7l> ?2 = ?2> •••	W-1'l
79

Обозначим через
Е± A El.
Qo' Qi' Qt' '"
подходящие дроби <а и через
1± А
Q'o' Ql'
А
— подходящие дроби <а'.
Из результатов леммы п. 4 легко усмотреть, что ввиду C.17)
Наименьшим значением всякого неполного частного, очевид-
очевидно, является единица. Значит, если все неполные частные некото-
некоторой непрерывной дроби — единицы, то числители и знаменатели
ее подходящих дробей растут медленнее, чем у подходящих дро-
дробей любой другой непрерывной дроби.
Оценим, насколько медленнее происходит этот рост. Очевид-
Очевидно, если не считать непрерывных дробей с единичными неполными
частными, медленнее всего растут числители и знаменатели Под-
Подходящих дробей такой непрерывной дроби, у которой одно из не-
неполных частных есть 2, а остальные являются единицами. Такие
непрерывные дроби тоже связаиы с числами Фибоначчи, как пока-
показывает следующая лемма.
Лемма. Если непрерывная дробь со имеет неполными част-
частными числа <7о> <7i. <7г, • • •, <7/>> причем
<70 = <?i = <?2 = ••• =<7г_1 = <7* + 1= ••• =<7„ = 1'
то
Доказательство этой леммы ведется индукцией по /.
Если (' = 1, то при всяком п
{
2+ '
1 +
n — 1 неполное
частное I
80

[ или ввиду доказанного в начале этого пункта
i
\ ш=1 +	—,— = 4	=
|	2 + -1-	2 + -^-
an-i	«n
.	, 1 t	_	 _, 1 j __
ип+г
или, полагая в соответствии с п. 25 § 1 «о = О,
_
Основание индукции этим доказано.
Предположим теперь, что при всяком п непрерывная дробь
, ,
i	i неполных <
1	частных |	*	C.18)
¦+i+—Ц-
2-'
о-п-1
равна
C 1
Возьмем непрерывную дробь
1
1 +
1 +
i + 1 неполное
частное
1
2 +
а.г-t-l
Ее, очевидно, можно рассматривать н так:
1 +
C.20)
i неполных
j	частных
V	_L I I	-
1	'
an-i-i
81

Непрерывная дробь, стоящая в C.20) ниже пунктирной черты, на
основании равенства C.18) и C.19) равна
ul+lttn-l+2
Значит, вся дробь C.20) равна
+
Этим доказаны индуктивный переход и вся лемма.
Следствие. Если не все неполные частные непрерывной
дроби со являются единицами, число этих неполных частных не
р
меньше п и <?о Ф 0, то, записав со в виде обычной дроби —,
мы будем иметь
Р й= «,+1«„_,+3 + ";"„_,+, > «г + 1«„_(+2 + «iun-i+i = un+2>
и аналогично
Q > ип+1.
Существенную роль при этом, конечно, играет лемма п. 4, на
основании которой в процессе «свертывания» непрерывной дроби
в обыкновенную мы получаем только несократимые дроби. По-
Поэтому уменьшение числителей и знаменателей получаемых дробей
нз-за их сокращения не будет иметь места.
8. Из доказанного в предыдущем пункте мы можем получить
следующую теорему, указывающую на особое положение чисел
Фибоначчи по отношению к алгорифму Евклида.
Теорема. Число шагов в алгорифме Евклида, примененном
к числам а и Ь, при некотором а равно п — 1, если Ь = и„, и при
всяком а меньше п— 1, если Ъ < и„.
Доказательство. Первая часть теоремы доказывается
совсем просто. В качестве а достаточно взять следующее за Ь
число Фибоначчи, т. е. ип+\. Тогда
ип+\ _п
—и— = ап-
ип
Непрерывная дробь ап имеет п неполных частных, т. е. число
шагов алгорифма Евклида, примененного к числам а и Ь, равно
га—1.
Докажем вторую часть теоремы. Предположим обратное, т. е.
что число шагов указанного алгорифма не меньше га—1. Разло-
Разложим отношение —г в непрерывную дробь со. Очевидно, со будет
82

иметь не меньше, чем п, неполных частных (именно, на единицу
больше, чем длина алгорифма Евкчида). Так как Ь не есть число
Фибоначчи, не все неполные частные со будут единицами, и по-
потому, по следствию леммы п. 7, Ь > ип, что противоречит усло-
условию теоремы.
Доказанная теорема означает, что алгорифм Евклида, при-
примененный к соседним числам Фибоначчи, в некотором смысле
«самый длинный».
9. Выражение
<7о + ' 1	C.21)
<?2 +
1
1 <7я+ ...
будем называть бесконечной непрерывной дробью. На
бесконечные непрерывные дроби можно естественным
образом распространить определения и результаты
предыдущих пунктов.
Пусть
"о "l	Рп	/о оо\
Qo' Qi'"" Qn""	{ '
¦—последовательность (очевидно, бесконечная) под-
подходящих дробей дроби C.21). Покажем, что эта по-
последовательность имеет предел.
Рассмотрим для этого отдельно последователь-
последовательности
и
D	D	D
C.24)
На основании C.12) и C.13)
Ргп+г __ Ргп 	 Ргп+1 	 fizrc + l i Ргга + i
О.гп+1 Q2n Q211+2 Q2+1
1 Q,n+>Q2,t "
Значит, последовательность C.23) — возрастающая.
Точно так же из
следует, что последовательность C.24)—убывающая.
83

Всякий член последовательности C.24) больше
всякого члена последовательности C.23). Действи-
Действительно, рассмотрим числа
Ч2п	Ч2!П+\
и возьмем нечетное число k, большее как 2и, так и
2т + 1. Из C.12) вытекает, что
-	C-25)
§г it	C-26)
И	р
Сравнивая выражения C.25), C.26) и C.27), мы по-
получаем, что
а из возрастания C.23) и убывания C.24) —
>
Ч.п	Ч2т+\
т. е. любая четная подходящая дробь всегда меньше
любой нечетной.
На основании C.12) и C.13)
Qn+iQn n2
и потому при увеличении п разность (и+1)-й и и-й
подходящих дробей по абсолютной величине стре-
стремится к нулю.
Из всего сказанного можно заключить, что после-
последовательности C.23) и C.24) имеют один и тот же
предел, который, очевидно, является и пределом
C.22). Этот предел называется значением бесконеч-
бесконечной непрерывной дроби C.21).
В п. 2 была установлена единственность разложе-
разложения рационального числа в непрерывную дробь. Так
как проведенные при этом рассуждения никак не
опирались на конечность рассмотренных непрерыв-
непрерывных дробей, тем самым нами было доказано, что лю-
любое вещественное (а не только рациональное) число
может быть значением не более чем одной непрерыв-
непрерывной дроби.
84

Так как рациональное число всегда может быть разложено
в конечную непрерывную дробь, из только что сказанного сле-
следует, что оно не может быть разложено в бесконечную непрерыв-
непрерывную дробь. Следовательно, значение бесконечной непрерывной
дроби обязательно является иррациональным числом.
Теория разложений иррациональных чисел в непрерывные
дроби представляет собой глубокую по содержанию и интерес-
интересную по результатам ветвь теории чисел. Мы не будем здесь уг-
углубляться в эту теорию, а остановимся только на примерах,
связанных с числами Фибоначчи.
10. Найдем значение бесконечной непрерывной
дроби
1 +	Ц	.	C.28)
1+
По доказанному выше это значение есть lim <х„,
П -+ со
где ап = ""+'-. Вычислим этот предел.
Как уже было установлено в п. 20 § 1, ип есть
а"
ближайшее к —=• целое число; значит
V5
где I 9„ | < -j I каково бы ни было п.
Поэтому ввиду доказанного в п. 5
lim а„ = lim -^2±1_ \\т
an+1
4.0
= lim
en
а
Но 9rt+i V5 есть величина ограниченная (она по
абсолютной величине меньше двух), а а" при п,
стремящемся к бесконечности, неограниченно возра-
возрастает (потому что а > 1). Значит,
85

В силу тех же причин и
н мы получаем
lim а. = а.
¦п ¦
Значение непрерывной дроби C.28) можно вычислить и не
прибегая к формуле Бине и предельным переходам. (Нам в из-
известном смысле «достаточно» проведенного в п. 2 индуктивного
рассуждения, обслуживающего, очевидно, не только конечные не-
непрерывные дроби, но и их пределы — бесконечные дроби.)
Представим для этого дробь C.28) в виде
Очевидно, здесь выражение х само является непрерывной дробью
C.28), так что
,= 1 + 1,
откуда
хг — х — 1 = 0,	C.29)
и
Так как значение дроби C.28) является неотрицательным чис-
числом, оно должно равняться положительному корню уравнения
C.29), т. е. 	тг"—, а это и есть а.
Из доказанного следует, что отношение соседних
чисел Фибоначчи с ростом их номеров приближается
к а. Этим можно воспользоваться для приближенного
вычисления числа а (сравни вычисление ип в п. 20 § 1,
а также формулу A.35)). Ошибка при таком вычис-
вычислении получается маленькой, даже если мы возьмем
небольшие числа Фибоначчи. Например (с точностью
до пятого знака),
?10=41=1,6176,
а а = 1,6180. Ошибка, как мы видим, меньше 0,1%.
Между прочим, в отношении ошибок при прибли-
приближенном вычислении иррациональных чисел с помо-
помощью подходящих дробей и их разложений в непре-
86

рывные дроби число а представляет собой наихудший
случай. Всякое другое число описывается своими под-
подходящими дробями в некотором смысле более точно,
чем а. Остановимся более подробно на рассмотрении
этого круга вопросов.
11. Так как значение непрерывной дроби является
пределом последовательности подходящих к ней дро-
дробей, подходящие дроби должны приближаться к зна-
значению своей непрерывной дроби, и можно говорить
о скорости такого приближения. В сущности, речь
здесь идет о том, насколько точно можно описывать
вещественные числа рациональными дробями, знаме-
знаменатели которых не очень велики.
Приближения вещественного числа его подходя-
подходящими дробями являются наиболее точными в смысле
следующего утверждения.
Теорема Л е ж а и д р а. Пусть со — произвольное
число, а — — некоторая несократимая дробь. Предпо-
Предпоследнюю подходящую дробь при разложении — обо-
обозначим через ?~г.
Я
Тогда для того чтобы — была подходящей дробью
к со, необходимо и достаточно выполнение неравенства
.	C.30)
" я(я + я') '
Доказательство. Необходимость. Пусть
~я~~~Оп~' я' ~ Qn-i
соответственно и-я и п—1-я подходящие дроби к со.
Тогда, вводя в рассмотрение n-f-1-e полное частное
соп+1 (которое больше единицы), мы согласно C.17)
и C.7) имеем
Qn
— со
Рп	Рп®п+1 ~ Рп-1
- Чп-1
(PnQn - PnQn)
87

Достаточность. Пусть выполняется C.30). Вы-
Выберем число 0, для которого будет
Тогда в силу C.17) и C.7) мы получаем
рдО- рдО + pq' — р'д
q(qd+q') ^ q (q + q') '
так что 6 > 1. Тем самым мы оказываемся в условиях
леммы п. 5, согласно которой -- есть подходящая
дробь к со, а 0 — соответствующее полное частное.
12.	В обозначениях предыдущего пункта q' <. <?•
Поэтому если
С-оЬ".	C-32)
то — является подходящей дробью к со. Ясно вместе
с тем, что это условие не является необходимым для
того, чтобы дробь — была подходящей: не все подхо-
подходящие дроби числа со обладают свойством C.32). Вме-
Вместе с тем имеется «достаточно много» подходящих
дробей к со, которые неравенству C.32) удовлетво-
удовлетворяют. Точная формулировка этого содержится в сле-
следующей теореме.
13.	Теорема Валена. Если а — произвольное
число, то из двух подходящих дробей со с соседними
номерами хотя бы одна — удовлетворяет неравенству
?-@
q
Доказательство. Возьмем две соседние под-
ходящие дроби -г— и ,, и оценим сумму
чп	Чп+\
о
Qn
88
— со
1+1
C.33)

Замечая, что на основании рассуждений п. 9 стоящие
под знаками модуля числа должны быть разных знаков
и вспоминая, что произведение двух различных чисел
меньше половины суммы их квадратов, мы получаем
Рп	Рп+1
1 + 1
Q.fln
+i
Значит, хотя бы одно из составляющих s слагаемы/
должно быть меньше соответствующего слагаемого
в C.33) справа, т. е.,
Р
	СО
< —г или
t+i
— со
«Л+1
п+1
а это и требовалось.
14. Если мы заменим неравенство C.32) на еще
более сильное, увеличив в нем коэффициент при q1,
то у нас окажется еще меньше шансов получить удов-
удовлетворяющие ему подходящие дроби. Тем не менее
при умеренном увеличении этого коэффициента таких
возможностей будет еще довольно много.
Теорема Бореля. Если со — произвольное чис-
число, то из любых трех последовательных его подходя-
подходящих дробей хотя бы одна — удовлетворяет условию
^-	C.31)
Доказательство. Возьмем три последователь-
последовательные подходящие дроби к числу со:
Рп	Рп+1	"п + 2	/Q ОЕ\
~Q~' Q + ' Q +2 '	(о.оо)
Как было выяснено в C.31),
1	1
C.36)
Поэтому, обозначая для удобства л/5 через с, мы
можем, учитывая C.36), переписать C.34), как
89

или
Qn
Далее будем доказывать теорему от противного. Не*
соблюдение неравенства C.34) ни для одной из под*
ходящих дробей C.35) означает
«га+1 + -^ =S с,	C.37)
S с,	C.38)
S с.	C.39)
Однако
так что из C.37) следует
ИЛИ
L«*±«^ j ^ac. C.40)
+
Перемножая это неравенство почленно с C.38),
мы получаем
или, полагая
и вспоминая, что с = д/5 > мы имеем
90

т. е., для положительных t,
t2 — 3/ + 1 5S 0,
откуда
! Заметим, что верхняя граница для t оказывается
j равной а2. Ясно поэтому, что если (о„+2 > а, то
< а.	C.41)
Однако если (о„+2 > а, то из C.38) следует
так что
Qn+i = 2
» и
» 2	1
что противоречит C.41). Значит, оп+2 2= <*• Так как,
однако, величины (о„+2 и "+1 входят в неравенства
C.38) и C.39) равноправно, аналогичные рассужде-
рассуждения дают нам
; а.	C.42)
- Qn
По тем же соображениям из C.40) и C.39) выте-
вытекает, что
g a.	C.43)
Далее заметим, что
^л+2 tfn+2 I со -j- *
01

т. е.
Так как qn+2 — целое положительное число, отсюда
следует, что qn+2=l. Но тогда
Qn+2 — Qn+i + Qn.
и из C.43) следует
Qft+2 	 1 _| Qtl <-¦ _
"л	— ~т~ ~п	== w>
Vrt+I	Vrt+I
откуда
Qn = a— l ~~a"
Вместе с C.42) это дает нам
чего, однако, не может быть, так как дробь ¦ Л+1-
рациональна, а число а является иррациональным.
15. Устанавливаемые в теоремах Валена и Бореля
флкты могут создать впечатление, будто дальнейшее
\ величение коэффициента при q2 в формулах C.32) и
C.34) заставит лишь выбирать нужную подходящую
дробь — из более длинных серий подходящих дробей.
Это впечатление, однако, оказывается обманчивым,
В действительности вся картина меняется весьма
PL3KO.
Подчеркнем, что в последующих рассуждениях
число а уже не возникает попутно по ходу доказа-i
тельства, а становится вместе со своими подходящими
дробями тем примером, который определяет всю аь
тулцшо.	_
Теорема Гурвица. Если с>л/5, то сущест-
существуют числа со, для которых неравенство
выполняется лишь для конечного числа несократимых
дробей —.

(Согласно теореме Лежандра все такие дроби —
должны быть подходящими для числа со.)
Доказательство. В качестве числа ю можно
взять <х = -
-?¦ — < — < —
q	cql 2q2
Тогда по теореме п. 13 — должна быть подходящей
дробью к а. Положим — = 7FL и напишем снова,
как в C.36),
1
Кроме того, согласно C.16) в нашем случае (о„+| = а,
a Qn = un. Значит (в обозначениях п. 10)
Qn <*„_, '
1	1
причем 	 отличается от —- на некоторое е„, ста-
становящееся с ростом п сколь угодно малым.
Поэтому мы имеем
1	1
Таким образом, если взять с> V^i то при доста-
достаточно большом п будет с > V5 + е„, так что
— о
Значит, в условиях с > -т/5 неравенство C.44)
будет при со = а выполняться лишь для конечного
числа подходящих дробей с не очень большими но-
номерами.
93

Остается открытым вопрос о том, существуют ли
другие, отличные от а, числа ю, для которых нера-
неравенство C.44) выполняется лишь для конечного числа
подходящих дробей.
§ 4. ЧИСЛА ФИБОНАЧЧИ И ГЕОМЕТРИЯ
1. Разделим отрезок АВ единичной длины (рис. 2)
на две части так, чтобы большая из его частей явля-
являлась средним пропорциональным между меньшей его
частью и всем отрезком.
Рис. 2.
Обозначим для этого искомую длину большей ча-
части отрезка через х. Очевидно, длина его меньшей
части при этом будет равна 1-х, и условие нашей
задачи дает нам пропорцию
откуда	*2=1-х.	D.2)
Положительным корнем D.2) является ——~^-—,
так что отношения в пропорции D.1) равны
1 _	2	_	2 A + -у/5")	_ 1 + д/5" _
каждое. Такое деление (точкой Ci) называется деле-
делением в среднем и крайнем отношении. Его часто на-
называют также золотым делением или золотым се-
сечением.
Если взять отрицательный корень уравнения D.2),
то делящая точка Сг окажется вне отрезка АВ (такого
рода деление в геометрии называется внешним деле-
делением), как это видно из рис. 2. Легко показать, что
и здесь мы имеем дело с золотым сечением;
СгВ _ АВ _
АВ ~ С2А ~~ а>
94

2. Фактическое построение точки, делящей отре-
отрезок золотым сечением, осуществляется без труда.
С1	В
Рис. 3.
Пусть АВ = 1; восставим из точки А перпендику-i
ляр и возьмем точку Е, для которой АЕ — -^ (рис. 3).
Тогда
Проведя из Е, как из цент-
центра, дугу через А до пересече-
пересечения с ЕВ в точке D, мы полу-
получаем
Наконец, проведя через D
дугу с центром в В, мы нахо-	Рис
дим искомую точку С\. Точку
внешнего деления С2 можно най^и из условия АС2 —
= ВСХ.
3. Золотое сечение довольно часто встречается п
геометрии. Например, для квадрата, вписанного в по-
полукруг (см. рис. 4), точка С делит золотым сечением
отрезок АВ.
Сторона а\о правильного десятиугольника (рис. 5),
вписанного в круг радиуса R, как известно, равна
п~ ¦ 360°
т. е. 2R sin 18°.
Вычислим sin 18°. На основании известных формул тригоно-
тригонометрии
sin 36° = 2 sin 18° cos 18°,
cos 36°= 1 —2 sin2 18°,
95

sin 72° = 4 sin 18° cos 18° A — 2 sin2 18°).	A3)
Так как sin 72° = cos 18° Ф О, из D.3) следует, что
1 = 4 sin 18° A —2 sin2 18°),
и потому sin 18° является одним из корней уравнения
1 = 4лг A —2л:2),
или
8л:3 — 4* + 1 = 0.
Разложив левую часть последнего уравнения на множители, мы
получаем
B*	 1) Dл'2 + 2л:	 1) = 0,
откуда
_ 1 „ _-M-V5; 	— 1 — vs".
Так как sin 18° есть положительное число, отличное от тг»
имеем
.mur-y-
4	2а
Заметим для дальнейшего, что
U	1	1
cos 36° =1 - 2 sin2 18° =1 -2
4а2 ~ 2а2 ~ 2а2 ""
2 + 2а — 1 2а + 1 _ _сГ	_а_
2а2 ~ 2а2 ~~ 2а2 ~~ 2 *
Таким образом,
аш —^Л 4 —Л 2 — —.
Иными словами, а^ равно большей части радиуса
круга, разделенного золотым сечением.
Практически при вычислении аю можно вместо а
брать отношение соседних чисел Фибоначчи (см. п. 26
§ 1 или п. 10 § 3) и считать приближенно, что ою есть
о	к
-jjR или даже -^ R.
96	3

4. Рассмотрим правильный пятиугольник. Его диа-
диагонали образуют правильный звездчатый пятиуголь-
пятиугольник (рис. 6).
Рис 6.
Угол AFD равен 108°, а угол ADF равен 36°. Зна-
Значит, по теореме синусов
Так как очевидно, что AF = AC, должно быть
AD AD _
IF" 1С — а'
и точка С делит отрезок AD золотым сечением.
Но тогда, по определению золотого сечения,
АС _
СО ~~а-
Замечая, что АВ = CD, мы получаем
АС __ АВ _
АВ~ ВС ~ а#
Таким образом, среди отрезков
ВС, АВ, AC, AD
каждый последующий в а раз больше предыдущего.
Пусть читатель попутно проверит, что и
AD
4 Н, Н, Воробьев	97

5. Возьмем прямоугольник со сторонами а и b и
будем вписывать в него наибольшие возможные квад-
квадраты, как это показано на рис. 7.
а
Рис. 7.
Рассуждения п. 5 § 2 показывают, что такой про-
процесс в случае целых а и b соответствует алгорифму
Евклида, примененному к этим числам. Числа квадра-
квадратов одинаковых размеров равны при этом (п. 1 § 3)
соответствующим неполным
1
а
частным разложения т- в не-
непрерывную дробь.
Если разбивать так на квад-
квадраты прямоугольник, стороны
которого относятся как сосед-
Рис 8	ние числа Фибоначчи (рис. 8),
то на основании п. 5 § 3 все
квадраты, кроме двух самых маленьких, будут раз-
различными.
Так как стороны всех этих квадратов равны соот-
соответственно и\, «2	и„, их суммарная площадь, оче-
очевидно, равна
и\ + и\+ ... +и\.
Но это есть площадь разбиваемого нами прямоуголь-
прямоугольника, равная ипип+\-
Таким образом, при любом п
и\ + и\+ ... +< = «„«„+„
и мы получили новое, геометрическое доказательство
утверждения п. 4 § 1.
98

6. Пусть теперь отношение сторон прямоугольника
равно а. (Такие прямоугольники мы будем для крат-
краткости называть прямоугольниками золотого сечения.)
Докажем, что, вписав в прямо-
прямоугольник золотого сечения наи-
наибольший возможный квадрат
(рис. 9), мы снова получим пря-
прямоугольник золотого сечения.
В самом деле,
АВ
а;
AD	'
по условию AD = AE — EF, так как AEFD — квадрат.
Значит,
EF АВ — ЕВ
ЕВ	ЕВ
Но а2 — 1 = а, так что
= а2-1.
На рис. 10 показано, как прямоугольник золотого
сечения может быть «почти весь» исчерпан квадра-
квадратами /, //, ///, ... При этом
каждый раз после вписы-
вписывания очередного квадрата
и
т
I
ж
ш
Рис. 10.	Рис. 11.
будет оставаться фигура, являющаяся прямоуголь-
прямоугольником золотого сечения.
Пусть читатель сравнит эти рассуждения с пп. 5
и 9 предыдущего параграфа.
Заметим, что если в квадрат вписать прямоуголь-
прямоугольник золотого сечения / и квадраты // и ///, как это
показано на рис. 11, то оставшийся прямоугольник
4*	99

тоже окажется прямоугольником золотого сечения.
Доказательство предоставляется провести читателю.
7. По аналогии с прямоугольниками золотого се-
сечения можно говорить и о треугольниках золотого се-
сечения: остроугольном — с углами 36°, 72° и 72° и тупо-
тупоугольном— с углами 108°,
36° и 36°. На рис. 12 видно, как
остроугольный треугольник зо-
золотого сечения разбивается на
меньшие три треугольника зо-
золотого сечения, и обозначены
величины углов и отрезков.
8. Природа дает нам мно-
многочисленные примеры располо-
расположений однородных предметов,
описываемых числами Фибо-
Фибоначчи.
В разнообразных спирале-
спиралевидных расположениях мелких
частей растений обычно можно
усмотреть два семейства спи-
спиралей. В одном из этих се-
семейств спирали завиваются
по часовой стрелке, а в другом — против. Числа спи-
спиралей того и другого типов часто оказываются сосед-
соседними числами Фибоначчи.
Так, взяв молодую сосновую веточку, легко заме-
заметить, что хвоинки образуют две спирали, идущих
справа снизу налево вверх. Вместе с тем они же со-
составляют три спирали, идущие слева снизу направо
вверх.
На многих шишках семена (т. е. «чешуйки») рас-
расположены в трех спиралях, полого навивающихся на
стержень шишки. Они же расположены в пяти спира-
спиралях, круто навивающихся в противоположном направ-
направлении. В крупных шишках удается наблюдать 5 и 8 и
даже 8 и 13 спиралей. Хорошо заметны такие спирали
и на ананасе: обычно их бывает 8 и 13.
У многих сложноцветных (например, у маргаритки
или ромашки) заметно спиральное расположение от-
отдельных цветков в соцветиях-корзинках. Число спира-
спиралей бывает здесь 13 в одном направлении и 21 в
другом или даже соответственно 21 и 34. Особенно
100

много спиралей можно наблюдать в расположении
семечек крупного подсолнуха. Их число в каждом из
направлений может достигать соответственно 55 и 89.
9. Прямоугольники золотого сечения выглядят
«пропорционально» и приятны на вид. Вещами, имею-
имеющими такую форму, оказывается удобным пользо-
пользоваться. Поэтому многим «прямоугольным» предметам
j нашего обихода (книгам, спичечным коробкам, чемо-
' данам и т. п.) часто придается именно такая форма.
Например, данная книга имеет форму прямоуголь-
прямоугольника с отношением сторон 1,62, а заполненная текстом
| часть ее страницы — форму прямоугольника с отно-
i шением сторон 1,64.
I	Различными философами-идеалистами древности и
' средневековья внешняя красота прямоугольников зо-
i лотого сечения и других фигур, в которых наблю-
наблюдается деление в среднем и крайнем отношении, возво-
• дилась в эстетический и даже философский принцип.
! Золотым сечением и еще некоторыми числовыми
отношениями пытались не только описать, но и объ-
объяснить явления природы и даже общественной жизни,
I а с самим числом а и с его подходящими дробями
i производились разного рода мистические «операции».
' Разумеется, подобные «теории» ничего общего с нау-
' кой не имеют.
j	10. Числа Фибоначчи появляются также в вопро-
вопросах, связанных с исследованием путей в различных
Г	AC,	Cj	С„_,
в	сг	сп_г	сп
Рис. 13
геометрических конфигурациях. Рассмотрим, напри-
например, сеть путей, изображенную на рис. 13 (такие сети
в математике принято называть ориентированными
графами), и подсчитаем число путей, которыми мож-
можно, двигаясь вдоль стрелок, перейти из вершины А
или вершины В в вершину Ся.
101

г Обозначим числа таких путей соответственно через
ап и Ьп. Ясно, что при начале движения, как из точки
А, так и из точки В, в вершину С„ можно попасть
двумя способами: через вершину Сп-\ с последующим
шагом вдоль наклонного ребра и через вершину Сп-ч
с последующим шагом вдоль горизонтального ребра.
Значит,
Ьп = Ьп_х + Ьп_2.
Нам остается заметить, что ai = a2=l, и bi=l,
Ъ2 = 2, откуда сразу следует, что ап = ип и Ьп = ип+\.
11. Следующая задача будет касаться уже не под-
подсчета числа путей в ориентированном графе, а выбора
рациональных переходов по этим путям.
Рассмотрим следующую игру-состязание в ее тра»
диционной постановке, называемой «цзяньшицзы».:
Пусть имеются две кучи предметов (например, спичек),
и два игрока поочередно берут
У\У\У\У\У\У либо произвольное число предме-
предметов из одной кучи, либо поровну
из каждой кучи. Выигравшим счи-
считается тот, кто забирает послед-
последние предметы.
В более математизированной
форме эту игру можно предста--
с- •	вить себе, как имеющийся перед
игроками ориентированный граф,
изображенный на рис. 14. Будем считать, что граф рас-
расположен на координатной плоскости, и две целочислен-
целочисленные координаты каждой из его вершин соответствуют
числу предметов в первой и второй кучах (например,
жирная точка на рис. 14 имеет координаты E,3)).
Начальное положение игры может быть отмечено по-
помещением фишки в соответствующую вершину графа.
Процесс игры состоит в поочередном уменьшении
игроками одной из координат вершины на целое число
или обеих координат на одно и то же число, т. е. в
прямолинейном передвижении фишки вдоль одного из
указанных стрелками на рис. 14 направлений на лю-
любое расстояние. Ясно, что за конечное число ходов
фишка окажется передвинутой в начало координат
|(отмеченное на графе кружком), и игрок, поставив-
102

ший фишку в эту вершину, считается выигравшим.
Эту игру будем далее для краткости называть игрой
Г, а изображенный на рис. 14 граф — графом игры Г.
Вершина графа, в которой находится (или может на*
ходиться) фишка, вместе с указанием, какой игрок
имеет очередь хода, будет называться позицией игры.
Применительно к игре Г встает вопрос о тех вер-
вершинах графа (позициях игры), приходя в которые тот
или иной игрок имеет возможность форсировать выиг-
выигрыш (а его противник тем самым обречен на пора-
поражение). Примем следующую программу исследований
этого вопроса.
Во-первых, сформулируем достаточно точно поня-
понятие выигрывающей позиции для игры Г (а факти-
фактически и для всех игр такого типа).
Во-вторых, сформулируем некоторую схему описа-
описания множества всех выигрывающих позиций.
В-третьих, опишем выигрывающие позиции в тер-
терминах фибоначчиевых представлений (в
смысле п. 27 § 1) их координат.
Наконец, в-четвертых, мы перейдем от фибонач-
фибоначчиевых представлений координат выигрывающих по-
позиций к их явным описаниям посредством формул.
Приступим к выполнению этой программы.
12. Мы будем называть позицию выигрывающей,
если игрок, приведший в нее фишку, гарантирует себе
выигрыш, независимо от того, как будет вести себя
его противник.
Тривиальным примером выигрывающей позиции в
игре Г является вершина @,0). Игрок, приведший
фишку в эту позицию, уже выиграл, и никаких дей-
действий противника уже не последует.
Простым примером выигрывающей позиции яв-
является A,2). Противник может перейти от нее к од-
одной из позиций @,2), A,0) или @, 1). Во всех трех
случаях наш игрок от каждой из этих позиций может
перейти к @,0) и тем самым выиграть. В такой же
мере выигрывающей позицией будет и позиция B, 1).
Более обстоятельно, но не более трудно показы-
показывается, что C,5) и E,3) также суть выигрывающие
позиции.
Формально говоря, в приведенное в начале этого
пункта определение, а именно в оборот «независимо
103

от того, как будет вести себя его противник», вкра-
вкралось новое для нас понятие: «поведение» игрока.
Чтобы дальнейшие рассуждения имели смысл, нам
надлежит это понятие точно описать.
Представим себе для этого, что каждый из игро-
игроков, прежде чем сесть за игру, составил точный план
игры, т. е. наметил ход, который он будет делать в
этой позиции, как только он в эту позицию попадет.
Такой план принято называть стратегией игрока.
Стратегия игрока в игре Г есть таким образом функ-
функция, определенная на множестве всех позиций, при-
причем значением ее на данной позиции Р может быть
любая позиция, в которую можно из Р перейти. Как
только оба игрока выбрали свои стратегии, все раз-
развитие игры уже можно считать предопределенным, в
какой бы позиции фишка первоначально ни находи-
находилась: тот игрок, чья очередь хода, передвигает ее в
соответствии со своей стратегией в некоторую вполне
определенную позицию; но в новой позиции очередь
хода будет принадлежать другому игроку, который
согласно своей стратегии также должен будет сделать
вполне определенный ход; после этого снова насту-
наступит очередь первого игрока и т. д. В результате фиш-
фишка будет проходить по графу однозначно определен-
определенный путь.
Теперь мы можем уточнить понятие выигрываю-
выигрывающей позиции в игре Г: позиция называется выигры-
выигрывающей, если существует такая стратегия пришедшего
в нее игрока А, что какова бы ни была стратегия его
противника Б, игрок А приведет фишку в позицию
(О, 0).
Важно отметить, что достижение игроком выигры-
выигрывающей позиции еще ни в коей мере не дает ему
оснований играть «спустя рукава». Напротив, это озна-
означает лишь то, что для него существует некоторая
стратегия (ее естественно также назвать выигрываю-
выигрывающей), которую ему еще предстоит точно установить
и неукоснительно соблюдать.
Ясно, что выигрывающая стратегия должна после
каждого хода противника снова приводить игру в
одну из выигрывающих позиций. В противном случае,
если на каком-то ходе игрок придет не в выигрываю-
выигрывающую позицию, то у него не окажется выигрывающего
104

продолжения, а это противоречит предположению о
том, что выбранная им стратегия — выигрывающая.
Таким образом, мы начали с введения «единич-
«единичного» понятия выигрывающей позиции, но для точного
его определения приходится рассматривать и все
остальные выигрывающие позиции. Поэтому целесо-
целесообразно с самого начала говорить одновременно о
множестве всех выигрывающих позиций.
13. Рассмотрим некоторое множество позиций R
игры на графе Г (или на любом другом ориентиро-
ориентированном графе). Оно может обладать (или не обла-
обладать) следующими свойствами:
1°. Любой ход в позиции, принадлежащей R, вы-
выводит за пределы R. По некоторым довольно глубоким
причинам, в которые мы здесь не имеем возможности
вдаваться, это свойство множества позиций в игре
(и в графе) называется его внутренней устойчивостью.
2°. В любой позиции, не принадлежащей R, суще-
существует ход, приводящий в позицию из R. Это свойство
R называется его внешней устойчивостью.
Множества позиций в играх на ориентированных
графах, которые являются одновременно внутренне
и внешне устойчивыми, имеют большое значение в
играх, связанных с поочередными перемещениями по
вершинам графа. Такие множества называются реше-
решениями этих игр (а также решениями графов этих
игр). Если фишка в ходе игры оказывается в принад-
принадлежащей решению позиции, то игрок, чья очередь
хода, обречен все последующие ходы «пытаться уйти
из решения»: какой бы ход он ни сделал, по свойству
внутренней устойчивости он выведет фишку за пре-
пределы решения; но тогда по свойству внешней устой-
устойчивости его противник сумеет следующим ходом
фишку в решение вернуть.
В рассматриваемой нами игре Г всякая партия
заканчивается приведением фишки в начало коорди-
координат, и игрок, приведший ее туда, выигрывает. Значит,
если решение игры содержит начало координат, то
игрок, имеющий очередь хода в одной из принадле-
принадлежащих этому решению позиций, выигрывает. Следова-
Следовательно, это решение состоит из выигрывающих по-
позиций.
105

Все сказанное дает нам основание исследовать до-
достаточно подробно вопросы, касающиеся решений
игры, содержащих начало координат.
14.	Прежде всего установим единственность та-
кого решения.
Лемма. Для игры Г существует не более одного
решения, содержащего начало координат.
Доказательство. Предположим, что, вопреки
утверждению леммы, имеется два таких решения, R
L S, причем некоторая позиция Sj из 5 не принадле-
жит R. По внешней устойчивости R из позиции Si
можно перейти в некоторую позицию т\ из R. Но по
внутренней устойчивости S позиция г\ не может при-
принадлежать. S. Значит, по внешней устойчивости 5 мы
можем из г\ перейти в некоторую позицию s-i из S,
которая (в силу внутренней устойчивости R) не мо-
может принадлежать R. Повторяя этот процесс доста»
точно долго, мы получим последовательность позиций
S\, T\, Si, r2, ..., которая заканчивается началом ко-
координат и в которой каждая позиция принадлежит
лишь одному из решений R или S. Значит, и начало
координат должно принадлежать только R или только
S, и мы получили противоречие.
15.	Определяющее, «характеристическое» свойство
решения игры R, содержащего начало координат,
описывается следующей теоремой.
Теорема. Пусть R — множество позиций в игре
Г, которое обладает следующими свойствами:
1)	позиция @,0) принадлежит R;
2)	если (а, Ъ) принадлежит R, то и (Ь, а)' принад-
принадлежит R;
3)	для всякого натурального а найдется ровно
одно натуральное Ь, для которого (а, Ь) принадле-
принадлежит R;
4)	для всякого натурального d найдется ровно
одна пара чисел (а,Ь) из R, для которой а — Ъ = d;
5)	если позиции (а, Ъ) и (k, l) принадлежат R,
причем a<.b, k<.l и Ъ — а < I — k, то а <. k и
Ь<1.
Тогда множество R является решением игры Г.
Доказательство. Заметим сначала, что, как
следует из 3), каждое натуральное число является
106

координатой ровно в одной симметричной паре (свой-
(свойство 2)) позиций из R.
Перейдем к установлению свойств внутренней и
внешней устойчивости множества R.
а)	Внутренняя устойчивость. Пусть (а, Ь)
принадлежит R. Если уменьшить а или Ь, то возни-
возникает пара, сочетающая с Ь (соответственно с а)
другое число, и потому по 3) не принадлежащая R.
Если же уменьшить одновременно и одинаково а и Ъ,
то получится отличающаяся от (а, Ь) пара с той же
разностью координат и не могущая поэтому в силу 4)
принадлежать R.
б)	Внешняя устойчивость. Пусть (а, Ь) не
принадлежит R.
Если а = Ь, то от этой вершины можно перейти к
вершине @,0), которая по 1) принадлежит R.
Если афЪ, то по 3) найдется такое с, что (а, с)
' принадлежит R, а по 4) найдутся такие k и /, что
/ — k = b — а и (k, l) принадлежит R. Тогда при
с<6 от (а, Ь) можно перейти к (а, с), уменьшив
Ъ, а при с>Ь имеет место с — а> Ь — a = l — k,
! так что по 5) должно быть с > I и а > k, и умень-
I шение каждой из координат позиции (а, Ь) на
a~k = b — / дает нам позицию (k, I).
Двойная устойчивость установлена, и R оказы-
| вается решением.
,	16. Теперь нетрудно построить некоторый развер-
i тывающийся (а по сути дела — рекуррентный) про-
! цесс, порождающий позиции из решения R игры Г,
содержащего @, 0).
Начнем с позиции @,0), а затем, уже выписав
набор позиций
(аь bi), ..., (ап, Ьп),
,	@, 0),	D.4)
i	(blt ах), ..., (Ьп, ап),
1 где ui<.bi для i= 1	п, положим an+i равным
I наименьшему из чисел, не участвовавших в наборах
1 4)&	(+1)
)
Фактически этот процесс приводит к системе по-
зиций
A,2), C,5), D,7), F, 10), (8, 13), (9, 15), ...
@, 0),
B,1), E,3), G,4), A0,6), A3,8), A5,9), ...
107

Позиции, составляющие это множество, расположены
«почти» на двух лучах, как это видно из рис. 15.
Непосредственно из описанного построения видно,
что полученная система позиций удовлетворяет усло-
условиям 1)—5) из доказанной в предыдущем пункте
теоремы. Следовательно, она является решением
игры, а в соответствии с п. 14 — и единственным
решением. Заметим, что игра Г имеет еще решения, не
содержащие позиции @,0). Однако это обстоятель-
обстоятельство нас интересовать не будет.
В принципе поставленная нами задача отыскания
решения игры Г тем самым решена. Однако множест-
множество R, хотя и определено у нас
однозначно, но имеет плохо
обозримый вид. Изобразим его
иначе.
17. Пусть, как в п. 27 § 1,
Ф@ обозначает фибоначчиево
представление натурального
числа t. Можно считать, что
последними фибоначчиевыми
-	—— цифрами представления каж-
каждого из чисел является неко-
Рис. 15.	торое количество нулей (если
этих нулей нет, то их число,
очевидно, равно нулю). Разделим все целые положи-
положительные числа на два класса: имеющие в конце своего
фибоначчиевого представления четное или нечетное
чичло нулей. Очевидно, каждое число из второго клас-
класса может быть получено ровно из одного числа пер-
первого класса приписыванием к его фибоначчиеву пред-
представлению одного нуля справа. Тем самым натураль-
натуральные числа объединяются в пары. Покажем, что мно-
множество всех таких пар {а, Ь) (и симметричных им
пар (Ь,а)) вместе с парой @,0) удовлетворяют усло-
условиям теоремы из п. 15 и тем самым образуют решение
игры Г.
Условия 1)—3) выполняются очевидным образом.
Рассмотрим разности сконструированных нами пар
н покажем, что каждое значение разности d встре-
встречается ровно один раз. Далее, пользуясь фибоначчие-
фибоначчиевыми представлениями чисел, мы будем для удобства
нумеровать фибойаччиевы цифры от низших разрядов
103

к высшим, т. е. записывать фибоначчиево представ-
представление числа в виде фпфп_1 ... ф2 (где, естественно, ф2
есть коэффициент при м2).
Если фибоначчиево представление
Ф (d) = фг ... ф2	D.5)
оканчивается нечетным числом нулей, то возьмем а
и & с фибоначчиевыми представлениями
Ф(а) = <р, ... <fcO,
ф (Ь) = Ф, ... ф200.	( '
Мы имеем
Ь — а = (%щ+2 + ... + ф2м4) — (ф*"г+1 + ... + Ф2"з) =
= Фг(«г+2 — «л-0 + ••• +Ф2( — «з) =
= фгИ, + • • • + Ф2«2 = d.
Если же Ф(й) оканчивается четным числом нулей:
Ф2 = фз = ••• =ф2т+1 = 0 И ф2т+2=1(т^ 1), ТО
возьмем
а = % ... ф2т+з0101 ... 01,
т + 1 раз по 0]	D.7)
Ь = % ... Ф2т+з0Ю1 ... 010,
и подсчитаем
Ъ — а = ф,Иг+2+ ... + ф2т+зт+5 + «2т+3 + ••• + Щ~
«2т + 1+ ... + «1.
или, воспользовавшись формулой A.2),
Ь — а = (PiUt + • • • + Ф2т + Зт + 3 + т+2 = d.
Проверим единственность пары с заданной разно-i
стью d.
Если Ф(^) имеет в конце нечетное число нулей, то
при другой паре {а, Ь) и фибоначчиевы представле-
представления этих чисел D.6) были бы иными; но тогда и
Ф(й) было бы иным, а в силу единственности фибо-
наччиева представления иным было бы и d.
Случай, когда Ф(^) имеет в конце четное число
нулей, по существу, столь же прост, хотя и требует
для своего анализа некоторых подсчетов,
109

Пусть представление
Ф (d) = \ik ... \i2
оканчивается ровно 1т нулями:
Ц2=: ••• ==^2m+l~0, V-2m+2~l> H>2m+3 —0,
и мы имеем
d=VkUk+ ••• + И2т+4«2т+4 + «2т+2-	D-8)
Представим d в виде разности & — а, где Ф(а)
имеет в конце четное число нулей, а Ф(&) получается
из Ф(а) путем приписывания к Ф(а) еще одного
нуля справа.
Пусть
+ Фг-1"/+ ••• + Фз«4 + Ф2«з-
Тогда
d = b — a = ф(Мг_1 + Ф/_1«:_2 + ... + Фз«2 + Фг«1- D.9)
Если при этом ф2 = 0, то ф/фг-i ... фз является
фибоначчиевым представлением d, и по единственно^
сти такого представления его цифры должны совпа-
совпадать с цифрами из D.8). В том числе должно быть
Ф2 = Фз = • • • — ф2т+2 — 0, Фгт+Я = 1.
т. е. фибоначчиево представление числа а оканчи-
оканчивается нечетным числом нулей, что противоречит вы-
выбору чисел а и Ъ. Значит, ф2 = 1. Но тогда
d— 1=фгМг_1 + Фг-1«(-2+ ••• +ФЗ«2
и
Ф(<*—1) = Ф,Ф,_1 ... Фз,	D.10)
а с другой стороны, из D.8) следует, что
= РкЦк + • • • + И2т+4«2т+4 + «2т+ 1 + «2т-1 + • • • + «3,
так что
... 010.
В силу единственности фибоначчиева представления
вместе с D.10) это дает
k l 1	== ф2т+5>	О
=Фз=
ф2т+2 = Ф2т = • • • = Ф4 = 1
110

Кроме того, как уже указывалось, ф2 = 1. Следова«
тельно, а, а потому и Ь, обязаны иметь вид из фор-
формулы D.7).
Это значит, что соблюдается условие 4).
Наконец, ясно, что в условиях выполненного по-
построения с ростом разности координат позиции долж-
должны возрастать и сами координаты. Это значит, что
выполняется 5).
Таким образом, построенная система пар чисел
является решением игры Г, содержащим @,0). Ввиду
доказанной единственности такого решения она долж-
должна совпадать с результатом построения из п. 16.
Фибоначчиевы представления чисел позволяют для
каждого натурального числа непосредственно указы-
указывать «парное» ему. Найдем, например, «пару» к
числу 31. Для этого числа мы имеем ФC1)= 1010010.
Полученное представление оканчивается одним нулем.
Значит, представление, парное к нему, получается в
результате отбрасывания последнего нуля, т. е. будет
101001; оно является фибоначчиевым представлением
числа 13 + 5+ 1 = 19.
18. Попытаемся изгнать из описания полученного
решения игры Г последние заключенные в фибонач-
чиевых представлениях остатки рекуррентности. Как
естественно ожидать (см., например, вывод формулы
Бине в п. 16 § 1), это будет связано с использованием
1 + V5"
числа а =	^—.
Предварительно докажем вспомогательную лемму,
значение которой выходит за пределы рассматривае-
рассматриваемого нами сейчас вопроса.
Лемма. Пусть у и б — положительные иррацио-
иррациональные числа, для которых
7 + i^1-	DЛ1>
Тогда среди чисел
ап = [пу], л=1,2, ....
Ьп = [п6], л=1, 2, ...	{ '
(где квадратные скобки означают целую часть с'гоя-
щих внутри них чисел) любое натуральное число
встретится ровно по разу.
11/

Доказательство. Заметим прежде всего, что
Y, б> 1. Возьмем далее произвольное натуральное N
и рассмотрим все натуральные значения п, для кото*
рых [пу] < N, т. е. пу < N, или п < -—, так что этому
неравенству удовлетворяют все натуральные числа
«-'¦>	Ж-
Аналогично для всех п=1, 2, ..., Г-yj будет
[пЬ] < N. Значит, среди чисел 1,2	N будет всего
Г—1 + |~3" 1 чисел вида 4.12). Но числа — и -у не
являются целыми. Значит,
Поэтому, складывая эти неравенства и учитывая D.11),
мы получаем
Значит, средняя часть написанного соотношения есть
целое число, лежащее строго между N — 2 и N. Таким
числом является N— 1:
Таким образом, для любого натурального N среди
чисел, меньших N, будет ровно N — 1 чисел вида
D.12): ими будут все натуральные числа, меньше N.
Нам остается сослаться на произвольность числа N.
19. Пары чисел ([пу], [пу]) удовлетворяют усло-
условиям 1)—3) теоремы п. 15. Чтобы они удовлетворяли
также условиям 4) и 5) этой теоремы, нужно, чтобы
при любом натуральном п было
Но так как
п = п + [пу] — [пу] = [п + пу] — [пу] = [и A + y)] — [пу],
это равносильно тому, чтобы при любом п было
112	4

[n6] = [rt(l + у)]. Но, как легко проверить, последнее
возможно лишь при б = 1 + Y> т- е- ввиду D.11) —
при
1 о-—!——1
откуда
2Y + 1=Y(Y+1),
или
Y2 — Y — 1 = 0,
так что ввиду положительности y —
Y = —
Таким образом, координаты выигрывающих по-
позиций в игре Г поддаются непосредственному вычи-
вычислению как пары
20. Закончим наше изложение небольшой геомет-
геометрической шуткой. Сейчас мы наглядно «докажем»,
что 64=65. Возьмем для этого квадрат со стороной 8
I
/-
Рис. 16.	Рис. 17.
и разрежем его на четыре части, как это показано на
рис. 16. Эти части мы сложим в прямоугольник
(рис. 17) со сторонами 13 и 5, т. е. с площадью, рав-
равной 65.
Объяснение этому, на первый взгляд загадочному,
явлению найти нетрудно. Все дело в том, что точки
5 Н. Н. Воробьев	113

А, В, С и D на рис. 17 на самом деле не лежат на
одной прямой, а являются вершинами параллело-
параллелограмма, площадь которого как раз и равна «лишней»
единице.
Это правдоподобное, но неверное «доказательство»
заведомо ложного высказывания (такие «доказатель-
«доказательства» называются софизмами), можно проделать еще
более наглядно и «убедительно», если вместо квад-
квадрата со стороной 8 взять квадрат со стороной, равной
некоторому числу Фибоначчи с достаточно большим
четным номером, и2п. Разобьем этот квадрат на части
(рис. 18) и сложим из этих частей прямоугольник
Рис. 18.	Рис. 19.
(рис. 19). «Пустота» в виде параллелограмма, вытя-
вытянутого вдоль диагонали прямоугольника, на основа-
основании п. 9 § 1 имеет площадь, равную единице. Наи-
Наибольшая ширина этой щели, т. е. высота параллело-
параллелограмма, равна, как легко вычислить,
V
«4 + Ап-2
Поэтому если мы возьмем квадрат со стороной
21 см и «превратим» его в прямоугольник со сторо-
сторонами 34 и 13 см, то наибольшая ширина щели полу-
получится
см,
т. е. около 0,4 мм, что почти незаметно для глаза.
114

§ 5. ЧИСЛА ФИБОНАЧЧИ И ТЕОРИЯ ПОИСКА
1. Известно, что при очень малых скоростях авто-
автомобиль расходует на каждый километр пути сравни-
сравнительно много бензина. Велик его расход и на боль-
больших скоростях. Какая-то промежуточная скорость
является при этом «оптимальной»: при передвижении
с этой скоростью автомобиль расходует на километр
пути наименьшее количество горючего. Таким обра-
образом, мы можем предполагать, что примерный график
зависимости расхода автомобилем горючего на кило-
километр пути от скорости автомобиля имеет вид, изобра-
изображенный на рис. 20: сначала, по мере роста скорости,
километровый расход горючего убывает до некото-
некоторой минимальной величины, а потом, с дальнейшим
ростом скорости, начинает неуклонно (как принято
говорить в математике, «монотонно») возрастать.
Хотя общие очертания графика этой зависимости
(сначала спуск, а потом подъем) одинаковы практи-
практически для всех автомобилей, его точная форма может
несколько изменяться даже в пределах автомобилей
одного типа, завися от индивидуальных особенностей
машины, от степени изно-
износа тех или иных ее меха-
механизмов и устройств и т. д. ^
В частности, и минимум |
на нашем графике также |.
может располагаться в
довольно широких пре- |
делах.	^
Предположим теперь,
ЧТО МЫ ПОЛУЧИЛИ В СВОе
распоряжение автомаши-
автомашину И хотим предпринять	Рис. 20.
путешествие по такой
местности, где в пути не удастся заправиться топли-
топливом. Для того чтобы иметь возможность проехать наи-
наибольшее расстояние, мы должны достаточно точно
определить скорость, соответствующую минимальному
расходу горючего. Эта скорость обычно называется
наиболее экономичной скоростью.
Определять наиболее экономичную скорость авто-
автомобиля естественнее всего опытным путем, проезжая
5*	115

с различными скоростями километровые участки до-
дороги, характер и качество которой типичны для усло-
условий предстоящего путешествия, и замеряя каждый раз
расход бензина. Так как это занятие не из веселых,
естественно задуматься над следующими вопросами:
сколько опытов достаточно поставить для того, чтобы
определить наиболее экономичную скорость автомо-
автомобиля с заданной точностью? На каких скоростях сле-
следует определять в этих опытах расходы горючего?
Близкими к этим вопросам являются следующие два:
как организовать данное число опытов, чтобы найти
экономичную скорость с наибольшей точностью? Ка-
Какова эта наибольшая точность?
При этом под определением наиболее экономичной
скорости «с точностью до данного е» мы будем пони-
понимать указание такой скорости v, что истинное значе-
значение наиболее экономичной скорости лежит между
v — е и v + е (т. е. что ошибка в определении этой
скорости не может превосходить е).
Для определенности будем считать заранее из-
известным, что наиболее экономичная скорость нашего
автомобиля лежит между некоторыми пределами v'
и v". В качестве v' следует взять скорость, которая
заведомо не превосходит наиболее экономичной, а в
качестве v" — такую скорость, которая заведомо не
меньше ее. (Например, в качестве v' можно взять
наименьшую скорость, при которой еще возможна
устойчивая работа мотора, а в качестве v" — макси-
максимальную скорость данного автомобиля.)
2. Отвлекаясь от описанного только что конкрет-
конкретного примера, рассмотрим следующую математиче-
математическую задачу.
Пусть нам о функции f(x) известно только то, что
она от заданного х' до некоторого неизвестного х убы-
убывает, а от этого х до заданного х" возрастает
(рис. 21). В частности, мы допускаем, что неизвестная
точка х в действительности совпадает с одним из
концов отрезка, х' или х". Очевидно, в этом случае
функция будет все время возрастать (рис. 22) или
все время убывать (рис. 23). Разумеется, если один
из последних двух случаев и имеет место, то мы будем
предполагать это обстоятельство заранее не извест-
известным. В точке х функция / принимает свое наименьшее
116

значение f(x), которое называется ее «минимальным»
значением или, короче, минимумом. О точке х обычно
в таких случаях говорят, что на ней функция дости-
достигает минимума. Ее также часто называют «миними-
«минимизирующей-» точкой функции.
Рис. 21.	Рис. 22.
Итак, мы далее будем рассматривать только такие
функции, в которых убывание не может следовать
за возрастанием. Такие функции мы будем в дальней-
дальнейшем для краткости назы-
называть «функциями с одним
минимумом».
Содержание данного
параграфа состоит в том,
чтобы проанализировать
возможности точного оп-
определения положения ми-
минимизирующей	точки
функции f с одним мини-
минимумом. То, что функция f	рис 23
является функцией с од-
одним минимумом, мы далее будем все время предпола-
предполагать, не оговаривая каждый раз. Совершенно ясно,
что с соответствующими изменениями все то, что мы
далее будем говорить о минимумах (наименьших
значениях) функций, справедливо и для их максиму-
максимумов (наибольших значений).
3. В поставленной проблеме, как и в широком
круге аналогичных ей проблем, участвуют три фак-
фактора: цели, которые мы перед собой ставим, возмож-
117

ности, которыми мы располагаем для осуществления
этих целей, и, наконец, те условия, в которых мы ис-
используем наши возможности для достижения целей.
В нашем случае цель состоит в повышении точ-
точности определения минимизирующей точки, т. е. в
уменьшении ошибки, с которой указывается эта
точка.
Возможности состоят в точном определении тем
или иным путем (вычислением, измерением или, на
худой конец, простым угадыванием) некоторого числа
значений функции / в произвольно выбираемых нами
точках и в сравнениях между собой найденных в раз-
различных точках значений по их величине.
Наконец, условия определяются величиной области
задания функции /, т. е. длиной L отрезка между
*' и х".
В соответствии со сказанным каждая конкретная
задача поиска может иметь три аспекта.
1)	Насколько осуществима поставленная цель при
данных возможностях и в данных условиях? Приме-
Применительно к интересующему нас вопросу это означает
следующее.
Пусть мы имеем право совершить п последователь-
последовательных определений значения f, выбирая каждый раз
точку определения по своему усмотрению. В каких
точках следует определять значения функции, чтобы
точка х определилась с наибольшей точностью, и ка-
какова эта точность?
2)	Какими возможностями необходимо распола-
располагать, чтобы осуществить поставленную цель в данных
условиях?
В нашей задаче этот вопрос можно конкретизиро-
конкретизировать так. Пусть мы хотим определить минимизирую-
минимизирующую функцию f точку х с заданной точностью е, т. е.
указать такое х, что х расположено между х — е и
х + е. Сколько определений значений функции f для
этого необходимо произвести и как эти определения
организовать?
3)	В каких условиях данные возможности доста-
достаточны для достижения поставленной цели?
В данном случае речь идет о нахождении наиболь-
наибольшего интервала L изменения функции / (т. е. наиболь-
наибольшего значения разности х" — х'), для которого суще-
118

ствует способ определения минимизирующей / точки
с заданной точностью е за п наблюдений.
4.	Строго говоря, нам придется сейчас иметь дело
не с одной задачей, а с двумя.
Во-первых, речь может идти о нахождении мини-
минимизирующей точки х вместе с тем значением f(x),
которое функция в этой точке принимает.
Во-вторых, мы можем интересоваться только самой
точкой х, оставаясь равнодушным к значению f{x).
Совершенно ясно, что в первой из этих задач
(будем далее ее называть задачей А) наши цели
шире, чем во второй (которую мы назовем задачей Б).
Поэтому естественно ожидать:
что при заданных возможностях и условиях цели
задачи А удастся осуществить в меньшей степени, чем
цели задачи Б (при данном числе п и длине L в за-
задаче Б удается получить меньшее б, чем в задаче А);
что для осуществления в равной мере целей обеих
задач при одинаковых условиях в задаче А необхо-
необходимы большие возможности (при одной и той же по-
погрешности е и одинаковых длинах L интервалов изме-
изменения функции в задаче А необходимо, вообще го-
говоря, большее п);
что одинаковое осуществление целей при равных
возможностях требует в задаче А более легких усло-
условий (данные е и п в задаче
А совместимы лишь с мень-
меньшими значениями L, чем в за-
задаче Б).
5.	Чтобы сделать сформули-
сформулированные задачи математиче-
математически вполне четкими, необхо-
необходимо разъяснить следующее
важное обстоятельство.
Допустим, что мы интере-
интересуемся возможностями опреде-	л-s хх
ления минимизирующей точки
х в отрезке длины L (очевид-	Рис. 24.
но, мы можем считать нача-
началом этого отрезка точку 0 на оси координат, а кон-
концом — точку L) с точностью е. Будем считать, что мы
решаем задачу А, т. е. что х интересует нас вместе со
значением f{x).
119

Предположим, что мы избрали следующий способ
определения х.
Выберем совершенно произвольно некоторое х
между 0 и L и определим значения функции f в точ-
точках х — е, х и х -\- е, т. е. вычислим величины
f(x-e), f(x), fix + г)
(рис. 24). Разумеется, при всей произвольности вы-
выбора х мы считаем, что все-таки х—е 5г 0, так что
значение функции f(x — е) можно фактически вы-
вычислить; точно так же мы принимаем, что jt + egL.
Вполне может случиться, что
f(x-B)>f(x)<f(x + e).
Это значит, что функция f, убывающая в х — е, при
переходе к х + е начинает возрастать. Но переход от
убывания функции к возрастанию неизбежно связан
с се прохождением через наименьшее значение. В дан-
данном случае это наименьшее значение функции f долж-
должно достигаться на некотором
х, лежащем между х — е и
х + е.
Поэтому х будет отстоять
от х не более, чем на е, и х
окажется как раз тем прибли-
приближенным значением х, которое
мы ищем. В этом случае опре-
определение искомого х осуществ-
осуществляется в результате всего-на-
всего-навсего трех наблюдений. Такое,
повторяем, может случиться.
Однако никакой гарантии того,
что это действительно произой-
Рис. 25.	дет, мы не имеем. Более того,
если длина L отрезка велика,
а е мало, то наступление этого явления может пока-
показаться довольно неожиданным. Наоборот, в этом слу-
случае вполне правдоподобно, что вблизи трех выбран-
выбранных нами точек функция f будет принимать сравни-
сравнительно большие значения, а минимума своего она
будет достигать где-нибудь совсем в другом месте.
Следовательно, трех наблюдений может хватить, а
может и не хватить.
120

Нам же нужен план действий, неизбежно приводя-
приводящий к определению х с точностью до е, где бы в дей-
действительности эта точка х ни лежала. Такие планы
существуют. Будем, например, систематически вы-
вычислять значения нашей функции
/@), f(e), fBe), ...	E.1)
до тех пор, пока не дойдем до такого f(re), что
(г+ 1)е будет больше, чем L (рис. 25). Ясно, что то
ke, для которого значение функции будет наименьшим
в последовательности E.1), и окажется искомым.
Смысл решаемых нами задач состоит в том, что
мы хотим составить не просто план действий, дающий
во всех и в том числе в наименее благоприятных
случаях жизни значение х с предписанной точностью,
а наиболее экономичный из таких планов, т. е. план,
«наилучший в наихудших условиях». Но наихудшими
условиями являются те, в которых число вычисляемых
значений функции / максимально. Аналогично наибо-
наиболее экономичным планом является такой план, кото-
который осуществляет поставленную цель с минимальным
числом вычислений значений функции.
Поэтому наилучший в наихудших условиях план
часто называют минимаксимальным планом, или пла-
планом минимакса. Мы будем этот план называть опти-
оптимальным.
Сущность действий, предписываемых оптимальным
планом (как в этой, так и в любой аналогичной за-
задаче), можно охарактеризовать как наиболее целе-
целесообразные поиски «прячущегося» от пас минимума
функции, «стремящегося оказаться как раз не там, где
мы его ищем». Сказанное не имеет ничего общего ни
с мистикой, ни с суевериями, а является лишь харак-
характеристикой тех наихудших обстоятельств, примени-
применительно к которым мы и квалифицируем наши дей-
действия как наилучшие.
6. Важно отметить, что не для всякой задачи
поиска существуют оптимальные планы. Так, напри-
например, в задаче Б оптимального плана нет.
В самом деле, пусть L = 2 и п = 2. Какую точ-
точность определения е мы можем при этом гаранти-
гарантировать?
121

будем считать концами нашего отрезка числа 0 и
2. Возьмем произвольно малое положительное е и
вычислим значения функции / в точках 1 —ей 1 + е.
Если при этом
то искомый минимум х должен лежать между нулем
и 1 + 8, а если
то х расположено между 1 —е и 2.
Положим в первом случае
Х__ 1 + 8
а во втором —
	 A — е) + 2 	 3-е
В наихудшем случае так определяемое х отли-
отличается от истинного минимума функции / на —"—-.
Приближая е к нулю, мы уменьшаем ошибку. Од-
Однако е не может обратиться в нуль (ибо тогда точки
1—е и 1 + е совпадут, и сравнение значения функ-
функции /A—е) с заведомо равным ему значением
/A + е), вычисленным в той же точке, не даст нам
никакой информации). Поэтому погрешность всегда
остается большей, чем половина, хотя и может быть
сделана сколь угодно близкой к этому числу.
Каждое положительное значение е определяет
здесь некоторый план. Чем ближе е к нулю, тем этот
план лучше. Так как для любого е > 0 найдется еще
меньшее положительное число, для любого плана най-
найдется еще лучший. Следовательно, оптимального
плана для задачи 5 нет.
Однако для задачи 5 существуют «почти опти-
оптимальные» планы, приводящие к таким результатам,
которые можно улучшить лишь незначительно. Го-
Говоря точнее, каково бы ни было число у > 0, суще-
существует такой план Ру, что никакой другой план не
сможет уменьшить даваемую планом Ру ошибку
больше, чем на у.
7. План, описываемый последовательностью E.1)
при е, достаточно малом по сравнению с длиной L
рассматриваемого нами отрезка, оптимальным не яв-
122

ляется. Придерживаясь этого плана, нам придется в
наихудших условиях выполнить все г вычислений.
Попробуем, однако, поступить несколько иначе.
Будем вычислять члены последовательности E.1) че-
через один:
f@), fBe), fDe), ...;
найдем в полученной последовательности наименьший
из членов (пусть им будет fBka)) и вычислим два
значения функции f(Bk—1)е) и f (Bk-\- I)г). То из
трех значений переменной Bk—1)е, 2кг и B&+1)е,
при котором значение функции f будет наименьшим
из трех
очевидно, и есть х с точностью до е. Этот новый план
приводит в наихудших условиях к цели после выпол-
выполнения примерно ^ +2 вычислений. При больших г
это существенно меньше, чем число вычислений, тре-
требуемых первым планом.
Итак, первый план не является оптимальным. По
сходным причинам второй план также нельзя, вообще
говоря, считать оптимальным.
Однако второй план отличается от первого одной
весьма существенной чертой: предусматриваемые им
точки определения значений функции планируются за-
заранее лишь частично, а выбор оставшихся точек осу-
осуществляется на основе сравнений уже вычисленных
значений функции. Интуитивно совершенно ясно, что
выбор наилучших действий всегда должен быть свя-
связан с использованием информации о результатах дей-
действий, которые мы уже произвели. Второй план яв-
является в этом отношении более совершенным, чем
первый. Но и он, вообще говоря, поддается дальней-
дальнейшим усовершенствованиям, которые в конце концов
приведут нас к оптимальному плану.
Естественно в процессе определения местонахож-
местонахождения минимума функции сравнивать каждое вновь
получаемое значение функции с теми или иными из ее
значений, полученных при предыдущих наблюде-
наблюдениях. Выбор точки, в которой будет производиться
следующее измерение (или решение о прекращении
дальнейших измерений), будет поэтому как-то зави-
123

сеть, во-первых, от тех точек, в которых значения
функции нами вычислены, а во-вторых, от самих вы-
вычисленных значений функции.
Очевидно, такой процесс последовательного вычисления зна-
значений функции f вполне определяется некоторым законом, ставя-
ставящим в соответствие для любого ййО произвольным наборам
точек Х{, х2, ¦.., Хц и значений функции f в этих точках ту или
иную точку Xk+i или же решение закончить наблюдения над
функцией /, приняв ту или иную точку в качестве х. Этот закон
соответствия принято называть решающей функцией.
Каждый план определяет некоторую решающую функцию.
Точно так же и всякая решающая функция определяет некото-
некоторый план. В сущности, решающая функция — это и есть четкое
и формализованное описание плана. Например, решающая функ-
функция, определяющая первый из рассмотренных в предыдущем
пункте планов, ставит в соответствие каждому числу 0 :? k < г
точку (k + 1)е, а числу г — окончание процесса.
Понятие решающей функции принадлежит к числу важней-
важнейших понятий современной математики. К сожалению, точное оп-
определение этого понятия довольно громоздко и не может быть
здесь приведено.
8. Пусть цель плана Р состоит в определении с
наименьшей погрешностью точки х, минимизирующей
функцию / на отрезке длины L на основе п наблюде-
наблюдений. Такой план мы далее будем называть п-шаговым.
Пусть в условиях некоторого «-шагового плана Р
удается определить х на отрезке длины L с точностью
до е. Эта точность зависит от самого плана Р, а также
от п и от L. Поэтому мы можем считать ее функцией
от Р, п и L и обозначать для задачи А через Тр(п, L),
а для задачи 5 — через Хр(п, L). Под хР(п, L) далее
будет подниматься любое (но, конечно, в пределах
одного рассуждения одно и то же) из выражений
т^ (п, L) и т« (п, L).
/г-шагопый план Ро определения минимума / на
отрезке длины L является оптимальным в задаче Л,
если т^ (п, L) не более, чем т^ (п, L) для любого дру-
другого плана Р, т. е.
Это можно также записать как
тД(л, /.) = tiling (л, L)	E.2)
121

Число т^ (га, L), таким образом, оказывается ха-
характеристикой уже не плана, а самой задачи (именно,
задачи нахождения за га шагов минимизирующей
точки функции f на отрезке длины L). Поэтому оно
не зависит от какого-либо плана, а зависит только от
п и L и может быть просто обозначено через rA(n, L).
В условиях задачи Б дело обстоит несколько слож-
сложнее. Здесь, как мы уже видели, нет оптимального
плана, гарантирующего в наихудших условиях наи-
наименьшую погрешность. Однако существует такая по-
погрешность, к которой можно подойти сколь угодно
близко, если только выбрать подходящий план. Эта
погрешность, которую естественно называть предель-
предельной погрешностью, также зависит только от условий
задачи. Поэтому ее естественно обозначить через
хБ(п, L). Любой план приводит к большей погреш-
погрешности:
и поэтому мы не можем написать здесь равенство,
аналогичное E.2).
Забегая несколько вперед, скажем, что итог всех
рассуждений этого параграфа, подчас довольно слож-
сложных, состоит в получении явных выражений для
хА{п, L) и хБ{п, L). Как окажется, в эти выражения
входят числа Фибоначчи:
^•^idr-'	E-3)
Таким образом, отказ от нахождения минималь-
минимального значения функции позволяет увеличить точность
определения ее минимизирующей точки в —IJ-^- раз.
Для достаточно больших п это отношение согласно
2
п. 26 § 1 близко к — = 1,236, что соответствует уве-
увеличению точности примерно на 23%.
9. Совершенно ясно, что для всех дальнейших рас-
рассуждений важны не каждое из чисел L и е само по
себе, а отношение L и е. Это отношение является
125

относительной ошибкой положения х. Если это отно-
отношение нам дано, то мы можем, выбирая надлежащим
образом единицу измерения величины х (т. е. единицу
измерения длины нашего отрезка), взять одно из чи-
чисел L и е совершенно произвольно.
Это соображение приводит к весьма поучитель-
поучительному выводу.
Изменение масштаба вдоль оси х изменяет как
численное выражение длины отрезка L, так и ошибку
в определении положения искомой точки любым
планом Р в одно и то же число раз. Другими словами,
для любого положительного К должно быть
хР (п, XL) = ХхР (п, L).	E.5)
Точно так же, если мы будем в описании плана опре-
определения минимизирующей точки указывать положе-
положения тех или иных точек отрезка не в абсолютных
мерах длины, а в относительных, то оптимальность
плана не нарушится: в результате такого изменения
в описании планов оптимальные планы останутся оп-
оптимальными, а неоптимальные — неоптимальными.
Отсюда непосредственно следует, что равномерное
растяжение (или сжатие) интервала изменения функ-
функции f в любое число раз осуществляет лишь «подоб-
«подобное преобразование» оптимального плана, не нарушая
при этом его оптимальности.
Значит, ошибки хр (п, XL) и хр (п, L), фигурирующие
в равенстве E.5), достигаются не просто в результате
осуществления тех или иных планов, а могут быть
достигнуты в результате применения одного и того же
плана, различным образом «подобно преобразован-
преобразованного».
10. После всех этих достаточно затянувшихся
предварительных рассмотрений перейдем к нахожде-
нахождению оптимального плана для задачи Лик доказа-
доказательству формул E.3) и E.4).
Лемма. Каковы бы ни были я Э: 1 и L, суще-
существует п-шаговый план поиска точки х, минимизи-
минимизирующей значение функции f (с одним минимумом)
на отрезке длины L за п шагов и обладающей сле-
следующими свойствами:
1) на каждом шаге рассматривается некоторый
отрезок х'х"\
126

2)	на первом шаге вычисляется значение функции
f в одной из точек: —— L или -Un+* L;
«п + 2	"/г + 2
3)	к началу каждого из последующих шагов с но-
номером k (г, е, при 1 < k :g n) известно значение f
в одной из следующих точек:
-х') и X2 = x' + J^(x"-x'); E.6)
4)	на k-м (I < k =S n) шаге вычисляется значение
в другой из точек E.6);
5)	на k-м (I < k fg n) шаге производится сравне-
сравнение чисел f(x\) и /(х2); при этом, если окажется, что
f (*i) Ss/(*г)> то на (k-\-l)-M шаге рассматривается
отрезок х'хг, а если \\х{) Si \{х2), то отрезок х\х".
Доказательство ведется индукцией по п.
Если «= 1, то, очевидно, мы имеем дело с отрез-
отрезком от 0 до L; значение функции f вычисляется в
точке — L = ~y', последующих же шагов в этом
случае вообще нет.
Предположим теперь, что существование некото-
некоторого «-шагового плана с требуемыми в условиях лем-
леммы свойствами нами уже установлено для любого
отрезка. Займемся построением интересующего нас
(п -\- 1)-шагового плана, проверяя параллельно
соблюдение условий леммы. Будем на каждом шаге
рассматривать некоторый отрезок х'х".
Возьмем в качестве первого шага выбор точки
J±±t а в качестве второго — выбор точки
ifn+2_ ? и Сравнение значений функции f{x\) и
f. В случае, когда f(xi)^f(x2), мы приходим к
рассмотрению отрезка между 0 и х2 (здесь 0 играет
роль х', а х2 — роль х"), а в случае /(*i) > f(x2) —
к рассмотрению отрезка между х\ и L (здесь х\ вы-
выступает в роли х', a L в роли х"). Длина рассматри-
рассматриваемого отрезка в обоих случаях равна иип+2 L.
После выполнения этих двух шагов мы находимся
применительно к рассматриваемому отрезку точно в
таких же условиях, что и при осуществлении «-шаго-
«-шагового процесса после выполнения его первого шага.
127

Именно, на отрезке длины u"+1 L известно зна-
чение функции f в точке, отстоящей на """*"' L от
ип+з
одного из его концов. Поэтому мы можем «перейти»
на этот «-шаговый процесс и довести его до конца.
На основании индуктивного предположения мы мо-
можем считать, что для последних п шагов выполняются
условия 3), 4) и 5). Следовательно, нам остается рас-
рассмотреть условия начала второго шага и его прове-
проведения. Но, очевидно, точка ""+1- L имеет вид первого
"п + 2
из выражений E.6) для случая k = 2, если вместо п
в него подставить п-f-l, а роль второго выражения
в соответствующей ситуации играет выбираемая нами
точка -^2±i-L.
«п+з
Этим индуктивный переход обоснован и лемма
доказана.
11. Будем называть n-шаговый план, существова-
существование которого было доказано в предыдущей лемме,
п-шаговым фибоначчиевьш планом, или, короче, пла-
планом Фп.
Теорема. 1) План Фп является единственным
оптимальным п-шаговым планом.
2) %* (п, 1) = ~.
п	ип+г
Доказательство ведется индукцией по п.
Рассмотрим сначала одношаговый план, состоя-
состоящий в выборе в качестве х некоторой точки х из ин-
интервала от х' до х". Очевидно, в наименее благо-
благоприятных условиях ошибка может достигнуть здесь
наибольшего из чисел х" — х и х — х'. Если эти числя
различны, то эта максимальная ошибка превосходит
-?-, если же они равны, то максимальная ошибка
равна -тр.
Таким образом, план CDi является оптимальным
одношаговым планом, а
128

При п = 2 мы имеем дело с планом Ф2, состоя-
состоящим в вычислении и сравнении значений функции
И -т L J и f (~o L) и выбора в качестве х точки
±L, если
§L, если f(±L)>f(lL).
Максимальная ошибка в определении истинного зна-
L L
чения х здесь, как легко видеть, достигает -q- =—:
О	Ui
%А (О М	L
Любой иной выбор точки будет приводить к большим
возможным ошибкам.
Основание индукции, таким образом, доказано.
Предположим теперь, что фибоначчиев план Фп
обладает требуемым в условиях теоремы свойством, и
рассмотрим (п -\- 1)-шаговые планы.
Произведя в плане Фп+\ первые два наблюдения
над функцией f, мы в результате сравнения двух ее
найденных значений сведем дело к применению к от-
резку длины	L, в котором известно значение /
в одной из точек, плана Фп, что даст нам в наименее
благоприятном случае ошибку
_ "п + 2 д / г \	 "га + 2 L- 	 L
Следовательно, т? (n+l,L) = —:—.
Нам остается показать, что план Фп+1 оптимален.
Возьмем с этой целью наблюдения над функцией /
в двух произвольных точках, х\ и х2 (для определен-
определенности будем считать, что х\ < х2). Сопоставление зна-
значения f(x\) с f(x2) приводит к поискам точки х либо
на отрезке от 0 до х2, либо на отрезке от х\ до L.
Если
xt<L,
1 «я+з '
то в случае f(fi)>[(.v2) нам придется искать по не-
129

которому n-шаговому плану минимизирующую f точку
на отрезке длины L — х\, т. е. большей, чем
т Un+\ т 	 u-п+г — «ft+i т 	 Цд+2 /
Li	Li 		L, 	 ~~"~~~" Li,
«га+з	«n+з	и«+з
Даже если положение точки Xi на этом отрезке
наиболее благоприятно, то ошибка в определении
окажется на основании индуктивного предположения
большей, чем 	.
"«+3
Симметричные рассуждения показывают, что план,
начинающийся выбором некоторой точки
также может при соответствующих неблагоприятных
условиях привести к большей ошибке в определении
х, чем план Фп+и
Пусть теперь
Х\ >	L.
«п+з
Если в действительности х находится между 0 и х\, то
на поиски местоположения этой точки нам остается
п—1 наблюдение, а длина отрезка, заключающего
эту точку, больше, чем n+' L. Значит, даже план
ип+ъ
Ф„_1 (который, по предположению, в этих условиях
оптимален) приведет нас к ошибке, большей, чем
Un+i
Симметрично разбирается случай, когда
Следовательно, план Фп+1 является оптимальным, и
теорема доказана.
Итак, единственная минимизирующая функцию /
точка может быть с помощью п наблюдений опреде-
определена на отрезке длины L с ошибкой, не превосходя-
L
щей
130

Поэтому п наблюдений позволяют определить
точку, минимизирующую /, с ошибкой 8 или меньше,
на отрезке, длина которого не превосходит еип+2-
Наконец, чтобы быть уверенным в том, что точка,
минимизирующая функцию /, определена на отрезке
длины L с ошибкой, не превосходящей е, необходимо
произвести такое число п наблюдений, что
ип+1 < ~ S3 W/i+2-
Таким образом, мы ответили на все вопросы п. 3.
12. Решение задачи Б можно получить из описан-
описанного выше решения задачи А без особого труда.
Пусть нам дан отрезок длины L. Проделаем на
этом отрезке первые п — 2 шага фибоначчиева плана
_ _ 3L
Фп-ь В результате мы придем к отрезку длины
W/Z+ 1
с концами х' и х" и с известным значением / в одной
из точек Х\ = х' -\	или х2 = х'-\	. Ограни-
чимся рассмотрением первого из этих случаев (второй
рассматривается симмет-
симметрично).	9	]
Итак, пусть f(xi) нам |	|
уже известно. Выберем i | i
произвольное число у, по -jc i j
абсолютной величине	i [ i
L	ill
меньшее, чем	; вы- }р ~^z~t ~T~v~t	\,
ЧИСЛИМ f(x2 — Y) (ЭТО
есть (п—l)-e вычислен-	Рис. 26.
ное значение функции {) и
сравним f(xi) и f(x2 — v)-
Если f(x\) ^ f(x2 — y) (случай ° на рис. 26), то,
очевидно, х находится между х' и х2 — y- Вычислим
(это — последнее, n-е вычисленное значение функ-
функции /).
Если при этом
f (*¦-?)==?/(*,)
131

(случай х на рис. 26), то х расположено между х' и х\.
Положим jc = —-—-. Ошибка в определении х не
превосходит половины длины отрезка от х' до Х\,
т. е. -х-	. Если
(случай ° на рис. 26), то х находится между
и х2 — у. Положив х^-^((х\—^Л + (х2—уп, мы
совершим ошибку, не большую, чем
y (to - y) - (*i - т))= т (Х2 - Xi - i)=
__ х2 — хх 	 у_ _ L 	 Y.
~ 2	4~ 2«„ + 1 4 '
Пусть теперь f(xi)>f(x2 — у) (рис. 27). Тогда к
.	находится между х\ и х".
,;,	Вычислим f(x2) (по-
i	следнее вычисленное зна-
] |	чение f).
i *	Если
j
н		^
д-	л} г-у ^г	(случай о на рис. 27), то х
расположено между Х\ и
Рис. 27.	1
х2; беря * = -^ w + х2),
мы допустим ошибку, достигающую разве лишь
1	L
"о" (-"•г ~^ -^l) == ~пТ. •
Если, наконец,
f(x2 — y)>f (x2)
(случай х на рис. 27), то л: расположено между х2 — v
и х"; положив х = -^- (х" + (х2 — у))> мы совершаем
ошибку, не превосходящую
— "— — ))— ' ( L	Л — L I v
132

В наихудшем для нас случае при у > О ошиб-
ошибка может таким образом достигнуть величины
+ -Ь а при V<«-величины^--!. По-
скольку, однако, число у находится в нашем распоря-
распоряжении, мы можем сделать ошибку, сколь угодно близ-
L
кои к ¦=	.
2««+i	{
Нам остается убедиться в том, что ошибку тт——
уменьшить нельзя.
В самом деле, отклонения от описанного плана на
каком-либо из первых п — 2 шагов могут привести,
как видно из теоремы п. 11, только к увеличению
длины отрезка, в котором местоположение минимизи-
минимизирующей точки определяется последующими измере-
измерениями, и тем самым к заведомому увеличению макси-
максимальной ошибки. Остается проверить оптимальность
действий, совершаемых на последних двух шагах.
Прежде всего, отклонение от описанных действий
может означать окончательный выбор в качестве х но
середины отрезка, где эта точка действительно распо-
расположена, а другой точки. Ясно, что это приведет к
тому, что возможная ошибка окажется равной боль-
большей части отрезка, т. е. возрастет. Следовательно,
должна быть выбрана именно середина отрезка.
Далее, мы могли бы выбрать для последнего опре-
определения f точку, не близкую к точке х\ (или соответ-
соответственно к х2). Но тогда возможная ошибка увеличи-
увеличилась бы и притом пропорционально расстоянию меж-
между этими точками.
Наконец, к таким же последствиям привел бы
выбор точки для предпоследнего определения f, дале-
далекой от Х2 (соответственно от Х\).
Итак, ни одно из отклонений от описанного плана
не может повлечь за собой уменьшения возможной
ошибки до числа, меньшего, чем -=	. Это показы-
показывает, что задача Б нами решена.
Мы предоставляем читателю сформулировать п
случае задачи Б ответы на остальные вопросы, пере-
перечисленные в п. 3.
13. В предыдущих пунктах описание самого пла-
плана поиска сопровождалось уточнениями постановки
133

задачи, формулировками, связанными с понятием
оптимальности и обоснованиями оптимальности конст-
конструируемого плана. Все эти отступления от прямого
описания являются неотъемлемыми элементами вся-
всякого математического рассуждения, цель которого
состоит не только в указании какого-то процесса, но
и в доказательстве того, что этот процесс—именно
тот, который нас интересует. Вместе с тем во многих
случаях существенным является четкое описание дей-
действий как таковых, а вся аргументация этих действий
становится совершенно неважной. Это бывает тогда,
когда, например, после решения задачи имеется в
виду фактическое осуществление этого решения. В та-
таких случаях для реализации решения задачи на прак-
практике необходимо располагать не столько математи-
математическим обоснованием верности решения, сколько
предельно четкими, не допускающими каких бы то
ни было кривотолков, предписаниями по его претво-
претворению в жизнь.
План наиболее точных поисков на отрезке от х1
до х" точки х, минимизирующей функцию f в условиях
задачи А в изложении, преследующем только что
описанные, так сказать, «практические» цели, напо-
напоминает план установления вида растения по ботани-
ботаническому определителю (заметим, что определение ра-
растения есть тоже поиск!). Он принимает следующий
вид (если в конце пункта не указывается, к какому
пункту следует переходить, то нужно переходить к
следующему пункту):
1°. Сравнить 1 и п:
а)	если п = 1, то перейти к п. 2°;
б)	если п > 1, то перейти к п. 4°.
2°. Вычислить х— х \х" ¦
3°. Вычислить / (х); на этом процесс кончается.
4°. Вычислить
-*') И х^
5°. Вычислить f (х\) и f (x2).
6°. Сравнить 2 и п:
а)	если п =2, то перейти к п. 7°;
б)	если п > 2, то перейти к п. 10°.
134

7°. Сравнить f(x{) и f (x2):
а)	если f (xi) sS / (х2), то перейти к п. 8°;
б)	если f(xl)>f(x2), то перейти к п. 9°.
8°. Положить х — Х\ и закончить процесс.
9°. Положить х = х2 и закончить процесс.
10°. Сравнить /(*,) и /(х2):
а)	если / (х\) sg / (х2), то перейти к п. 11°;
б)	если f(x\)>f(x2), то перейти к п. 14°.
11°. Переобозначить
х2	через х",
х\	через х2,
п — 1	через п.
12°. Вычислить
13°. Вычислить f (х\) и перейти к п. 6°.
14°. Переобозначить
Х\ через х',
х2 через Х\,
п — 1 через п.
15°. Вычислить
16°. Вычислить f(x2) и перейти к п. 6°.
14.	Хотя сформулированное описание оптималь-
оптимального плана поисков минимума функции f абсолютно
четкое, не оставляющее места какому-либо произволу,
и в применении к каждой конкретной функции /, от-
отрезку от х' до х" и числу п предписывает совершенно
точную последовательность действий, оно является
довольно запутанным и трудно обозримым.
Приведем поэтому для наглядности еще одно опи-
описание этого же плана в виде некоторой графической
схемы (рис. 28).
Схемы такого рода обычно называются блок-схе-
блок-схемами. Составление блок-схемы вычислительного про-
процесса обычно является первым этапом при составле-
составлении программы проведения вычислений на электрон-
электронных цифровых вычислительных машинах.
15.	Приведем в заключение пример использова-
использования описанного в пп. 13 и 14 плана для нахождения
135

2°
3L
Да
_ x'+x"
" 2
¦
Конец
|
Нет'.
л+Z
\
f(*,)
i—.
л=2
Да	Нет
Да
Ж=Х;
Конец
Нет
9°
¦
S=x2
КОЖГ !
77"
Да
хг-х"
73°
/7*2
7У
76'
Нет
РИС. 21.
136

с помощью пяти вычислений на отрезке от 1 до 2
точки х, минимизирующей функцию
Предварительно сделаем важное замечание.
Нахождение точки, минимизирующей (или макси-
максимизирующей) функцию, которая задана аналитически
(т. е. в виде формулы, позволяющей вычислять ее
значения), обычно удобнее проводить не методами
теории поиска, а другими, более приспособленными
для этого приемами, которые относятся к дифферен-
дифференциальному исчислению. Поэтому следует иметь в
виду, что приводимый далее пример носит чисто
иллюстративный характер. Диференциальное исчисле-
исчисление позволяет без труда показать, что в этом случае
х = <\/4 = 1,5874011 ... Нам же удастся найти значи-
значительно более грубое приближение. Однако в тех слу-
случаях, когда заранее о функции нам неизвестно ничего
(кроме того, что она не может переходить от возра-
возрастания к убыванию) или же выражения, которыми
она задается, чересчур сложны, методика дифферен-
дифференциального исчисления неприменима, и теория поиска
оказывается полезным инструментом.
Г. Сравнение « = 5 и 1 дает нам, что пф\, по-
поэтому переходим к п. 4°.
4°. Вычисляем:
х"-х')=\ +4" B- 0=1,38461,
*" - *') = 1 + 4-B - 1) = 1,61538.
1
5°. Вычисляем:
f (x\) = 4- + V^ = f A.38461) = 0,72222 +1,17670 =
= 1,89892,
/ (Х2) = -L + л/х~2 = f A,61538) = 0,61905 + 1,27098 =
= 1,89003.
6°. Сравнение rt = 5 и 2 дает, что п Ф 2; поэтому
переходим к п. 10°.
137

10°. Сравнение
f(x,) = 1,89892 и /(х2) = 1,89003
дает нам f(X])>f(x2); поэтому переходим к п. 14°.
14°. Переобозначаем:
Xl->x'= 1,38461,
Л;2_»Х1 = 1,61538,
п = 4.
15°. Вычисляем:
х2 = х' + -2*±i- (х" - х') = 1,38461 + -I B - 1,38461) =
"rt + 2	О
= 1,76927.
16°. Вычисляем:
+ V^7
= /A,76927) = 0,56522+ 1,33012 =
= 1,89534	i
и переходим к п. 6°.	>
6°. Сравниваем п = 4 и 2; поскольку пф2, пере-
переходим к п. 10°.
10°. Сравниваем f(хО = 1,89003 и /(*2)= 1,89534;
поскольку / (х\) ^ f (x2), переходим к п. 11°.
11°. Переобозначаем:
х2->х"= 1,76923,
хх-*х2 = 1,61538,
12°. Вычисляем:
= 1,38461 +|-A,76923 — 1,38461)= 1,53846.
13°. Вычисляем:
= -^ + V^i - / A,53846) = 0,65000 + 1,24035 =
= 1,89035
и переходим к п. 6°.
6°. Сравниваем п = 3 и 2; поскольку пф2, пере-
переходим к п. 10°.
133

10°. Сравниваем
f (*,) = 1,89035 и f (х2) = 1,89003;
поскольку f(x{) > f(x2), переходим к п. 14°.
14°. Переобозначаем:
х1->х'= 1,53846,
х2->х{ = 1,61538,
п = 2.
15°. Вычисляем:
х2 = х' + 2z*± {x" — х') =
= 1,53846 + -| A,76923 - 1,53846) = 1,69231.
16°. Вычисляем
/ (х2) = — + V*7 = f A,69231) = 0,59091 + 1,30089 =
= 1,89170
и переходим к п. 6°.
6°. Сравнение п и 2 дает нам, что п = 2; перехо-
переходим к п. 7°.
7°. Сравниваем
f(xi)= 1,89003 и f(*2)= 1,89170;
) ^ f (x2); поэтому переходим к п, 8.
8°. Полагаем х — 1,61538.
На основании теоремы п. 11 найденное нами х
может отличаться от истинного положения миними-
зирующеи точки не более чем на —	= — = -^ =
= 0,077. Фактически эта ошибка оказывается мень-
меньшей; она равна 0,028. Заметим, что принимаемое нами
за наименьшее значение функции /, т. е. f(x), равно
1,89003 и отличается от истинного наименьшего зна-
значения /, равного
= { ^2 = 1,88988,
) = =,
лишь на 0,00015. Это показывает, что значения х
можно было в ходе наших вычислений определять
с меньшей точностью, чем значения f.
139

Сам по себе такой вывод не содержит ничего уди-
удивительного. В самом деле, значения х мы должны
находить с той предельной точностью, с какой мы
можем в наших условиях найти минимизирующую
точку х (мы знаем, что эта точность равна 	).
Значения же функции / должны вычисляться с точ-
точностью, обеспечивающей сравнение пар значений
этой функции и выделение из каждой такой пары наи-
наименьшего и наибольшего значения. Поэтому если в
действительности какие-нибудь f(a) и f(b) сильно
отличаются друг от друга и это отличие заметно уже
при грубом определении f(a) и f(b), то мы можем
вычислять эти значения с малой точностью. Наоборот,
если эти Да) и f(b) в действительности близки, то
для выяснения того, какое из них больше другого,
приходится вести вычисление с большой точностью.
Так как мы наперед (до фактического выполнения
пычислений) не знаем, насколько отличаются друг ог
друга сравниваемые значения функции, мы можем
«промахнуться» и вычислить их с недостаточной точ-
точностью, которая не даст возможности решить, какое
из этих значений больше. В этом случае придется
произвести повторные, более точные вычисления, за-
затратив на это дополнительные усилия.
Все сказанное вызывает необходимость рассмот-
рассмотрения дальнейших проблем, касающихся «управления
точностью» вычислительного процесса. Однако эти
вопросы довольно сложны и с темой данной книжки
непосредственно уже не связаны.

СОДЕРЖАНИЕ
Предисловие к первому изданию		3
Предисловие к четвертому изданию		5
Введение . •		7
§ 1. Простейшие свойства чисел Фибоначчи ...	11
§ 2. Теоретико-числовые свойства чисел Фибоначчи	39
§ 3. Числа Фибоначчи и непрерывные дроби ...	71
§ 4. Числа Фибоначчи и геометрия		94
§ 5. Числа Фибоначчи и теория поиска		115

Николай Николаевич Воробьев
Числа Фибоначчи
(Серия «Популярные лекции по математике»)
М., 1978 г., 144 стр.
Редактор В. В. Доиченко
Техн. редактор Е. В.Морозова
Корректор Л. С. Сомова
ИВ № 11172
Сдано в набор 24.02.78. Подписано к печати
01.09.78. Бумага 84Х108'/зг, тип. № 1. Литератур-
Литературная гарнитура. Высокая печать. Условн. печ. л.
7,56. Уч.-изд. л. 7,07. Тираж 100 000 экз. Заказ
№ 990. Цена 25 коп.
Издательство «Наука»
Главная редакция
физико-математической литературы
117071, Москва, В-71, Ленинский проспект, 15
Ордена Трудового Красного Знамени Ленин-
Ленинградская типография № 2 имени Евгении
Соколовой «Союзполиграфпрома» при Государ-
Государственном комитете Совета Министров СССР
по делам издательств, полиграфин и книжной
торговли. 198052, Ленинград, Л-52, Измайловский
проспект, 29.

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
Вып. 1. А. И. М а р к у ш е в и ч. Возвратные последовательности.
Вып. 2. И. П. Н а т а н с о и. Простейшие задачи на максимум и
минимум.
Вып. 3. И. С. С о м и н с к и й. Метод математической индукции.
Вып. 4. А. И. М а р к у ш е в и ч. Замечательные кривые.
Вып. 5. П. П. К о р о в к и и. Неравенства.
Вып. 6. Н. Н. Воробьев. Числа Фибоначчи.
Вып. 7. А. Г. К у р о ш. Алгебраические уравнения произвольных
степеней.
Вып. 8. А. О. Г е л ь ф о н д. Решение уравнений в целых числах.
Вып. 9. А. И. М а р к у ш е в и ч. Площади и логарифмы.
Вып. 10. А. С. С м о г о р ж е в с к и й. Метод координат.
Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказатель-
доказательствах.
Вып. 12. И. П. Натансон. Суммирование бесконечно малых
величин.
Вып. 13. А. И. М а р к у ш е в и ч. Комплексные числа и конформ-
конформные отображения.
Вып. 14. А. И. Фетисов. О доказательствах в геометрии.
Вып. 15. И. Р. Ш а ф а р е в и ч. О решении уравнений высших сте-
степеней.
Вып. 16. В. Г. Ш е р в а т о в. Гиперболические функции.
Вып. 17. В. Г. Болтянский. Что такое дифференцирование?
Вып. 18. Г. М. М и р а к ь я н. Прямой круговой цилиндр.
Вып. 19. Л. А. Л юс тер ни к. Кратчайшие линии.
Вып. 20. А. М. Л о п ш и ц. Вычисление площадей ориентирован-
ориентированных фигур.
Вып. 21. Л. И. ГоловинаиИ. М. Яглом. Индукция в гео-
геометрии.
Вып. 22. В. Г. Болтянский. Равновеликие и равносоставлен-
иые фигуры.
Вып. 23. А. С. С м о г о р ж е в с к н й. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигура-
Конфигурационные теоремы.
Вып. 25. А. С. С м о г о р ж е в с к и й. Линейка в геометрических
построениях.	»
Вып. 26. Б. А. Т р а х т е н б р о т. Алгоритмы и машинное решение
задач.
Вып. 27. В. А. Успенский. Некоторые приложения механики
к математике.
Вып. 28. Н. А. Архангельский и Б. И. Зайце в. Автомати-
Автоматические цифровые машины.
Вып. 29. А. Н. К о с т о в с к и й. Геометрические построения од-
одним циркулем.
Вып. 30. Г. Е. Шилов. Как строить графики.
Вып. 31. А. Г. Д о р ф м а н. Оптика конических сечений.
Вып. 32. Е. С. В е н т ц е л ь. Элементы теории игр.
Вып. 33. А. С. Б а р с о в. Что такое линейное программирование?
Вын. 34. Б. Е. Маргулис. Системы линейных уравнений.
Вып. 35. Н. Я. В и л е н к и н. Метод последовательных приближе-
приближений.
Вып. 36. В. Г. Б о л т я и с к и й. Огибающая.
Вып. 37. Г. Е. Шило в. Простая гамма (устройство музыкаль-
музыкальной шкалы).
Вып. 38. Ю. А. Ш рей дер. Что такое расстояние?
Вып. 39. Н. Н. Воробье в. Признаки делимости.
Вып. 40. С. В. Ф о м и н. Системы счисления.
Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.
Вып. 42. 10. И. Любич и Л. А. Шор. Кинематический метод в
геометрических задачах.
Вып. 43. В. А. Успенски й. Треугольник Паскаля.
Вып. 44. И. Я. Б а к е л ь м а н. Инверсия.
Вып. 45. И. М. Яглом. Необыкновенная алгебра.
Вып. 46. И. М. С о б о л ь. Метод Монте-Карло.
Вып. 47. Л. А. К а л у ж н и и. Основная теорема арифметики.
Вып. 48. А. С. Солодовников. Системы линейных неравенств.
Вып. 49. Г. Е. Ш и л о в. Математический анализ в области рацио-
рациональных функций.
Вып. 50. В. Г. Болтянский, И. Ц. Г о х б е р г. Разбиение фи-
фигур на меньшие части.
Вып. 51. И. М. Б ее к и н. Изображения пространственных фигур.
Вып. 52. Н. М. Б ее к и н. Деление отрезка в ллнном отношении.
Вып. 53. Б. А. Розен фельд н И. Д. Сергеева. Стереогра-
Стереографическая проекция.