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

Числа Фибоначчи — это последовательность целых чисел, в которой каждый последующий элемент равен сумме двух предыдущих. Классическая последовательность Фибоначчи начинается с чисел 0 и 1, и её первые члены выглядят так: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 и так далее. Последовательность названа в честь итальянского математика Леонардо Пизанского, известного как Фибоначчи, который ввёл её в европейскую математику в XIII веке. Числа Фибоначчи обладают множеством уникальных математических свойств и встречаются в различных областях — от природы и искусства до компьютерных наук и финансов.

Определение и рекуррентная формула

Формально последовательность чисел Фибоначчи \(\{F_n\}\) задаётся рекуррентным соотношением:

\[ F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1} + F_{n-2} \quad \text{для } n \geq 2. \]

Таким образом, каждое число, начиная с третьего, является суммой двух предыдущих. Иногда в литературе последовательность начинают с \(F_1 = 1\) и \(F_2 = 1\), что эквивалентно сдвигу индекса на единицу. В таком варианте первые члены: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946.

История

Древние упоминания

Свойства чисел, близких к последовательности Фибоначчи, были известны ещё в древности. В индийской математике (VI–XII века) описывались комбинаторные задачи, связанные с ритмическими структурами в поэзии, которые приводили к последовательности, аналогичной числам Фибоначчи. В частности, индийский математик Пингала (около III–II века до н. э.) в своём трактате «Чхандас-шастра» рассматривал количество возможных последовательностей долгих и кратких слогов, что соответствует числам Фибоначчи. Позднее, в XII веке, индийский учёный Хемачандра дал явную формулу для этой последовательности.

Леонардо Пизанский (Фибоначчи)

В западноевропейской математике последовательность впервые была описана в 1202 году в книге «Liber Abaci» («Книга абака») итальянского математика Леонардо Пизанского, известного как Фибоначчи (около 1170 – около 1250). В задаче о размножении кроликов он вывел последовательность, которая теперь носит его имя. Условие задачи: пара кроликов (самец и самка) каждый месяц даёт приплод — новую пару, которая, в свою очередь, начинает размножаться со второго месяца. Число пар кроликов по месяцам образует последовательность 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946. Хотя Фибоначчи не был первым, кто открыл эту последовательность, именно его работа популяризировала её в Европе.

Дальнейшее развитие

В XIX веке французский математик Эдуард Люка ввёл термин «числа Фибоначчи» и систематически исследовал их свойства. Он также ввёл обобщённые последовательности, такие как числа Люка, которые имеют ту же рекуррентную формулу, но другие начальные значения. В XX веке числа Фибоначчи нашли применение в различных областях, включая теорию чисел, комбинаторику, алгоритмы, криптографию, биологию и финансовые рынки.

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

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

Одно из важнейших свойств последовательности Фибоначчи — её связь с золотым сечением (\(\varphi\), примерно 1,6180339887...). Отношение двух последовательных чисел Фибоначчи \(F_{n+1} / F_n\) стремится к \(\varphi\) при \(n \to \infty\). Например, 13/8 = 1,625; 21/13 ≈ 1,615; 34/21 ≈ 1,619; 55/34 ≈ 1,6176; 89/55 ≈ 1,61818. Это свойство используется в анализе рынков (уровни Фибоначчи) и в архитектуре.

Формула Бине

Существует явная формула для вычисления \(n\)-го числа Фибоначчи, известная как формула Бине (названа в честь французского математика Жака Бине, хотя она была известна ранее):

\[ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}, \]

где \(\varphi = \frac{1 + \sqrt{5}}{2}\) — золотое сечение, а \(\psi = \frac{1 - \sqrt{5}}{2} = -1/\varphi \approx -0,6180339887\). Поскольку \(|\psi| < 1\), при больших \(n\) второе слагаемое становится пренебрежимо малым, и \(F_n\) приблизительно равно \(\varphi^n / \sqrt{5}\).

Делимость и простые числа

Числа Фибоначчи обладают свойствами делимости: если \(m\) делит \(n\), то \(F_m\) делит \(F_n\). Например, \(F_3 = 2\) делит \(F_6 = 8\). Простые числа Фибоначчи — это числа Фибоначчи, которые являются простыми. Известные примеры: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073. Вопрос о бесконечности множества простых чисел Фибоначчи остаётся открытым.

Другие свойства

