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

А теперь перейдем к особенной последовательности чисел — быть может, наиболее приятной из всех — последовательности Фибоначчи

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

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

Наглядный пример естественного возникновения чисел Фибоначчи дают „родословные деревья пчел“ Рассмотрим родословную пчелы-самца. Каждый самец (называемый также трутнем) появляется на свет непарным путем от самки (называемой также маткой), однако каждая самка имеет двух родителей — самца и самку. Вот несколько начальных уровней такого дерева:

У трутня один дед и одна бабка, один прадед и две прабабки, два прапрадеда и три прапрабабки. И вообще, как легко установить по индукции, у него ровно прап-дедушек и прап-бабушек.

Числа Фибоначчи часто обнаруживаются в природе — возможно, по причинам, аналогичным закону образования родословного дерева пчел. К примеру, семечки, плотно набитые в крупную „корзинку" обыкновенного подсолнуха, располагаются по спиралям — обычно это 34 спирали, закручивающиеся в одном направлении, и 55 спиралей — в другом. Корзинки поменьше будут иметь соответственно 21 и 34 или же 13 и 21 спираль, а однажды в Англии демонстрировался гигантский подсолнух с 89 спиралями одного направления и 144 — другого. Подобные закономерности обнаруживаются и в некоторых видах сосновых шишек.

А вот пример другого рода [223]. Предположим, что друг на друга наложены две стеклянные пластинки. Сколько существует способов прохождения луча света через пластинки или отражения от них после изменения его направления раз? Несколько первых случаев таковы:

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

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

