Bdtyk

Чи́сла Фибона́ччи (иногда пишут Фибона́чи^[1]) — элементы числовой последовательности

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

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

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

F0=0,F1=1,Fn=Fn−1+Fn−2,n⩾2,n∈Z.{displaystyle F_{0}=0,qquad F_{1}=1,qquad F_{n}=F_{n-1}+F_{n-2},quad ngeqslant 2,quad nin mathbb {Z} .}

Иногда числа Фибоначчи рассматривают и для отрицательных значений n{displaystyle n}, как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: Fn=Fn+2−Fn+1{displaystyle 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	…
Fn{displaystyle 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+1Fn{displaystyle 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{displaystyle n}-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количество новорождённых пар, которых будет столько же, сколько пар было два месяца назад. Таким образом:
Fn=Fn−2+Fn−1.{displaystyle F_{n}=F_{n-2}+F_{n-1}.}

Формула Бине |

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

Fn=(1+52)n−(1−52)n5=φn−(−φ)−nφ−(−φ)−1=φn−(−φ)−n2φ−1,{displaystyle 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}}{2varphi -1}},}

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

Из формулы Бине следует, что для всех n⩾0{displaystyle ngeqslant 0}, Fn{displaystyle F_{n}} есть ближайшее к φn5{displaystyle {frac {varphi ^{n}}{sqrt {5}}}} целое число, то есть Fn=⌊φn5⌉{displaystyle F_{n}=leftlfloor {frac {varphi ^{n}}{sqrt {5}}}rightrceil }. В частности, при n→∞{displaystyle nto infty } справедлива асимптотика Fn∼φn5{displaystyle F_{n}sim {frac {varphi ^{n}}{sqrt {5}}}}.

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

Fz=15(φz−cos⁡πzφz).{displaystyle F_{z}={frac {1}{sqrt {5}}}left(varphi ^{z}-{frac {cos {pi z}}{varphi ^{z}}}right).}

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

Тождества |

Иллюстрация формулы для суммы квадратов первых n чисел Фибоначчи^[3].

• F1+F2+F3+⋯+Fn=Fn+2−1{displaystyle F_{1}+F_{2}+F_{3}+dots +F_{n}=F_{n+2}-1}


• F1+F3+F5+⋯+F2n−1=F2n{displaystyle F_{1}+F_{3}+F_{5}+dots +F_{2n-1}=F_{2n}}


• F2+F4+F6+⋯+F2n=F2n+1−1{displaystyle F_{2}+F_{4}+F_{6}+dots +F_{2n}=F_{2n+1}-1}


• Fn+1Fn+2−FnFn+3=(−1)n{displaystyle F_{n+1}F_{n+2}^{}-F_{n}F_{n+3}=(-1)^{n}}


• 
  F12+F22+F32+⋯+Fn2=FnFn+1{displaystyle F_{1}^{2}+F_{2}^{2}+F_{3}^{2}+dots +F_{n}^{2}=F_{n}F_{n+1}} (см. рис.)


• Fn2+Fn+12=F2n+1{displaystyle F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}}


• F2n=Fn+12−Fn−12{displaystyle F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}}


• F3n=Fn+13+Fn3−Fn−13{displaystyle F_{3n}=F_{n+1}^{3}+F_{n}^{3}-F_{n-1}^{3}}


• F5n=25Fn5+25(−1)nFn3+5Fn{displaystyle F_{5n}=25F_{n}^{5}+25(-1)^{n}F_{n}^{3}+5F_{n}}


• Fn+1=Cn0+Cn−11+Cn−22+...{displaystyle F_{n+1}=C_{n}^{0}+C_{n-1}^{1}+C_{n-2}^{2}+...}

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

• Fn+m=Fn−1Fm+FnFm+1=Fn+1Fm+1−Fn−1Fm−1{displaystyle 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=Fn−1Fkn+FnFkn+1{displaystyle F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_{n}F_{kn+1}}


• Fn=FlFn−l+1+Fl−1Fn−l{displaystyle F_{n}^{}=F_{l}F_{n-l+1}+F_{l-1}F_{n-l}}


• Числа Фибоначчи представляются значениями континуант на наборе единиц: Fn+1=Kn(1,…,1){displaystyle F_{n+1}=K_{n}(1,dots ,1)}, то есть

Fn+1=det(110⋯0−111⋱⋮0−1⋱⋱0⋮⋱⋱⋱10⋯0−11){displaystyle 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&1end{pmatrix}}}, а также  Fn+1=det(1i0⋯0i1i⋱⋮0i⋱⋱0⋮⋱⋱⋱i0⋯0i1){displaystyle 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&1end{pmatrix}}},

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

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

Fn+1=(−i)nUn(−i2),{displaystyle F_{n+1}=(-i)^{n}U_{n}left({frac {-i}{2}}right),}

F2n+2=Un(32).{displaystyle F_{2n+2}=U_{n}left({frac {3}{2}}right).}

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