• Сумма первых \(n\) чисел Фибоначчи: \(F_1 + F_2 + \dots + F_n = F_{n+2} - 1\).
• Сумма квадратов первых \(n\) чисел Фибоначчи: \(F_1^2 + F_2^2 + \dots + F_n^2 = F_n \cdot F_{n+1}\).
• Каждое третье число Фибоначчи чётно, каждое четвёртое делится на 3, каждое пятое делится на 5, каждое шестое делится на 8 и т. д. (обобщение: \(F_n\) делится на \(F_m\) тогда и только тогда, когда \(n\) делится на \(m\)).
• Числа Фибоначчи можно выразить через биномиальные коэффициенты: \(F_{n+1} = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}\).

Классификация и обобщения

Числа Люка

Числа Люка определяются той же рекуррентной формулой, но с начальными значениями \(L_0 = 2\), \(L_1 = 1\). Последовательность: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127. Они также связаны с золотым сечением и имеют много общих свойств с числами Фибоначчи.

Обобщённые последовательности

Существуют обобщённые последовательности Фибоначчи, где начальные значения могут быть произвольными числами, а рекуррентное соотношение остаётся тем же. Например, последовательность Фибоначчи-Трибоначчи, где каждый член равен сумме трёх предыдущих. Также существуют последовательности с другими коэффициентами (например, \(F_n = aF_{n-1} + bF_{n-2}\)).

Отрицательные индексы

Числа Фибоначчи можно определить для отрицательных индексов, используя рекуррентное соотношение в обратную сторону: \(F_{-n} = (-1)^{n+1} F_n\). Например, \(F_{-1} = 1\), \(F_{-2} = -1\), \(F_{-3} = 2\), \(F_{-4} = -3\), \(F_{-5} = 5\), \(F_{-6} = -8\).

Применение

В природе

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

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

Золотое сечение, тесно связанное с числами Фибоначчи, используется в живописи, скульптуре и архитектуре с древних времён. Пропорции Парфенона, пирамиды Хеопса, «Витрувианский человек» Леонардо да Винчи, «Мона Лиза» — все они содержат элементы, основанные на золотом сечении. В музыке числа Фибоначчи встречаются в ритмических структурах и интервалах (например, в произведениях Баха, Моцарта, Бетховена, Дебюсси).

В компьютерных науках

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

• Поиск Фибоначчи — алгоритм поиска в отсортированном массиве, использующий числа Фибоначчи для разделения массива.
• Куча Фибоначчи — структура данных, поддерживающая операции слияния и уменьшения ключа с амортизированной оценкой O(log n).
• Генерация псевдослучайных чисел — некоторые генераторы используют рекуррентные соотношения, основанные на числах Фибоначчи.
• Кодирование Фибоначчи — способ представления чисел с помощью битов, где каждый бит соответствует числу Фибоначчи (код Фибоначчи).

В финансовых рынках

Трейдеры и аналитики используют уровни Фибоначчи (коррекции, расширения, дуги, веера) для прогнозирования ценовых движений. Уровни коррекции Фибоначчи (23,6%, 38,2%, 50%, 61,8%, 78,6%, 100%) основаны на отношениях чисел Фибоначчи. Этот инструмент является частью технического анализа, хотя его эффективность не имеет строгого научного обоснования и подвергается критике.

В криптографии

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

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

• Самое большое известное число Фибоначчи, которое является простым, — это \(F_{81839}\) (содержит 17103 цифры), открытое в 2001 году.
• В 1963 году был основан «Журнал Фибоначчи» (The Fibonacci Quarterly), посвящённый исследованиям, связанным с числами Фибоначчи и их обобщениями.
• Числа Фибоначчи встречаются в теории игр (например, в игре «Ним» с ограничением на количество снимаемых камней, где выигрышная стратегия связана с числами Фибоначчи).
• В художественной литературе числа Фибоначчи упоминаются в романе Дэна Брауна «Код да Винчи» и в фильме «Пи» (1998).

Критика и мифы

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

Источники

• Воробьёв Н. Н. «Числа Фибоначчи». — М.: Наука, 1978.
• Грэхем Р., Кнут Д., Паташник О. «Конкретная математика». — М.: Мир, 1998.
• Леонардо Пизанский (Фибоначчи). «Liber Abaci» (1202).
• Оре О. «Теория чисел и её история». — М.: Наука, 1980.
• «The Fibonacci Quarterly» — журнал, издаваемый Fibonacci Association.
• Статья «Fibonacci number» в энциклопедии MathWorld (Wolfram Research).