Эти числа ввел в 1202 г. Леонардо Фибоначчи, и математики постепенно стали выяснять все больше и больше интересного о них. Эдуард Люка, причастный к головоломке о ханойской башне, рассмотренной в гл. 1, активно занимался ими во второй половине девятнадцатого столетия (в действительности, благодаря именно Люка, название „числа Фибоначчи" стало общеупотребительным). Одно из его удивительных достижений состояло в использовании свойств чисел Фибоначчи для доказательства того, что -значное число Мерсенна является простым.

Одним из самых первых фактов о числах Фибоначчи, обнаруженным в 1680 г. французским астрономом Жан-Домиником Кассини [126], является соотношение

Так, при соотношение Кассини справедливо утверждает, что (Этот закон был известен Иоганну Кеплеру [1291 еще в

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

для выражения через большие числа Фибоначчи при и если воспользоваться формулой

для замены меньшими числами Фибоначчи при Так, например, можно заменить на в (6.103), получая соотношение Кассини вида

Кроме того, если заменить то соотношение Кассини принимает вид

это то же самое, что и , а последнее совпадает с Таким образом «Кассини(n)» справедливо тогда и только тогда, когда справедливо «Кассини(n+1)» так что по индукции равенство (6.103) справедливо при любом

Соотношение Кассини лежит в основе геометрического парадокса, который был одной из излюбленных головоломок Льюиса Кэррола ([160], [352], [301]). Суть его в том, чтобы взять шахматную доску и разрезать ее на четыре части, как показано ниже, а затем составить из этих частей прямоугольник:

Presto: первоначальные клетки переставлены так, что получилось клеток! Аналогичная конструкция расчленяет любой -квадрат на четыре части с размерами сторон клеток вместо соответственно 13, 8, 5, и 3 клеток в нашем примере. В результате получается -прямоугольник, и в соответствии с (6.103) одна клетка либо прибавляется, либо утрачивается — в зависимости от того, четно или нечетно

Строго говоря, мы не можем применять правило (6.105) кроме как при ибо нами не определены при отрицательном Мы обретем большую свободу действий, если избавимся от этого ограничительного условия и воспользуемся правилами (6.104) и (6.105) Для доопределения чисел Фибоначчи при отрицательных индексах. Так, оказывается равным — равным Действуя таким образом, выписываем величины

и вскоре становится ясно (по индукции), что

Если обобщить последовательность Фибоначчи подобным образом, то соотношение Кассини (6.103) будет справедливым при любых целых а не только при

Процесс сведения к комбинации по правилам (6.105) и (6.104) приводит к последовательности формул

в которой просматривается закономерность другого рода:

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

Если в (6.108) положить то выясняется, что

следовательно, кратно Аналогично,

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

при любых целых кип. Это объясняет, в частности, почему (которое равно 610) кратно как так и (которые равны 2 и 5). Фактически справедливо даже большее: в упр. 27 доказывается, что

К примеру,

Теперь можно доказать обращение свойства если и если кратно то кратно Действительно, если то . А это возможно только тогда, когда и наше допущение о том, что приводит к необходимости того, что Следовательно, .

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

Докажем это, рассмотрев последовательность при и выяснив, когда же (Мы знаем, что должно иметь вид если Вначале имеем что не равно нулю. Затем, согласно (6.108), получаем

поскольку Аналогично

Это сравнение позволяет вычислить

И вообще, индукцией по к устанавливается, что

А поскольку взаимно просто с то

и лемма Матиясевича доказана.

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

Тогда каждое целое положительное число имеет единственное представление вида

(Это „теорема Цеккендорфа“ [188], [342].) К примеру, представление одного миллиона оказывается таким:

Подобное представление всегда может быть найдено с помощью „жадного" подхода: в качестве выбирается наибольшее число Фибоначчи затем в качестве выбирается наибольшее число (Более точно, предположим, что тогда Если -одно из чисел Фибоначчи, то представление (6.113) справедливо при . В противном случае индукция по показывает, что имеет фибоначчиево представление и представление (6.113) справедливо, если положить ибо неравенства означают, что ) И обратно, всякое представление вида (6.113) означает, что

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

(Эта формула легко доказывается индукцией по к — ее левая часть обращается в нуль при к равном 2 или 3.) Поэтому это как раз описанная выше, „жадно“ выбранная величина, и данное представление должно быть единственным.

Любая система однозначного представления чисел является системой счисления — следовательно, теорема Цеккендорфа приводит к фибоначчиевой системе счисления. Всякое целое неотрицательное число можно представить в виде последовательности нулей и единиц, записав

Эта система счисления отчасти напоминает двоичное (с основанием 2) представление, за исключением того, что в ней никогда не встречаются две 1 подряд. Вот, к примеру, числа от 1 до 20, представленные по Фибоначчи:

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

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

При прибавлении 1 в фибоначчиевой системе счисления возникают два случая. В случае, если „разряд единиц“ есть 0, он заменяется на 1 — тем самым прибавляется ибо разряд единиц связан с . В противном случае двумя наименее значащими цифрами будут и они заменяются на 10 (тем самым прибавляя Наконец, мы должны „перенести“ 1 столько раз, сколько это необходимо, заменяя набор цифр на до тех пор, пока в строке цифр имеются две рядом стоящие 1. (Подобное правило переноса эквивалентно замене на Так, для того чтобы перейти от или от переносов не требуется, но для того чтобы перейти от необходимо выполнить перенос дважды.

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

чисел Стирлинга, ни для чисел Эйлера или Бернулли найдены не были, мы все же сумели обнаружить замкнутое выражение для гармонических чисел. А нет ли какой-нибудь связи между и другими известными нам величинами? Можно ли „разрешить" рекуррентность, посредством которой определяются числа

Ответ утвердительный: действительно, существует простой способ решения этой рекуррентности, если воспользоваться понятием производящей функции, вкратце рассмотренной в гл. 5. Образуем бесконечный ряд

Если мы сможем найти простую формулу для то появятся шансы установить простую формулу и для его коэффициентов

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

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

и решение получается в виде компактной формулы

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

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

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

Следовательно, все, что от нас требуется, — это найти константы , такие, что

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

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

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

Обратите внимание, что сомножители в знаменателе уравнения (6.119) записаны в виде а не в более привычной форме где — некоторые корни. Дело в том, что запись приводит к более привлекательным разложениям в степенные ряды.

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

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

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

и искомые константы и получены.

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

(Ниже будет еще о числах

Итак, найдены константы необходимые в (6.119); теперь нужно лишь установить А и В в (6.120). Подстановка в это уравнение показывает, что так что (6.120) сводится к уравнению

решением которого является Следовательно, разложение (6.117) на элементарные дроби имеет вид

Неплохо: получено в той форме, что и хотелось. А разложение дробей в степенные ряды, как в (6.118), доставляет выражение в замкнутой форме для коэффициента при

(Эта формула впервые опубликована Даниэлем Бернулли в 1728 г., но о ней позабыли до 1843 г., пока она не была вновь открыта Жаком Вине [25].)

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

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

Проявив некоторую смекалку, можно было бы просто угадать формулу (6.123) и доказать ее по индукции. Однако метод производящих функций является действенным способом именно ее нахождения — в гл. 7 мы увидим, что тот же самый метод приводит к решению куда более трудных рекуррентных соотношений. Между прочим, мы нисколько не беспокоились, сходятся ли бесконечные суммы в нашем выводе формулы -оказывается, что большинство операций с коэффициентами степенного ряда может быть строго обосновано независимо от того, сходятся или нет данные суммы в действительности [336]. Тем не менее, скептически настроенные читатели, подозрительно относящиеся к действиям с бесконечными суммами, могут найти успокоение в том факте, что после того, как уравнение (6.123) найдено с использованием бесконечного ряда, оно может быть проверено путем надежного доказательства по индукции.

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

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

ибо при любом . Если четно, то немного меньше, чем в противном случае оно немного больше.

Соотношение Кассини (6.103) может быть переписано как

При большом величина весьма мала, так что отношение должно быть почти тем же самым, что и отношение а (6.124) указывает на то, что это отношение приближает . И в самом деле,

(Это соотношение непосредственно проверяется при а при доказывается по индукции; оно может быть также доказано непосредственно подстановкой в формулу Отношение весьма близко к числу которое оно приближает попеременно то с избытком, то с недостатком.

Кроме того, в силу простого совпадения, число довольно близко к числу километров в одной миле. (Точное число равно 1.609344, поскольку один дюйм равен в точности 2.54 сантиметрам.) Это дает нам удобный способ перевода в уме километров в мили и обратно, ибо расстояние в километров равно (довольно близко) расстоянию в миль.

Предположим, что мы хотим перевести некоторое число (не являющееся числом Фибоначчи) километров в мили — сколько будет 30 км по-американски? Это делается легко: мы просто прибегаем к фибоначчиевой системе счисления и переводим в уме число 30 в его фибоначчиевое представление с помощью объясненного выше „жадного" подхода. Теперь можно сдвинуть каждое число на одну позицию вправо, получая . (Первоначальная была числом поскольку в (6.113); новая же Сдвиг вправо практически равносилен делению на Следовательно, наша оценка — 19 миль. (Это довольно точная оценка: правильный ответ — около 18.64 миль.) Аналогично, для перехода от миль к километрам можно осуществить сдвиг на одну позицию влево: 30 миль — это примерно километров. (Это уже не столь точная оценка: правильное число — около 48.28.)

Оказывается, что подобное правило „сдвига вправо" дает правильно округленное число миль в километрах при всех , за исключением случаев , когда оно отличается меньше чем на 2/3 мили. А правило „сдвига влево" дает либо правильно округленное число километров в милях, либо на 1 км больше, при всех . (Единственный, действительно нарушающий данное правило случай — это когда отдельные ошибки округления для накладываются друг на друга, вместо того чтобы компенсировать друг друга.)