Последовательность Фибоначчи

Последовательность Фибоначчи — это числовая последовательность, в которой каждое последующее число равно сумме двух предыдущих. Классическая последовательность начинается с 0 и 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … В математике она обозначается как \(F_n\), где \(F_0 = 0\), \(F_1 = 1\), и для \(n \geq 2\) выполняется рекуррентное соотношение \(F_n = F_{n-1} + F_{n-2}\). Последовательность Фибоначчи является одним из фундаментальных понятий комбинаторики, теории чисел и прикладной математики, а также часто встречается в природе, архитектуре и искусстве.

История

Древние истоки

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

Леонардо Фибоначчи

В 1202 году Леонардо Пизанский (около 1170–1250), известный как Фибоначчи, опубликовал труд «Книга абака» (Liber Abaci). В одной из задач этой книги рассматривался рост популяции кроликов: «Сколько пар кроликов родится от одной пары за год, если каждая пара даёт приплод (ещё одну пару) каждый месяц, начиная со второго месяца жизни?» Решение этой задачи дало последовательность чисел: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … (в современной версии часто добавляют начальный ноль). Фибоначчи не открыл последовательность, но популяризировал её в Европе, связав с практической задачей.

Последующее развитие

В XIX веке французский математик Эдуард Люка (1842–1891) ввёл термин «числа Фибоначчи» и систематизировал их свойства. Он же разработал обобщение — последовательности Люка, которые также удовлетворяют рекуррентному соотношению \(L_n = L_{n-1} + L_{n-2}\), но с другими начальными значениями (например, \(L_0 = 2, L_1 = 1\)). В XX веке последовательность Фибоначчи стала активно применяться в алгоритмах (например, поиск Фибоначчи), криптографии и теории хаоса.

Математические свойства

Рекуррентное соотношение и формула Бине

Основное свойство последовательности — рекуррентность: \(F_n = F_{n-1} + F_{n-2}\). Для вычисления \(n\)-го члена без рекурсии используется формула Бине (названа в честь французского математика Жака Филиппа Мари Бине, 1786–1856): \[ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}, \] где \(\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\) — золотое сечение, а \(\psi = \frac{1 - \sqrt{5}}{2} \approx -0.618\). Формула показывает, что числа Фибоначчи растут экспоненциально с основанием \(\varphi\).

Золотое сечение

Отношение соседних членов последовательности \(F_{n+1} / F_n\) стремится к \(\varphi\) при \(n \to \infty\). Например, \(F_6 / F_5 = 8 / 5 = 1.6\), \(F_{10} / F_9 = 55 / 34 \approx 1.6176\), \(F_{20} / F_{19} \approx 1.6180\). Это свойство связывает последовательность Фибоначчи с золотым сечением, которое часто встречается в геометрии, архитектуре и живописи.

Делимость и свойства

• Наибольший общий делитель (НОД): \(\gcd(F_m, F_n) = F_{\gcd(m, n)}\). Например, \(\gcd(F_8, F_{12}) = \gcd(21, 144) = 3 = F_4\).
• Чётность: \(F_n\) чётно тогда и только тогда, когда \(n\) делится на 3 (например, \(F_3 = 2\), \(F_6 = 8\), \(F_9 = 34\)).
• Простые числа Фибоначчи: не все числа Фибоначчи просты. Простые числа Фибоначчи (например, 2, 3, 5, 13, 89, 233) встречаются редко; известно, что если \(F_n\) простое, то \(n\) — простое число (обратное неверно: \(F_{19} = 4181 = 37 \times 113\)).
• Сумма первых \(n\) членов: \(\sum_{k=1}^{n} F_k = F_{n+2} - 1\).
• Квадраты чисел Фибоначчи: \(F_n^2 + F_{n+1}^2 = F_{2n+1}\).

Обобщения

• Последовательность Люка: \(L_0 = 2, L_1 = 1, L_n = L_{n-1} + L_{n-2}\). Числа Люка: 2, 1, 3, 4, 7, 11, 18, 29, 47, …
• Числа трибоначчи: каждый член равен сумме трёх предыдущих (например, 0, 0, 1, 1, 2, 4, 7, 13, 24, …).
• Числа Фибоначчи с отрицательными индексами: \(F_{-n} = (-1)^{n+1} F_n\).

Применение

В математике и информатике

• Алгоритмы: поиск Фибоначчи (метод поиска в отсортированном массиве), куча Фибоначчи (структура данных для приоритетных очередей), генерация псевдослучайных чисел.
• Криптография: числа Фибоначчи используются в некоторых криптосистемах, например, в системе Фибоначчи-Люка.
• Теория чисел: свойства делимости и простоты чисел Фибоначчи применяются в доказательствах и задачах.

В природе

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

• Расположение листьев (филлотаксис): у многих растений число листьев на стебле или спиралей в соцветиях (например, подсолнечник, ананас, сосновая шишка) соответствует числам Фибоначчи (чаще 3, 5, 8, 13, 21).
• Раковины моллюсков: форма раковины наутилуса приближается к логарифмической спирали, связанной с золотым сечением.
• Ветвление деревьев: число ветвей на разных уровнях может следовать ряду Фибоначчи.

В искусстве и архитектуре

• Живопись: художники эпохи Возрождения (например, Леонардо да Винчи) использовали золотое сечение для композиции, хотя прямых доказательств применения именно чисел Фибоначчи нет.
• Архитектура: пропорции Парфенона в Афинах, пирамиды Хеопса и собора Нотр-Дам в Париже приближённо соответствуют золотому сечению.
• Музыка: в произведениях Баха, Моцарта и Бетховена иногда находят соотношения длительностей, близкие к числам Фибоначчи.

В технике и финансах

• Технический анализ: на финансовых рынках (фондовых, валютных) трейдеры используют уровни Фибоначчи (коррекции и расширения) для прогнозирования ценовых движений. Эти уровни (23.6%, 38.2%, 50%, 61.8%, 100%) основаны на отношениях чисел Фибоначчи. Эффективность метода является спорной и не подтверждена строгими научными исследованиями.
• Оптика: числа Фибоначчи применяются в конструкции волоконно-оптических линий связи для минимизации интерференции.

Критика и ограничения

Мифы о золотом сечении

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

Финансовые рынки

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

Интересные факты

• Рекорды: наибольшее известное простое число Фибоначчи (по состоянию на 2024 год) — \(F_{81839}\) (содержит более 17 000 цифр). Оно было найдено в 2001 году.
• Последовательность в культуре: числа Фибоначчи упоминаются в романе Дэна Брауна «Код да Винчи» и фильме «Пи» (1998).
• День Фибоначчи: 23 ноября (11/23 в американском формате даты) отмечается как неофициальный праздник, поскольку числа 1, 1, 2, 3 образуют начало последовательности.

Источники

• Леонардо Фибоначчи, «Книга абака» (Liber Abaci), 1202 г.
• Эдуард Люка, «Теория чисел» (Théorie des nombres), 1891 г.
• Р. Грэхем, Д. Кнут, О. Паташник, «Конкретная математика», 1994 г.
• Дж. Х. Конвей, Р. К. Гай, «Книга чисел», 1996 г.
• Статья «Fibonacci number» в энциклопедии Britannica.
• Исследования по филлотаксису: R. O. Erickson, «The Geometry of Phyllotaxis», 1983.