Числа Фибоначчи

Самый значительный математик европейского средневековья – Леонардо Пизанский (Фибоначчи) – в «Книге абака» сформулировал следующую задачу:
«Некто поместил пару кроликов в некоем месте, огороженном со всех сторон стеной, чтобы узнать, сколько пар кроликов родится при этом в течение года, если природа кроликов такова, что через месяц пара кроликов производит на свет другую пару, а рождают кролики со второго месяца после своего рождения».
Если первая пара кроликов – новорожденные, то на второй месяц имеем по-прежнему 1 пару, на третий месяц – уже 2 (кролики начали размножаться), на четвертый – 3 (потомство пока дает лишь первая пара), на пятый – 5 (начала размножаться пара, родившаяся на третьем месяце), на шестой – 8 (потомство дают те пары, которые имелись на четвертом месяце) и т. д. Каждый раз число кроликов, имеющихся на n-ом месяце, равно числу кроликов на (n – 1)-ом месяце плюс число только что родившихся, которое, в свою очередь, равно числу кроликов на (n – 2)-ом месяце. Если обозначить число кроликов на n-ом месяце un, то un = un – 1 + un – 2. При этом u1 = 1, u2 = 1. Исходя из этих двух значений, можно вычислить u3 = 2, u4 = 3, u5 = 5, u6 = 8, u7 = 13, u8 = 21, u9 = 34, u10 = 55, u11 = 89, u12 = 144.

Последовательность, разумеется, можно продолжать по тому же закону un = un – 1 + un – 2 до бесконечности. Французский математик XIX в. Эдуар Люка назвал ее последовательностью чисел Фибоначчи. С помощью свойств чисел Фибоначчи он доказал, что число Мерсенна (2127 – 1) является простым.

Рис. 1. Число кроликов в задаче Фибоначчи
Рис. 2. Каждое число Фибоначчи равно сумме двух предыдущих

Числа Фибоначчи обладают целым рядом замечательных свойств, например:
u1 + u2 + u3 + ... + un = un + 2 – 1,
u1 + u3 + u5 + ... + u2n – 1 = u2n,
u2u4 + u6+ ... + u2n = u2n + 1 – 1.

Попробуйте их доказать, используя, что un = un + 2 – un + 1 и  un = un + 1 – un + 2.

Есть замечательное свойство делимости чисел Фибоначчи, а именно: un делится на um тогда и только тогда, когда n делится на m. Можете проверить это свойство для различных n и m.

Возникает вопрос: а нельзя ли с помощью какой-нибудь формулы выразить n-ое число Фибоначчи выразить через n без ссылок на предыдущие числа? Нельзя ли, скажем, каким-то образом свести числа Фибоначчи к геометрической прогрессии? Для ответа на этот вопрос рассмотрим, нет ли такого числа q, что qn = qn – 1 + qn – 2. Сократив на qn – 2, получаем q2 = q + 1. Решив это уравнение, получим:

Нетрудно заметить, что q1 – не что иное, как большое число Фидия Φ, выражающее золотое сечение. Об этом, впрочем, нетрудно было догадаться: золотое сечение – такое отношение двух отрезков, что больший отрезок относится к меньшему, как сумма обоих отрезков к большему: (a + b) / a = a/b. Если Φ = a/b, то 1 + 1/Φ = Φ, откуда Φ2 = Φ + 1. В то же время q2 = – 1/Φ = –φ(φ= 1/Φ  – малое число Фидия).
Далее рассмотрим последовательность
Поскольку Фn = Фn – 1 + Фn – 2,  (–φ)n = (–φ)n – 1 + (–φ)n – 2, вычтя одно равенство из другого, получим
Φn – (–φ)n = (Φn – 1 – (–φ)n – 1) + (Φn – 2 – (–φ)n – 2),

а поделив обе части на , найдем

откуда vn = vn – 1 + vn – 2. Кроме того,

v2 = Φ2 – (–φ)2 = Φ + 1 + (–φ– 1) = Φ + (–φ) = 1.

Таким образом, последовательность обладает тем свойством, что v1 = v2 = 1, vn = vn – 1 + vn – 2.
Эта последовательность совпадает с последовательностью чисел Фибоначчи un, и нами найдена формула для n-го числа Фибоначчи:

(она называется формулой Бине по имени открывшего ее французского математика XIX в. Ж. Ф. М. Бине).

Рассмотрим формулу Бине. Поскольку φ < 1, последовательность (–φ)n является бесконечно убывающей геометрической прогрессией. Следовательно, с ростом n число un все слабее отличается от Φn. Таким образом, отношение двух последовательных чисел Фибоначчи un+1/un с ростом n делается все ближе и ближе к «золотому сечению».

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

Решение

Последовательность Фибоначчи неожиданно появляется в самых разных математических задачах, на первый взгляд, с этими числами никак не связанных, в частности, в задачах теории игр, оптимизации и т. д. Последовательность Фибоначчи встречается и в живой природе – например, в филлотаксисе (листорасположении). Листья или почки на ветвях многих растений располагаются по спирали, причем на определенное число оборотов (k) спирали приходится определенное число листьев (l). Ряды листьев, идущие вдоль побега, – так называемые ортостихи, – образуют друг с другом угол 360° k / l.

Растение k l Угол
Пшеница, липа, вяз, бук 1 2 180°
Орешник, виноград, тюльпан, осока 1 3 120°
Дуб, вишня 2 5 144°
Малина, тополь, барбарис 3 8 135°
Миндаль, облепиха 5 13 138° 28′

Нетрудно видеть, что k и l – два числа Фибоначчи, стоящие «через одно»: un и un +2. При возрастании n отношение этих чисел становится все ближе к числу
а угол – к т. н. идеальному углу, приблизительно равному 137° 30′ 28′′.

Зачатки листьев на поперечном разрезе почки, а также чешуйки на шишке, цветки в соцветиях-корзинках располагаются иначе: на пересечении двух семейств спиралей, называемых парастихами. Парастихи одного семейства закручиваются к центру против хода часовой стрелки, спирали другого семейства – по ходу; при этом числа тех и других спиралей равны двум последовательным числам Фибоначчи: для сосновой шишки это обычно 8 и 13, либо 13 и 21, для корзинки подсолнечника – 34 и 55, либо 55 и 89.

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