Я думаю, каждый слыхал о числах Фибоначчи: ряд чисел, в котором каждое, кроме первых двух, равно сумме двух предыдущих. Сам Леонардо Пизанский, известный под прозвищем Фибоначчи, современник Ричарда Львиное Сердце и князя Игоря, жил на сотню лет до Данте и считается первым крупным средневековым математиком Европы, а в Италии даже и одним из крупнейших вообще. О его результатах можно прочитать в Википедии, а мы давайте поговорим о его ряде.
Ряд Фибоначчи получается как решение задачи о кроликах. В модели Фибоначчи пара кроликов производит пару кроликов в месяц, начиная со второго месяца жизни. Начинаем с одной пары кроликов. Через месяц у нас все еще одна. Затем имеем эту пару и нарожденную ею пару: всего две. Потом старая пара пришлет еще одну, а новая повзрослеет: 1+2=3. И так далее: на каждом шаге имеем все пары предыдущего шага и приплод от шага на два раньше.
Математически это записывается в виде рекуррентного уравнения:
N(n) = N(n-1)+N(n-2)
с начальными условиями N(0)=1, N(1)=1.
Могут быть, кстати, и другие начальные условия и это тоже называется ряд Фибоначчи.
Как найти формулу для вычисления члена этой последовательности прямо по номеру, без вычисления предыдущих? Технику мы уже обсуждали, но не вредно и повторить: уравнение выше является линейным уравнением на множестве бесконечных последовательностей. То есть сумма двух решений есть решение, и если решение умножить на число, это будет тоже решение. И даже более того: это двумерное пространство, потому что если мы знаем первые два члена ряда, то все остальные восстанавливаются однозначно. Так что через два решения можно выразить любое другое: ведь всё определяют два первых члена ряда, двумерный вектор. То есть, надо подобрать всего два (ненулевых) решения, для каких угодно начальных данных.
Поищем решение в виде степени: N(n)=λⁿ. Подставим это в уравнение и получим для лямбды (λ) квадратное уравнение
λ² - λ - 1 = 0.
У него есть два различных вещественных корня, но они не целые и даже не рациональные. Не будем пока нервничать и запишем общее решение:
В случае начальных данных Фибоначчи получается
Что дает в итоге формулу
Получается очень поучительная вещь: задачу мы решили, формулу для n-го члена последовательности получили. Вся последовательность целочисленная, но в формуле красуются иррациональные числа. В каждом конкретном случае они сокращаются, но в формуле стоят.
Их не было в задаче про кроликов! Но они есть в ответе.
И ведь в левой части стоит размерная величина: число пар кроликов. А справа, что измеряется в кроликах? Кто скажет? Корень из пяти там чего/кого?
Важно ещё вот что. Любая последовательность Фибоначчи получается комбинацией двух каких-нибудь. Удобно брать в качестве базисных классическую, которая начинается с 1, 1, и её же, только в начале 0, 1. Потом, очевидно, будет опять 1 и далее классическая последовательность. То есть вы добавили месяц перед покупкой пары кроликов: в этот месяц у вас кроликов не было.
Тогда, если первую умножить на В, вторую на А, и сложить, то получится последовательность Фибоначчи, у которой первый член В, второй А+В, ну и далее по схеме. То есть получается по сути последовательность Фибоначчи, начинающаяся с чисел А и В. Только "нулевой член" А отбросили. Имея формулы для классической последовательности и (0,1)-последовательности, можно легко сложить любую другую, и даже вычислять ничего не надо: коэффициентами и будут первые два числа.
Есть такой фокус: попросите написать любые два числа, потом выписать восемь членов последовательности Фибоначчи с этой парой в качестве начальной, и просуммировать все десять чисел. Это довольно трудоемко. Потом Вам покажут выписанные числа и вы их мгновенно просуммируете в уме. Либо вам скажут первые два, а вы быстро назовете сумму.
Дело в том, что сумма десяти чисел Фибоначчи в 11 раз больше седьмого числа.
Проверим это. Выпишем первые 10 чисел:
A, B, A+B, A+2B, 2A+3B, 3A+5B, 5A+8B, 8A+13B, 13A+21B, 21A+34B.
Теперь сложим их: получим 55A+88B = 11(5A+8B).
Интересно проследить за отношением двух последовательных чисел Фибоначчи, при любом начальном условии. Полученная формула (общее решение) показывает, что при больших n второе слагаемое играет все меньшую роль, а первое — все большую. Дело в том, что √5 лежит между 2 и 3, так что 1-√5 лежит между -2 и -1, а половина от этой величины по модулю меньше единицы. В большой степени это мало. При этом 1+√5 лежит между 3 и 4, а половина больше единицы, так что в большой степени это много. Так что асимптотически роль играет только первое слагаемое.
Асимптотически — это при больших n. Но насколько больших — зависит от контекста. В данном случае долго ждать не придется: отношение четвертого к третьему уже близко к пределу (относительная погрешность 3%). Это для классической последовательности, конечно.
Предел отношения двух последовательных чисел не зависит от коэффициента и равен (1+√5)/2. Это число примерно равно 1.618, называется "золотое сечение", часто встречается в самых разных построениях, распространено в природе, применяется в архитектуре и почему-то выглядит привлекательно для человека.
Формально это отношение частей отрезка, разделенного так, что отношение большей части к меньшей равно отношению всего отрезка к большей части.
Это приводит к уравнению
которое сводится к
φ² = 1 + φ, где φ = y/x.
Точно такое же уравнение мы получим, обозначив через φ предел N(n)/N(n-1) и перейдя к пределу в уравнении
N(n) = N(n-1)+N(n-2),
поделив обе части предварительно на N(n-1).
У этого квадратного уравнения два корня. Один равен золотому сечению (1+√5)/2, второй ему обратен и имеет обратный знак: (1-√5)/2.
В данной пропорции делят друг друга диагонали правильного пятиугольника, которые образуют пятиконечную звезду.
Возможно, поэтому пятиугольник, звезда, пентаграмма и т.п. были всегда так популярны.
Но это тема для другой беседы.