Числа Фибоначчи и их свойства¶

Числа Фибоначчи — это последовательность натуральных чисел, в которой каждое следующее число равно сумме двух предыдущих. Она начинается как 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 и далее. Последовательность названа в честь итальянского математика Леонардо Пизанского, известного под прозвищем Фибоначчи, который описал её в 1202 году в трактате «Liber abaci» на примере задачи о размножении кроликов. Числа Фибоначчи занимают важное место в теории чисел, комбинаторике и математическом моделировании, а также часто встречаются в описаниях природных объектов.

¶Определение и рекуррентное соотношение

Формально последовательность задаётся рекуррентным соотношением:

F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2) при n ≥ 2.

Иногда последовательность начинают с единиц: 1, 1, 2, 3, 5, 8 и так далее. Выбор начальных членов не меняет её фундаментальных свойств, а лишь сдвигает индексацию. Каждый член последовательности однозначно определяется двумя предыдущими, что делает её простейшим примером линейной рекуррентной последовательности второго порядка.

¶История

Леонардо Пизанский (около 1170 — около 1250) ввёл последовательность в европейскую математику, изучая задачу: сколько пар кроликов родится от одной пары за год, если каждая пара приносит приплод ежемесячно, начиная со второго месяца жизни. Решение задачи дало ряд чисел, который позже был назван его именем. Сам термин «числа Фибоначчи» закрепился лишь в XIX веке, его ввёл французский математик Эдуард Люка.

Отдельные элементы последовательности встречались в индийской математике задолго до Фибоначчи: они упоминаются в трудах Пингалы (около II века до н. э.) при описании метрических схем стихосложения. Однако систематическое изучение последовательности в Европе началось именно с трактата Фибоначчи.

¶Связь с золотым сечением

Отношение соседних чисел Фибоначчи F(n+1)/F(n) при стремлении n к бесконечности стремится к числу φ ≈ 1,6180339887, известному как золотое сечение. Это иррациональное число является корнем уравнения x² = x + 1. Точная формула для n-го числа Фибоначчи, называемая формулой Бине, выражает его через золотое сечение:

F(n) = (φⁿ − ψⁿ) / √5, где ψ = (1 − √5)/2 ≈ −0,618.

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

¶Свойства

Числа Фибоначчи обладают множеством примечательных свойств:

Сумма первых n чисел Фибоначчи равна F(n+2) − 1.
Сумма квадратов первых n чисел равна F(n) · F(n+1).
Каждое третье число чётно, каждое четвёртое делится на 3, каждое пятое — на 5.
Отношение F(n−1)/F(n+1) стремится к 1/φ².
Числа Фибоначчи тесно связаны с биномиальными коэффициентами: их можно представить как суммы диагоналей треугольника Паскаля.
Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи от НОД их индексов: НОД(F(m), F(n)) = F(НОД(m, n)).

Эти свойства широко применяются в задачах дискретной математики и алгоритмах.

¶Числа Фибоначчи в природе

Последовательность часто упоминается в связи с расположением листьев, лепестков и семян у растений. Число лепестков многих цветков соответствует числам Фибоначчи: у ириса — 3, у лютика — 5, у дельфиниума — 8, у календулы — 13, у астры — 21, у маргаритки — 34 или 55. Спирали в соцветиях подсолнечника и в шишках хвойных растений также образуют ряды, близкие к числам Фибоначчи. Это объясняется тем, что такое расположение обеспечивает наиболее эффективное заполнение пространства и доступ к свету.

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

¶Применение

В информатике числа Фибоначчи используются в алгоритмах поиска (например, в поиске Фибоначчи — разновидности двоичного поиска), в структурах данных (фибоначчиева куча), в генераторах псевдослучайных чисел и в анализе сложности алгоритмов. В экономике и финансах на их основе строятся инструменты технического анализа, в частности «уровни Фибоначчи» — линии, рассчитываемые по коэффициентам 0,236; 0,382; 0,5; 0,618; 0,786, которые применяются для оценки возможных уровней поддержки и сопротивления на графиках цен.

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

¶Обобщения

Существуют обобщения последовательности: числа Люка (2, 1, 3, 4, 7, 11, ...), задаваемые тем же рекуррентным соотношением при других начальных условиях; последовательности Трибоначчи, где каждый член равен сумме трёх предыдущих; обобщённые последовательности Фибоначчи с произвольными начальными значениями. Эти конструкции изучаются в комбинаторике и теории чисел.

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

23 ноября отмечается неофициальный «День Фибоначчи», поскольку дата 11/23 соответствует началу последовательности 1, 1, 2, 3.
В 1963 году была основана «Фибоначчи-ассоциация» — математическое общество, выпускающее журнал «The Fibonacci Quarterly», посвящённый изучению последовательности и её обобщений.
Числа Фибоначчи встречаются в задачах о разбиениях, в теории графов (число остовных деревьев некоторых графов) и в анализе алгоритма Евклида.

Источники: Воробьёв Н. Н. «Числа Фибоначчи»; Грэхем Р., Кнут Д., Паташник О. «Конкретная математика»; Кнут Д. «Искусство программирования»; энциклопедические материалы по теории чисел.