(1110)n=(Fn+1FnFnFn−1).{displaystyle {begin{pmatrix}1&1\1&0end{pmatrix}}^{n}={begin{pmatrix}F_{n+1}&F_{n}\F_{n}&F_{n-1}end{pmatrix}}.}

• 
  Следствие. Подсчёт определителей даёт

(−1)n=Fn+1Fn−1−Fn2.{displaystyle (-1)^{n}=F_{n+1}F_{n-1}-F_{n}^{2}.}

• Fn+1=Fn+5Fn2+4(−1)n2{displaystyle F_{n+1}={frac {F_{n}+{sqrt {5F_{n}^{2}+4(-1)^{n}}}}{2}}}

Свойства |

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


• Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен x2−x−1{displaystyle x^{2}-x-1} имеет корни φ{displaystyle varphi } и −1φ{displaystyle -{frac {1}{varphi }}}.


• Отношения Fn+1Fn{displaystyle {frac {F_{n+1}}{F_{n}}}} являются подходящими дробями золотого сечения ϕ{displaystyle phi } и, в частности, limn→∞Fn+1Fn=φ.{displaystyle lim _{nto infty }{frac {F_{n+1}}{F_{n}}}=varphi .}
  


• Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы
  

  
  Fn+1=∑k=0⌊n/2⌋(n−kk){displaystyle F_{n+1}=sum _{k=0}^{lfloor n/2rfloor }{n-k choose k}}.

  
  


• В 1964 году Дж. Кон (J. H. E. Cohn) доказал,^[4] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
  

  
  F0=02=0{displaystyle F_{0}=0^{2}=0}, F1=12=1{displaystyle F_{1}=1^{2}=1}, F2=12=1{displaystyle F_{2}=1^{2}=1}, F12=122=144{displaystyle F_{12}=12^{2}=144}.

  
  


• 
  Производящей функцией последовательности чисел Фибоначчи является:
  

  x+x2+2x3+3x4+5x5+⋯=∑n=0∞Fnxn=x1−x−x2{displaystyle x+x^{2}+2x^{3}+3x^{4}+5x^{5}+dots =sum _{n=0}^{infty }F_{n}x^{n}={frac {x}{1-x-x^{2}}}}

  
  


• Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена
  

  z(x,y)=2xy4+x2y3−2x3y2−y5−x4y+2y,{displaystyle z(x,y)=2xy^{4}+x^{2}y^{3}-2x^{3}y^{2}-y^{5}-x^{4}y+2y,}

  
  

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

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


• Период чисел Фибоначчи по модулю натурального числа 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 является числом Фибоначчи тогда и только тогда, когда 5N2+4{displaystyle 5N^{2}+4} или 5N2−4{displaystyle 5N^{2}-4} является квадратом.^[6]
  


• Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.^[7]
  


• Число Фибоначчи Fn+2=Fn+1+Fn{displaystyle F_{n+2}=F_{n+1}+F_{n}} равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом Fn+1{displaystyle F_{n+1}} равно количеству таких кортежей, начинающихся с нуля, а Fn{displaystyle F_{n}} — начинающихся с единицы.


• Произведение любых n{displaystyle n} подряд идущих чисел Фибоначчи делится на произведение первых n{displaystyle n} чисел Фибоначчи.


• Число 0,112358132134… (после запятой записаны подряд идущие числа Фибоначчи) является иррациональным.^{[источник не указан 1742 дня]}
  

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

• Числа трибоначчи


• Числа Фибоначчи являются частным случаем последовательностей Люка Fn=Un(1,−1){displaystyle F_{n}=U_{n}(1,-1)}.
  
  • При этом их дополнением являются числа Люка Ln=Vn(1,−1){displaystyle L_{n}=V_{n}(1,-1)}.
  
  

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

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

В природе |

• 
  Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи. Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи^{[10][11][12][13]}
  


• Длины фаланг пальцев человека относятся примерно как числа Фибоначчи^[10][14].


• Раковины моллюсков, в частности Наутилуса, строятся по спирали, соотносящейся^[как?] с рядом чисел Фибоначчи.^{[источник не указан 1010 дней]}
  

См. также |

• Дерево Фибоначчи


• Метод Фибоначчи с запаздываниями


• Метод Фибоначчи поиска экстремума


• Фибоначчи


• Фибоначчиева система счисления


• Числа Бине


• Числа Леонардо


• Таблица Витхоффа


• Последовательность коров Нараяны


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

Примечания |

Литература |

• Н. Н. Воробьёв. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).


• А. И. Маркушевич. Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).


• А. Н. Рудаков. Числа Фибоначчи и простота числа 2¹²⁷-1 // Математическое Просвещение, третья серия. — 2000. — Т. 4.


• Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4.


• Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7.


• 
  Грант Аракелян. Математика и история золотого сечения. — М.: Логос, 2014. — С. 404. — ISBN 978-5-98704-663-0.

Ссылки |

	Числа Фибоначчи в Викиучебнике
	Числа Фибоначчи на Викискладе

• 
  Первые 300 чисел Фибоначчи (англ.).


• 
  Числа Фибоначчи в природе (англ.).