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

Числа Фибоначчи (также Фибоначи) — элементыпоследовательности

 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,2584, 4181, 6765, 10946, \ldots ,
 в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждоепоследующее число равно сумме двух предыдущих чисел. Названы в честьсредневекового математика Леонардо Пизанского (известного какФибоначчи).
 Более формально, последовательность чисел Фибоначчи {Fn}задаётся линейным рекуррентным соотношением:

F0=0,F1=1,Fn=Fn1+Fn2,n2,n\Z.
 Иногда числа Фибоначчи рассматривают и для отрицательных значений n,как двусторонне бесконечную последовательность, удовлетворяющую тому жерекуррентному соотношению. При этом члены с отрицательными индексамилегко получить с помощью эквивалентной формулы «назад»:Fn=Fn+2Fn+1:
n\ldots−10−9−8−7−6−5−4−3−2−1012345678910\ldots
Fn\ldots−5534−2113−85−32−11011235813213455\ldots

 Легко заметить, что Fn=(1)n+1Fn.

Происхождение


 Файл:Liber abbaci magliabf124r.jpgthumbright300pxСтраницаКниги абака Фибоначчи из Национальной центральной библиотекиФлоренции.\\В правом блоке демонстрируется последовательностьФибоначчи.\\Позиции от 0 до 12 обозначены тёмным цветом римскимицифрами, а значения красным цветом индо-арабскими цифрамидревней Индии,где она применялась в метрических науках (просодии, другими словами —стихосложении) намного раньше, чем стала известна в Европе.
 Образец длиной n может быть построен путём добавления S кобразцу длиной n-1, либо L к образцу длиной n-2; ипросодицисты показали, что число образцов длиною n являетсясуммой двух предыдущих чисел в последовательности. Дональд Кнутрассматривает этот эффект в книге «Искусство программирования».
 На Западе эта последовательность была исследована Леонардо Пизанским,известным как Фибоначчи, в его труде «Liber Abaci» (1202). Онрассматривает развитие идеализированной (биологически нереальной)популяции кроликов, предполагая, что: изначально есть новорожденная паракроликов (самец и самка); со второго месяца после своего рождениякролики начинают спариваться и каждый месяц производить новую парукроликов; кролики никогда не умирают. Сколько пар кроликов будет черезгод?

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

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

ФормулаБине


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

Fn=(1+52)n(152)n5=φn(φ)nφ(φ)1=φn(φ)n2φ1,
 где φ=1+52 — золотое сечение. При этомφ и (φ)1=1φ являются корнямихарактеристического уравнения x2x1=0.
 Из формулы Бине следует, что для всех n0, Fn естьближайшее к φn5 целое число, то естьFn=φn5. В частности,при n справедлива асимптотикаFnφn5.
 Формула Бине может быть аналитически продолжена следующим образом:

Fz=15(φzcosπzφz).
 При этом соотношение Fz+2=Fz+1+Fz выполняется для любогокомплексного числа z.

Тождества


 Файл:FibonacciBlocks.svgthumb300pxИллюстрацияформулы для суммы квадратов первых n чисел Фибоначчи.континуантна наборе единиц: Fn+1=Kn(1,,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\}, а также  Fn+1=det1i00i1i0i0i00i1,

 где матрицы имеют размер n×n, i — мнимая единица.

  • Числа Фибоначчи можно выразить через многочлены Чебышёва:


Fn+1=(i)nUn(i2),


F2n+2=Un(32).

  • Для любого n,



 \{begin\{pmatrix\} 1 \& 1 \{\{1 \& 0 \{end\{pmatrix\}\^n =

 \texttt      \{begin\{pmatrix\} F\_\{n+1\} \& F\_n \{\{\\\texttt                      F\_n   \& F\_\{n-1\} \{end\{pmatrix\}.
 :* Следствие. Подсчёт определителей даёт


(1)n=Fn+1Fn1F2n.


  • Рекуррентная формула для получения чисел Фибоначчи:



Fn+1=Fn+5F2n±42

 Знак перед коэффициентом 4 выбирается так, чтобы корень извлекалсянацело.

Свойства



  • Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть (Fm,Fn)=F(m,n). Следствия:
    • Fm делится на Fn тогда и только тогда, когда m делится на n (за исключением n=2). В частности, Fm делится на F3=2 (то есть является чётным) только для m=3k; Fm делится на F4=3 только для m=4k; Fm делится на F5=5 только для m=5k и т. д.
    • Fm может быть простым только для простых m (с единственным исключением m=4). Например, число F13=233 простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — F19=4181=37113. Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.


  • Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен x2x1 имеет корни φ и 1φ.
  • Отношения Fn+1Fn являются подходящими дробями золотого сечения ϕ и, в частности, limnFn+1Fn=φ.
  • Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы
    Fn+1=n/2k=0(nkk).
  • В 1964 году Дж. Кон (J. H. E. Cohn) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
    F0=02=0, F1=12=1, F2=12=1, F12=122=144.
  • Производящей функцией последовательности чисел Фибоначчи является:
    x+x2+2x3+3x4+5x5+=n=0Fnxn=x1xx2
  • Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена
    z(x,y)=2xy4+x2y32x3y2y5x4y+2y,


 на множестве неотрицательных целых чисел x и y.

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


  • Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность:
      1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, \ldots
    • В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.

  • Натуральное число N является числом Фибоначчи тогда и только тогда, когда 5N2+4 или 5N24 является квадратом.
  • Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.
  • Число Фибоначчи Fn+2=Fn+1+Fn равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом Fn+1 равно количеству таких кортежей, начинающихся с нуля, а Fn — начинающихся с единицы.
  • Число 0,112358132134\ldots (после запятой записаны подряд идущие числа Фибоначчи) является иррациональным.

Вариации иобобщения



  • Числа трибоначчи
  • Числа Фибоначчи являются частным случаем последовательностей Люка Fn=Un(1,1).
    • При этом их дополнением являются числа Люка Ln=Vn(1,1).

В другихобластях


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

Вприроде



  • Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи. Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи
  • Длины фаланг пальцев человека относятся примерно как числа Фибоначчи.
  • Раковины моллюсков, в частности Наутилуса, строятся по спирали, соотносящейся с рядом чисел Фибоначчи.