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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Чи́сла Фибона́ччи — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS)

в которой каждое последующее число равно сумме двух предыдущих чисел. Назван этот способ именем средневекового математика Леонардо Пизанского (известного как Фибоначчи)[1]. Иногда число 0 не рассматривается как член последовательности.

Более формально, последовательность чисел Фибоначчи \left\{F_n\right\} задается линейным рекуррентным соотношением:

F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in \Z.

Иногда числа Фибоначчи рассматривают и для отрицательных значений n, как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: F_n=F_{n+2}-F_{n+1}:

n −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 0 1 2 3 4 5 6 7 8 9 10
F_n −55 34 −21 13 −8 5 −3 2 −1 1 0 1 1 2 3 5 8 13 21 34 55

Легко заметить, что \! F_{-n} = (-1)^{n+1}F_n.

Происхождение[править | править вики-текст]

Страница Книги абака (лат. Liber abaci) Фибоначчи из Национальной центральной библиотеки Флоренции.
В правом блоке демонстрируется последовательность Фибоначчи.
Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами, а значения красным цветом индо-арабскими цифрами.

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении), намного раньше, чем она стала известна в Европе.

Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что: изначально есть новорожденная пара кроликов (самец и самка), со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов, кролики никогда не умирают. Сколько пар кроликов будет через год?

  • В начале первого месяца есть только одна новорожденная пара (1).
  • В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1)
  • В конце второго месяца первая пара рождает новую пару и опять спаривается (2)
  • В конце третьего месяца первая пара рождает еще одну новую пару и спаривается, вторая пара только спаривается (3)
  • В конце четвертого месяца первая пара рождает еще одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5)

В конце n-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количество новорожденных пар, которых будет столько же, сколько пар было два месяца назад. Таким образом: F_n = F_{n-2} + F_{n-1}.

Формула Бине[править | править вики-текст]

Формула Бине выражает в явном виде значение F_n как функцию от n:

F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} = \frac{\varphi^n - (-\varphi )^{-n}}{\varphi - (-\varphi )^{-1}} = \frac{\varphi^n - (-\varphi )^{-n}}{2\varphi - 1},

где \varphi=\frac{1 + \sqrt{5}}{2} — золотое сечение. При этом \varphi\,\! и (-\varphi )^{-1}=1-\varphi\,\! являются корнями характеристического уравнения x^2-x-1=0\,\!.

Из формулы Бине следует, что для всех n\geqslant 0, F_n есть ближайшее к \frac{\varphi^n}{\sqrt{5}}\, целое число, то есть F_n = \left\lfloor\frac{\varphi^n}{\sqrt{5}}\right\rceil. В частности, при n\to\infty справедлива асимптотика F_n\sim \frac{\varphi^n}{\sqrt{5}}.

Формула Бине может быть аналитически продолжена следующим образом:

F_z = \frac{1}{\sqrt{5}} \left( \varphi^z - \frac{\cos{\pi z}}{\varphi^z} \right).

При этом соотношение  F_{z+2} = F_{z+1} + F_z выполняется для любого комплексного числа z.

Тождества[править | править вики-текст]

Геометрическое доказательство формулы для суммы квадратов первых n чисел Фибоначчи[2].
  • F_1+F_2+F_3+\dots+F_n=F_{n+2}-1
  • F_1+F_3+F_5+\dots+F_{2n-1}=F_{2n}
  • F_2+F_4+F_6+\dots+F_{2n}=F_{2n+1}-1
  • F_{n+1}F_{n+2}^{}-F_nF_{n+3}=(-1)^{n}
  • F_1^2+F_2^2+F_3^2+\dots+F_{n}^2=F_nF_{n+1}
  • F_n^2+F_{n+1}^2=F_{2n+1}
  • F_{2n}=F_{n+1}^2-F_{n-1}^2
  • F_{3n}=F_{n+1}^3+F_n^3-F_{n-1}^3
  • F_{5n}=25F_{n}^5+25(-1)^{n}F_n^3+5F_{n}

И более общие формулы:

  • F_{n+m}^{}=F_{n-1}F_{m}+F_{n}F_{m+1}=F_{n+1}F_{m+1}-F_{n-1}F_{m-1}
  • F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_nF_{kn+1}
  • F_n^{}=F_lF_{n-l+1}+F_{l-1}F_{n-l}
  • Числа Фибоначчи представляются значениями континуант на наборе единиц: F_{n+1} = K_n(1,\dots,1), то есть
F_{n+1} =
\det \begin{pmatrix} 
1 & 1    & 0 &\cdots & 0 \\
-1  & 1  & 1 &  \ddots    & \vdots\\
0   & -1   & \ddots &\ddots & 0 \\
\vdots & \ddots  & \ddots   &\ddots & 1 \\ 
0 & \cdots & 0 & -1 & 1
\end{pmatrix}, а также \ F_{n+1} =
\det \begin{pmatrix} 
1 & i    & 0 &\cdots & 0 \\
i  & 1  & i &  \ddots    & \vdots\\
0   & i   & \ddots &\ddots & 0 \\
\vdots & \ddots  & \ddots   &\ddots & i \\ 
0 & \cdots & 0 & i & 1\end{pmatrix},
где матрицы имеют размер n\times n, i — мнимая единица.
F_{n+1} = (-i)^n U_n\left(\frac{-i}{2}\right),
F_{2n+2} = U_n\left(\frac{3}{2}\right).
  • Для любого n,
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
       \begin{pmatrix} F_{n+1} & F_n \\
                       F_n   & F_{n-1} \end{pmatrix}.
(-1)^n = F_{n+1} F_{n-1} - F_n^2.

Свойства[править | править вики-текст]

  • Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. (F_m,F_n) = F_{(m,n)}. Следствия:
    • F_m делится на F_n тогда и только тогда, когда m делится на n (за исключением n=2). В частности, F_m делится на F_3=2 (то есть является чётным) только для m=3k; F_m делится на F_4=3 только для m=4k; F_m делится на F_5=5 только для m=5k и т. д.
    • F_m может быть простым только для простых m (с единственным исключением m=4). Например, число F_{13}=233 простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — F_{19}=4181=37\cdot 113. Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
на множестве неотрицательных целых чисел x и y.[4]
  • Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
  • Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность:
    1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)
    • В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
  • Натуральное число N является числом Фибоначчи тогда и только тогда, когда 5N^2 + 4 или 5N^2 - 4 является квадратом.[5]
  • Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.[6]
  • Число Фибоначчи F_{n+2}=F_{n+1}+F_n равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом F_{n+1} равно количеству таких кортежей, начинающихся с нуля, а F_n — начинающихся с единицы.
  • Число 0,112358132134… (после запятой записаны подряд идущие числа Фибоначчи) является иррациональным.[источник не указан 196 дней]
  • F_{n+1}/F_n-1=F_{n-1}/F_n (Д.Е. Трунов, Челябинская обл, гор Магнитогорск)

Вариации и обобщения[править | править вики-текст]

В других областях[править | править вики-текст]

Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространенный миф, который часто оказывается неточной подгонкой под желаемый результат[7][8].

В природе[править | править вики-текст]

В культуре[править | править вики-текст]

Числа Фибоначчи на главном вокзале Цюриха
  • Американский писатель-фантаст Дэн Браун в книге «Код да Винчи» описал анаграмму на основе последовательности Фибоначчи.
  • Светящиеся числа Фибоначчи от 1 до 55 прикреплены на дымовой трубе Turku Energia в Турку[14] и главном вокзале Цюриха[15].
  • В фильме 2009 года «Господин Никто» в реальности, где Немо не родился, адрес заброшенного дома 12358, что является частью последовательности Фибоначчи. Номер телефона 123-581-1321, по которому он должен позвонить Анне, также близок к этой последовательности (лишняя 1 в 581).
  • В фильме «Двадцать одно» (англ. 21) последовательность Фибоначчи представлена в виде надписи на торте.
  • В сериале «Связь» (англ. Touch) одна из особенностей главного героя — возможность замечать последовательность Фибоначчи в окружающем его мире.
  • «Фибоначчи» — название песни российской рок-группы «Сплин» из альбома «Обман зрения» (2012).
  • В java-игре Doom RPG для мобильных телефонов в «Проходе» после прохождения 7-го сектора есть секретная дверь, кодом которой являются числа Фибоначчи
  • Числам Фибоначчи посвящён один из шуточных лимериков Джеймса Линдона[16]
  • В финале сериала Battlestar Galactica Кара Трейс набирает числа-координаты для сверх-светового прыжка. Последовательность, что она набирает (1123, 6536, 5321), являются числами Фибоначчи, а именно: 1123 и 5321.
  • В фильме Ларса фон Триера «Нимфоманка» для главной героини числа 3 и 5 являлись самыми «запоминающимися», ибо связаны с одним из важных моментов в жизни. Далее в фильме рассказывается о Бахе и связи транскрипции его фамилии с числами Фибоначчи (Bach: B - 2 буква алфавита, A - 1, C - 3, H - 8).
  • У электронного музыканта BT есть композиция «Fibonacci Sequence». В тексте называются числа из начала последовательности (1, 1, 2, 3, 5, 8, 13, 21).

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Числа Фибоначчи — статья из Большой советской энциклопедии
  2. Фибоначчи числа // Энциклопедический словарь юного математика / Сост. Савин А. П.. — 2-е изд. — М.: Педагогика, 1989. — С. 312—314. — 352 с. — ISBN 5715502187.
  3. J H E Cohn. Square Fibonacci Numbers Etc, стр. 109–113.
  4. P. Ribenboim. The New Book of Prime Number Records. — Springer, 1996. — С. 193.
  5. Ira Gessel Problem H-187 // Fibonacci Quarterly. — 1972. — Т. 10. — С. 417–419.
  6. В. Серпинский Задача 66 // 250 задач по элементарной теории чисел. — М.: Просвещение, 1968. — 168 с.
  7. Fibonacci Flim-Flam (англ.)
  8. The Myth That Will Not Go Away (англ.)
  9. 1 2 Золотое сечение в природе
  10. Числа Фибоначчи
  11. Числа Фибоначчи
  12. Акимов О. Е. Конец науки.
  13. Г. Манукян. ПОЭЗИЯ ЧИСЕЛ ФИБОНАЧЧИ
  14. Марио Мерц Fibonacci Sequence 1-55 (фин.)
  15. Based in Villigen: Fibonacci sequence at the Zürich Hauptbahnhof
  16. Матвеев, Михаил Путешествие по ПаЛиндондромии с Джеймсом Линдоном // Знание-сила. — 2012. — № 3. — С. 110-116. — ISSN 0130-1640.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]