Фибоначиева низа

Фибоначиева низа — низа каде секој член е збир од претходните два члена. Броевите во оваа низа се нарекуваат Фибоначиеви броеви (симбол: F_n ). Првичните елементи на низата се F₁ = 1 и F₂ = 1, иако многу автори вклучуваат нулти елемент F₀ = 0. Почнувајќи од F₀, низата гласи

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... (низа A000045 во OEIS)

Квадрати со страни чии должини се последователни Фибоначиеви броеви: 1, 1, 2, 3, 5, 8, 13 и 21

Овие броеви биле присутни во индиската математика уште во стариот век. Во 200 г. п.н.е. Пингала ги опишува во дело за набројување на можните обрасци во санскритска поезија од слогови со две должини. Наречени се по италијанскиот математичар Леонардо Пизански, наречен Фибоначи, кој ја вовел низата во западноевропската математика во неговото дело „Книга за абакот“ од 1202 г.

Фибоначиевите броеви се јавуваат неочекувано често во математиката, до тој степен што постои научно списание Fibonacci Quarterly посветено на нив. Тие се применуваат во сметачките алгоритми како Фибоначиевата техника на пребарување и податочната структура „Фибоначиев куп“ и графови наречени Фибоначиеви кубови користени за меѓусебно поврзување на напоредни и распределени системи. Се јавуваат и во биологијата: разгранувањето на дрвата, распоредот на листови на дршка, плодните изданоци на ананасот, цветањето на артичоката и распоредот на припероците на шишарките (иако не кај сите видови).

Фибоначиевите броеви се исто така силно поврзани со златниот пресек: Бинеовата формула го изразува n-тиот Фибоначиев број користејќи n и златниот пресек, со што покажува дека соодносот на два последователни Фибоначиеви броја тежнее кон златниот пресек со зголемувањето на n. Фибоначиевите броеви се во блиско сродство со Ликините броеви, кои го задоволуваат истиот рекурентен однос и со Фибоначиевите броеви образуваат комплементен пар на Ликини низи.

Дефиниција

Фибоначиевата спирала: приближување на златната спирала создадено со цртање на кружни лакови што ги поврзуваат спротивните агли на квадратите во Фибоначиевото поплочување.

Фибоначиевите броеви може да се дефинираат со рекурентниот однос $$F_{0}=0,\quad F_{1}=1,$$ и $$F_{n}=F_{n-1}+F_{n-2}$$ за n > 1.

Според некои постари дефиниции, вредноста на $F_{0}=0$ се изоставува, така што низата почнува од $F_{1}=F_{2}=1$.

Првиот 21 Фибоначиев број F_n е:

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19	F20
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765

Фибоначиевата низа може да се прошири на негативни целобројни индекси следајќи го истиот рекурентен однос во негативна насока (низа A039834 во OEIS): ⁠$F_{1}=1$⁠, ⁠$F_{0}=0$⁠ и ⁠$F_{n}=F_{n+2}-F_{n+1}$⁠ for n < 0 . Речиси сите нивни својства не зависат од позитивноста или негативноста. Вредностите за позитивните и негативните индекси го задоволуваат односот: $$F_{-n}=(-1)^{n+1}F_{n}.$$

Историја

Индија

Тринаесет (F₇) начини на распоредување на долги и кратки слогови во такт со должина шест. Одум (F₆) завршуваат со краток слог, а пет (F₅) со долг.

Фибоначиевата низа се јавува во индиската математика во врска со санскритската прозодија. Во санскритската поетска традиција имало интерес да се набројат сите обрасци на долги (Д) слогови со траење од 2 единици, сопоставени со кратки (К) слогови со траење од 1 единица. Набројувајќи ги разните обрасци на последователни Д и К со дадено вкупно траење води до Фибоначиеви броеви: бројот на обрасци со траење m единици е F_m+1.

Низата ја познавал уште индискиот математичар Пингала (ок. 450 –200 п.н.е.). Синг ја наведува Пингалината криптична формула мисрау ча („се мешаат двете“) и се толкува дека бројот на обрасци за m нагласоци (F_m+1) се добива со додавање недно [К] кон F_m случаи и едно [Д] кон F_m−1 случаи. Барата Муни исто така покажува познавање на низата во делото „Натја шастра“ (ок. 100 –ок. 350). Меѓутоа, најјасно излагање на низата добиваме во делото на Вираханка (ок. 700), чија сопствена работа е изгубена, но е цитарана од Гопала (ок. 1135):

Варијациите во двата претходни метри [е варијацијата] ... На пример, за [метар на траење] од четири, при мешање на варијациите во метрите од два [и] три, добиваме пет. [ги разработува примерите 8, 13, 21] ... Вака треба да се проследи постапката за сите матра-врти [прозодиски комбинации].

Низата му била позната и на Хемачандра (ок. 1150), кој напишал дека „збирот од последниот и претпоследниот е бројот ... на следната матра-врта.“

Европа

Страница од Фибоначиевата „Книга за абакот“ со 13 ставки на Фибоначиевата низа.

Фибоначиевата низа за првпат се јавува во „Книга за абакот“ (Liber Abaci, 1202) на Леонардо Фибоначи, каде се користи за пресметување на прирастот на популацијата на зајаци. Дибоначи го разгледува прирастот на идеализирана (биолошки неостварлива) популација на зајаци, под претпоставка дека: новородениот размножувачки пар зајаци се ставени во поле; секој пар се пари на старост од еден месец, и на крајот од вториот месец секогаш раѓаат свој пар зајаци; и зајаците никогаш не умираат, туку продолжуваат бесконечно да се размножуваат. Дибоначи поставил математички проблем за зајаците: колку пара ќе има за една година?

• На крајот од првиот месец се парат, но и понатаму останува еден пар.
• На крајо од вториот месец создаваат нов пар, така што има 2 пара во полето.
• На крајот од третииот месец првичниот пар создава втор пар, но за вториот, женката допрва ќе биде бремена во претстојниот месец, така што има вкупно 3 пара.
• На крајот од четвртиот месец првичнипт пар создал уште еден нов пар, а парот роден пред два месеци исто создава прв свој пар, така што има 5 пара.

На крајот од n-тиот месец, бројот на парови е еднаков на бројот на зрели парови (т.е. бројот на парови во месец n – 2) плус бројот на парови што живееле претходниот месец (месец n – 1). Бројот во n-тиот месец е n-тиот Фибоначиев број.

Називот „Фибоначиева низа“ е воведен во XIX век од теоретичарот Едуар Лика.

Решение на Фибоначиевиот проблем со зајаците: Во растечко идеално население, бројот на парови сочинува Фибоначиева низа. На крајот од n-тиот месец, бројот на парови е еднаков на F_n.

Поврзаност со златниот пресек

Израз од затворен облик

Како секоја низа дефинирана од хомогена линеарна рекуренција со постојани коефициенти, Фибоначиевите броеви имаат израз од затворен облик. Позната е како Бинеова формула, наречена по францускиот математичар Жак Филип Мари Бине, иако веќе им била позната на Абрахам де Моавр и Даниел Бернули:

$$F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}},$$

каде ⁠$\varphi$⁠ е златниот пресек, а ⁠$\psi$⁠ е неговиот конјугат,

$${\begin{aligned}\varphi &={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}={\phantom {-}}1,61803\ldots ,\\[5mu]\psi &={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}=-0,61803\ldots .\end{aligned}}$$

Броевите ⁠$\varphi$⁠ и ⁠$\psi$⁠ се двете решенија на квадратната равенка ⁠$\textstyle x^{2}-x-1=0$⁠, т.е. ⁠$(x-\varphi )(x-\psi )=x^{2}-x-1$⁠, и затоа ги задоволуваат идентитетите ⁠$\varphi +\psi =1$⁠ и ⁠$\varphi \psi =-1$⁠.

Бидејќи $\psi =-\varphi ^{-1}$, Бинеовата формула може да се запише како

$$F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}.$$

За да се увиди врската помеѓу низата и овие константи, да забележиме дека $\varphi$ and $\psi$ исто така се корени од $x^{n}=x^{n-1}+x^{n-2},$ така што степените на $\varphi$ и $\psi$ ја задоволуваат Фибоначиевата низа. До други зборови,

$${\begin{aligned}\varphi ^{n}&=\varphi ^{n-1}+\varphi ^{n-2},\\[3mu]\psi ^{n}&=\psi ^{n-1}+\psi ^{n-2}.\end{aligned}}$$

Следува дека за сите вредности a и b, низата дефинирана од

$$U_{n}=a\varphi ^{n}+b\psi ^{n}$$

ја задоволува истата рекуренција. Ако се изберат a и b така што U₀ = 0 и U₁ = 1 тогаш добиената низа U_n мора да биде Фибоначиева низа. Ова е исто со барањето a и b да го задоволат системот на равенки:

$${\begin{aligned}a\varphi ^{0}+b\psi ^{0}&=0\\a\varphi ^{1}+b\psi ^{1}&=1\end{aligned}}$$

кој има решение

$$a={\frac {1}{\varphi -\psi }}={\frac {1}{\sqrt {5}}},\quad b=-a,$$

давајќи ја бараната формула.

Земајќи ги почетните вредности U₀ и U₁ како произволни константи го решаваме системот на равенки и до го добиваме општото решение $${\begin{aligned}a&={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{aligned}}$$ Особено, ако го избереме a = 1, тогаш n-тиот елемент на низата е блископриближен на n-тиот степен на ⁠$\varphi$⁠ за доволно големи вредности на n. Ова се јавува кога U₀ = 2 и U₁ = 1, што ја дава низата од Ликини броеви.

Пресметување со заокружување

Бидејќи ${\textstyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$ за сите n ≥ 0, бројот F_n е најблискиот цел број до ${\frac {\varphi ^{n}}{\sqrt {5}}}$. Затоа, него можеме да го најдеме со заокружување, користејќи се со најблиската целобројна функција: $$F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.$$

Впрочем, грешкат апри заокружување набргу станува мнногу мала со порастот на n, помала од 0,1 за n ≥ 4, и помала од 0,01 за n ≥ 8. Оваа формула можеме лесно да ја инвертираме за да го најдеме индексот на Фибоначиев број F: $$n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.$$

Наместо тоа, ја користиме долната цела вредност што ни го дава најголемиот индекс на Фибоначиев број кој не е поголем од F: $$n_{\mathrm {max} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,$$ каде $\log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )$, $\ln(\varphi )=0,481211\ldots$, and $\log _{10}(\varphi )=0,208987\ldots$.

Величина

Бидејќи F_n е астимтотска на $\varphi ^{n}/{\sqrt {5}}$, бројот на цифри во F_n е асимптотски на $n\log _{10}\varphi \approx 0,2090\,n$. Како последица од тоа, за секој цел број d > 1 постојат или 4 или 5 Фибоначиеви броеви со d децимални цифри.

Поопшто земено, претставено на бројната основа b, бројот на цифри во F_n е асимптотски на $n\log _{b}\varphi ={\frac {n\log \varphi }{\log b}}.$

Граница на последователни количници

Јоханес Кеплер забележал дека соодносот на последователни Фибоначиеви броеви конвергира. Напишал дека „како што е 5 спрема 8 така е 8 спрема 13, практично, и како што е 8 спрема 13, така е 13 спрема 21, речиси“, и заклучил дека овие соодноси се доближуваат до златниот пресек ⁠$\varphi$⁠: $$\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .$$

Оваа конвергенција важи без оглед на почетните вредности $U_{0}$ and $U_{1}$, освен ако $U_{1}=-U_{0}/\varphi$. Ова може да се провери со Бинеовата формула. На пример, првичните вредности 3 и 2 ја создаваат низата 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... . Соодносот на последователни елементи во оваа низа ја покажува истата конвергенција кон златниот пресек.

Општо речено, $\lim _{n\to \infty }{\frac {F_{n+m}}{F_{n}}}=\varphi ^{m}$, бидејќи соодносите меѓу последователни Фибоначиеви броеви се доближува до $\varphi$.

Разложување на степени

Бидејќи златниот пресек ја задоволува равенката $$\varphi ^{2}=\varphi +1,$$

овој израз може да послужи за разложување повисоки степени $\varphi ^{n}$ како линеарна функција од пониски степени, кои пак може да се разложат сè до линеарна комбинација од $\varphi$ и 1. Добиените рекурентни односи даваат Фибоначиеви броеви како линеарни коефициенти: $$\varphi ^{n}=F_{n}\varphi +F_{n-1}.$$ Оваа равенка може да се докаже со индукција на n ≥ 1: $${\begin{aligned}\varphi ^{n+1}&=(F_{n}\varphi +F_{n-1})\varphi =F_{n}\varphi ^{2}+F_{n-1}\varphi \\&=F_{n}(\varphi +1)+F_{n-1}\varphi =(F_{n}+F_{n-1})\varphi +F_{n}=F_{n+1}\varphi +F_{n}.\end{aligned}}$$ За $\psi =-1/\varphi$, исто така важи дека $\psi ^{2}=\psi +1$ и воедно важи дека $$\psi ^{n}=F_{n}\psi +F_{n-1}.$$

Овие изрази важат и за n < 1 доколку Фибоначиевата низа F_n се прошири на негативни цели броеви користејќи го Фибоначиевото правило $F_{n}=F_{n+2}-F_{n+1}.$

Распознавање

Бинеовата формула дава доказ дека позитивниот целоброен x е Фибоначиев број ако и само ако барем еден од $5x^{2}+4$ или $5x^{2}-4$ е совршен квадрат. Ова следува затоа што Бинеовата формула, која може да се запише како $F_{n}=(\varphi ^{n}-(-1)^{n}\varphi ^{-n})/{\sqrt {5}}$, може да се помножи со ${\sqrt {5}}\varphi ^{n}$ и да се реши како квадратна равенка во $\varphi ^{n}$ преку квадратната формула:

$$\varphi ^{n}={\frac {F_{n}{\sqrt {5}}\pm {\sqrt {5{F_{n}}^{\!2}+4{(-1)}^{n}}}}{2}}.$$

Кога ќе го споредиме тоа со $\varphi ^{n}=F_{n}\varphi +F_{n-1}=(F_{n}{\sqrt {5}}+F_{n}+2F_{n-1})/2$, следува дека

$$5{F_{n}}^{\!2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2}\,.$$

Поконкретно, левата страна е совршен квадрат.

Матричен облик

Еден дводимензионален систем на линеарни разликовни равенки што опишува Фибоначиевата низа е

$${\begin{pmatrix}F_{k+2}\\F_{k+1}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{\begin{pmatrix}F_{k+1}\\F_{k}\end{pmatrix}}$$ поинаку запишано $${\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},$$

што дава ${\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}$. Сопствените вредности на матрицата A се $\varphi ={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}$ и $\psi =-\varphi ^{-1}={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}$ што одговараат на соодветните сопствени вектори $${\vec {\mu }}={\begin{pmatrix}\varphi \\1\end{pmatrix}},\quad {\vec {\nu }}={\begin{pmatrix}-\varphi ^{-1}\\1\end{pmatrix}}.$$

Бидејќи првичната вредност е $${\vec {F}}_{0}={\begin{pmatrix}1\\0\end{pmatrix}}={\frac {1}{\sqrt {5}}}{\vec {\mu }}\,-\,{\frac {1}{\sqrt {5}}}{\vec {\nu }},$$ следува дека n-тиот елемент ќе биде $${\begin{aligned}{\vec {F}}_{n}\ &={\frac {1}{\sqrt {5}}}A^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}A^{n}{\vec {\nu }}\\&={\frac {1}{\sqrt {5}}}\varphi ^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}(-\varphi )^{-n}{\vec {\nu }}\\&={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}{\begin{pmatrix}\varphi \\1\end{pmatrix}}\,-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}{\begin{pmatrix}{c}-\varphi ^{-1}\\1\end{pmatrix}}.\end{aligned}}$$

Оттука, n-тиот елемент во Фибоначиевата низа може непосредно да се распознае како израз од затворен облик: $$F_{n}={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}.$$

Еквивалентно, истата пресметка може да се направи со дијагонализација на A при употреба на нејзиното сопствено разложување: $${\begin{aligned}A&=S\Lambda S^{-1},\\[3mu]A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}$$ каде $$\Lambda ={\begin{pmatrix}\varphi &0\\0&-\varphi ^{-1}\!\end{pmatrix}},\quad S={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}.$$ Така, изразот од затворен облик за n-тиот елемент во Фибоначиевата низа е даден од $${\begin{aligned}{\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}}&=A^{n}{\begin{pmatrix}F_{1}\\F_{0}\end{pmatrix}}\ \\&=S\Lambda ^{n}S^{-1}{\begin{pmatrix}F_{1}\\F_{0}\end{pmatrix}}\\&=S{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}S^{-1}{\begin{pmatrix}F_{1}\\F_{0}\end{pmatrix}}\\&={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}{\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&\varphi ^{-1}\\-1&\varphi \end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}},\end{aligned}}$$ што повторно дава $$F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.$$

Матрицата A има детерминанта −1, и затоа претставува 2 × 2 унимодуларна матрица.

Ова својство може да се разбере како претстава на непрекината дропка за златниот пресек φ: $$\varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\ddots }}}}}}.$$ Конвергентите на непрекинатата дропка за φ се соодноси на последователните Фибоначиеви броеви: φ_n = F_n+1 / F_n е n-тиот конвергент, а (n + 1)-виот конвергент може да се најде од рекурентниот однос φ_n+1 = 1 + 1 / φ_n. Матрицата образувана од последователни конвергенти на секоја непрекината дропка има детерминанта of +1 or −1. Матричната претстава го дава следниов израз од затворен облик за Фибоначиевите броеви: $${\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.$$ За даден n, оваа матрица може да се пресмета во O(log n) аритметички операции, користејќи го методот на степенување со квадрирање.

Ако ја земеме детерминантата од двете страни на оваа равенка го добиваме Касиниевиот идентитет, $$(-1)^{n}=F_{n+1}F_{n-1}-{F_{n}}^{2}.$$

Покрај тоа, бидејќи AⁿA^m = A^n+m за секоја квадратна матрица A, може да се изведат следните идентитети (се добиваат од два различни коефициента на матричен производ, и можеме лесно да го изведеме вториот од првиот заменувајќи го n со n + 1), $${\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\[3mu]F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.\end{aligned}}$$

Особено, со m = n, $${\begin{aligned}F_{2n-1}&={F_{n}}^{2}+{F_{n-1}}^{2}\\[6mu]F_{2n{\phantom {{}-1}}}&=(F_{n-1}+F_{n+1})F_{n}\\[3mu]&=(2F_{n-1}+F_{n})F_{n}\\[3mu]&=(2F_{n+1}-F_{n})F_{n}.\end{aligned}}$$

Последниве два идентитета ни даваат начин за пресметување на Фибоначиеви броеви рекурзивно во O(log n) аритметички операции. Ова одговара на времето за пресметување на n-тиот Фибоначиев број од матричната формула со затворен облик, но со помалку излишни чекори ако избегнеме повторна пресметка на веќе пресметан Фибоначиев број (рекурзија со мемоизација).

Комбинаторни идентитети

Комбинаторни докази

Повеќето идентитети со Фибоначиеви броеви можат да се докажат со комбинаторски аргументи според фактот што $F_{n}$ може да се толкува како бројот на (можеби празни) низи на единици и двојки чиј збир изнесува $n-1$. Ова може да се земе како дефиниција на $F_{n}$ со начините $F_{0}=0$, што значи дека не постои низа чиј збир изнесува −1, а $F_{1}=1$, што значи дека празната низа дава збир од 0. Во следново, $|{...}|$ е кардиналноста на множество:

$F_{0}=0=|\{\}|$

$F_{1}=1=|\{()\}|$

$F_{2}=1=|\{(1)\}|$

$F_{3}=2=|\{(1,1),(2)\}|$

$F_{4}=3=|\{(1,1,1),(1,2),(2,1)\}|$

$F_{5}=5=|\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|$

На овој начин рекурентниот однос $$F_{n}=F_{n-1}+F_{n-2}$$ може да се разбере како делење на $F_{n}$ низи на две непреклопувачки множества каде сите низи почнуваат со 1 или со 2: $$F_{n}=|\{(1,...),(1,...),...\}|+|\{(2,...),(2,...),...\}|$$ Изземајќи го првиот елемент, збирот на останатите членови во секоја низа изнесува $n-2$ или $n-3$, а кардиналноста на секое множество е $F_{n-1}$ или $F_{n-2}$ што дава вкупно $F_{n-1}+F_{n-2}$ низи, и покажува дека ова е еднакво на $F_{n}$.

На сличен начин можеме да покажеме дека збирот од првите Фибоначиеви броеви до n-тиот е еднаков на (n + 2)-тиот Фибоначиев број минус 1. Со симболи: $$\sum _{i=1}^{n}F_{i}=F_{n+2}-1$$

Ова се гледа со делење на сите низи што даваат збир $n+1$ според положбата на првата 2. Поконкретно, секое множество се состои од оние низи кои почнуваат $(2,...),(1,2,...),...,$ до последните две множества $\{(1,1,...,1,2)\},\{(1,1,...,1)\}$ секое со кардиналност 1.

Следејќи ја истата логика како претходно, собирајќи ја кардиналноста на секое множество увидуваме дека

$F_{n+2}=F_{n}+F_{n-1}+...+|\{(1,1,...,1,2)\}|+|\{(1,1,...,1)\}|$

... каде последните два члена ја имаат вредноста $F_{1}=1$. Оттука следува дека $\sum _{i=1}^{n}F_{i}=F_{n+2}-1$.

Сличен аргумент, групирање на збирови според положбата на првата 1 наместо првата 2, дава уште два идентитета: $$\sum _{i=0}^{n-1}F_{2i+1}=F_{2n}$$ и $$\sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.$$ Изразено со зборови, збирот на првите Фибоначиеви броеви со непарен индекс до $F_{2n-1}$ е (2n)-тиот Фибоначиев број, а збирот од првите Фибоначиеви броеви со парен индекс до $F_{2n}$ е (2n + 1)-тиот Фибоначиев број минус 1.

Можеме да се послужиме со поинаква финта за да го докажеме $$\sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}$$ или со зборови, збирот на квадратите на првите Фибоначиеви броеви до $F_{n}$ е производ од n-тите и (n + 1)-тите Фибоначиеви броеви. За да го видиме ова, почнуваме со Фибоначиев правоаголник со големина $F_{n}\times F_{n+1}$ и го разложуваме на квадрати со големина $F_{n},F_{n-1},...,F_{1}$; од ова следи идентитетот со споредување на плоштини:

Индуктивни докази

Фибоначиевите идентитети можат лесно да се докажат со математичка индукција.

На пример, да го преиспитаме $$\sum _{i=1}^{n}F_{i}=F_{n+2}-1.$$ Додаваме $F_{n+1}$ на двете страни

$\sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1$

така ја имаме формулата за $n+1$ $$\sum _{i=1}^{n+1}F_{i}=F_{n+3}-1$$

Слично на тоа, додаваме ${F_{n+1}}^{2}$ на двете страни $$\sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}$$ и добиваме $$\sum _{i=1}^{n}F_{i}^{2}+{F_{n+1}}^{2}=F_{n+1}\left(F_{n}+F_{n+1}\right)$$ $$\sum _{i=1}^{n+1}F_{i}^{2}=F_{n+1}F_{n+2}$$

Докази со Бинеовата формула

Бинеовата формула гласи $${\sqrt {5}}F_{n}=\varphi ^{n}-\psi ^{n}.$$ Со ова можеме да докажуваме Фибоначиеви идентитети.

На пример, за да докажеме дека ${\textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$ забележуваме дека левата страна помножена со ${\sqrt {5}}$ станува $${\begin{aligned}1+&\varphi +\varphi ^{2}+\dots +\varphi ^{n}-\left(1+\psi +\psi ^{2}+\dots +\psi ^{n}\right)\\&={\frac {\varphi ^{n+1}-1}{\varphi -1}}-{\frac {\psi ^{n+1}-1}{\psi -1}}\\&={\frac {\varphi ^{n+1}-1}{-\psi }}-{\frac {\psi ^{n+1}-1}{-\varphi }}\\&={\frac {-\varphi ^{n+2}+\varphi +\psi ^{n+2}-\psi }{\varphi \psi }}\\&=\varphi ^{n+2}-\psi ^{n+2}-(\varphi -\psi )\\&={\sqrt {5}}(F_{n+2}-1)\\\end{aligned}}$$ по потреба, користејќи ги фактите ${\textstyle \varphi \psi =-1}$ и ${\textstyle \varphi -\psi ={\sqrt {5}}}$ за да ги упростиме равенките.

Други идентитети

Можеме да изведеме бројни други идентитети по пат на различни методи. Еве некои од нив:

Касиниев и Каталанов идентитет

Касиниевиот идентитет вели дека $$F_{n}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}$$ Катакаловиот идентитет е воопштување: $$F_{n}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}F_{r}^{2}$$

д’Окањов идентитет

$$F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}$$ $$F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}$$ каде L_n е n-тиот Ликин број. Последниот е идентитет за удвојување на n; други идентитети од овој вид се $$F_{3n}=2F_{n}^{3}+3F_{n}F_{n+1}F_{n-1}=5F_{n}^{3}+3(-1)^{n}F_{n}$$ според Касиниевиот идентитет.

$$F_{3n+1}=F_{n+1}^{3}+3F_{n+1}F_{n}^{2}-F_{n}^{3}$$ $$F_{3n+2}={F_{n+1}}^{3}+3F_{n+1}^{2}F_{n}+F_{n}^{3}$$ $$F_{4n}=4F_{n}F_{n+1}\left(F_{n+1}^{2}+2F_{n}^{2}\right)-3F_{n}^{2}\left(F_{n}^{2}+2F_{n+1}^{2}\right)$$ Овие може да се добијат опитно користејќи сведување на мрежа, и се корисни во поставувањето на специјалниот метод на сито во бројно поле за факторизирање на Фибоначиев број.

Поопшто,

$$F_{kn+c}=\sum _{i=0}^{k}{\binom {k}{i}}F_{c-i}F_{n}^{i}F_{n+1}^{k-i}.$$

или пак

$$F_{kn+c}=\sum _{i=0}^{k}{\binom {k}{i}}F_{c+i}F_{n}^{i}F_{n-1}^{k-i}.$$

Ако ставиме k = 2 во оваа формула, повторно ги добиваме формулите на крајот од одделот Матричен облик.

Производни функции

Обична

Обичната производна функција на Фибоначиеват а низа е степенскиот ред

$$s(z)=\sum _{k=0}^{\infty }F_{k}z^{k}=0+z+z^{2}+2z^{3}+3z^{4}+5z^{5}+\cdots .$$

Оваа низа е конвергентна за секој комплексен број $z$ satisfying $|z|<1/\varphi \approx 0,618,$ и неговиот збир има единствен затворен облик:

$$s(z)={\frac {z}{1-z-z^{2}}}.$$

Ова може да се докаже со множење со ${\textstyle (1-z-z^{2})}$: $${\begin{aligned}(1-z-z^{2})s(z)&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=0}^{\infty }F_{k}z^{k+1}-\sum _{k=0}^{\infty }F_{k}z^{k+2}\\&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=1}^{\infty }F_{k-1}z^{k}-\sum _{k=2}^{\infty }F_{k-2}z^{k}\\&=0z^{0}+1z^{1}-0z^{1}+\sum _{k=2}^{\infty }(F_{k}-F_{k-1}-F_{k-2})z^{k}\\&=z,\end{aligned}}$$ каде сите членови со $z^{k}$ for $k\geq 2$ се поништуваат поради дефиницискиот Фибоначиев рекурентен однос.

Примената на $z={10}^{-n}$ ги изложува Фибоначиевите броеви преку претпоследниот број со $n$ цифри во децималното проширување на $s(z)$. На пример, $$s(10^{-3})={\frac {0,001}{0,998999}}={\frac {1000}{998999}}=000,\,001\,001\,002\,003\,005\,008\,013\,\ldots .$$

Разложувањето на парцијални дропки е дадено со $$s(z)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi z}}-{\frac {1}{1-\psi z}}\right)$$ каде ${\textstyle \varphi ={\tfrac {1}{2}}\left(1+{\sqrt {5}}\right)}$ е златниот пресек, а $\psi ={\tfrac {1}{2}}\left(1-{\sqrt {5}}\right)$ е неговиот конјугат.

Експоненцијална

Експоненцијалната производна функција на Фибоначиевата низа може да се добие и од рекурентниот однос, давајќи хомогена линеарна диференцијална равенка: $${\begin{aligned}\sum _{k=0}^{\infty }F_{k+2}{\frac {x^{k}}{k!}}={}&\sum _{k=0}^{\infty }F_{k+1}{\frac {x^{k}}{k!}}+\sum _{k=0}^{\infty }F_{k}{\frac {x^{k}}{k!}}\\F^{\prime \prime }(x)={}&F^{\prime }(x)+F(x)\end{aligned}}$$ Својствениот полином на оваа равенка е ${\textstyle r^{2}=r+1}$, чии решенија се точно златниот пресек ${\textstyle \varphi }$ и неговиот конјугат ${\textstyle \psi }$. Заедно со првичните вредности ${\textstyle F_{0}=F(0)=0}$ и ${\textstyle F_{1}=F^{\prime }(0)=1}$, експоненцијалната производна функција на Фибоначиевите броеви е дадена од целата функција $$F(x)={\frac {e^{\varphi x}-e^{\psi x}}{\sqrt {5}}}$$ Пресметката на изводите на експоненцијалната производна функција во ${\textstyle x=0}$ ја дава Бинеовата формула: $$F^{(n)}(0)=F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}$$

Реципрочни збирови

Бесконечните збирови над реципрочни Фибоначиеви броеви понекогаш можат да се пресметаат преку тета-функции. На пример, збирот на сите непарно индексирани реципрочни Фибоначиеви броеви може да се изрази како $$\sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}={\frac {\sqrt {5}}{4}}\;\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{2},$$

а збирот од квадрираните реципрочни Фибоначиеви броеви како $$\sum _{k=1}^{\infty }{\frac {1}{{F_{k}}^{2}}}={\frac {5}{24}}\!\left(\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}-\vartheta _{4}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}+1\right).$$

Ако додадеме 1 кон секој Фибоначиев број од првиот збир, го имаме и затворениот облик $$\sum _{k=1}^{\infty }{\frac {1}{1+F_{2k-1}}}={\frac {\sqrt {5}}{2}},$$

а имаме и вгнезден збир од квадрирани Фибоначиеви броеви, што ја дава реципрочната вредност на златниот пресек, $$\sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{\sum _{j=1}^{k}{F_{j}}^{2}}}={\frac {{\sqrt {5}}-1}{2}}.$$

Збирот од сите парно индексирани Фибоначиеви броеви е $$\sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}={\sqrt {5}}\left(L(\psi ^{2})-L(\psi ^{4})\right)$$ со Ламбертова низа $\textstyle L(q):=\sum _{k=1}^{\infty }{\frac {q^{k}}{1-q^{k}}},$ бидејќи $\textstyle {\frac {1}{F_{2k}}}={\sqrt {5}}\left({\frac {\psi ^{2k}}{1-\psi ^{2k}}}-{\frac {\psi ^{4k}}{1-\psi ^{4k}}}\right)\!.$

Така, реципрочната Фибоначиева константа is $$\sum _{k=1}^{\infty }{\frac {1}{F_{k}}}=\sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}+\sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}=3,359885666243\dots$$

Покрај тоа, докажано е дека овој број е ирационален од Ришар Андре-Жанен.

Милиновиот ред го дава идентитетот $$\sum _{k=0}^{\infty }{\frac {1}{F_{2^{k}}}}={\frac {7-{\sqrt {5}}}{2}},$$ кој следи од затворениот облик за неговите парцијални збирови како што N тежнее кон бесконечност: $$\sum _{k=0}^{N}{\frac {1}{F_{2^{k}}}}=3-{\frac {F_{2^{N}-1}}{F_{2^{N}}}}.$$

Прости броеви и деливост

Своства на деливост

Секој трет број од низата е парен (кратно на $F_{3}=2$) и, поопшто речено, секој k-ти број од низата е кратно на F_k. Со тоа Фибоначиевата низа е пример за низа на деливост. Всушност, Фибоначиевата низа го задоволува посилното својство на деливост $$\gcd(F_{a},F_{b},F_{c},\ldots )=F_{\gcd(a,b,c,\ldots )}\,$$ каде gcd е функцијата на најголем заеднички делител. (Овој однос е поинаков ако се користи поинаков начин на индексирање, како оној што ја отпочнува низата со ⁠$F_{0}=1$⁠ и ⁠$F_{1}=1$⁠.)

Особено, секои три последователни Фибоначиеви броеви are заемно прости по парови бидејќи истовремено $F_{1}=1$ и $F_{2}=1$. То ест,

$\gcd(F_{n},F_{n+1})=\gcd(F_{n},F_{n+2})=\gcd(F_{n+1},F_{n+2})=1$

за секој n.

Секој прост број p дели Фибоначиев број кој може да се определи според вредноста на p по модул 5. Ако p е складен со 1 или 4 по модул 5, тогаш p го дели F_p−1, и ако p е складен со 2 или 3 по модул 5, тогаш, p divides F_p+1. Останатиот случај е кога p = 5, и во овој случај p го дели F_p.

$${\begin{cases}p=5&\Rightarrow p\mid F_{p},\\p\equiv \pm 1{\pmod {5}}&\Rightarrow p\mid F_{p-1},\\p\equiv \pm 2{\pmod {5}}&\Rightarrow p\mid F_{p+1}.\end{cases}}$$

Овие случаи можат да се здружат во една неподелна формула, користејќи го Лежандровиот симбол: $$p\mid F_{p\,-~\!\left({\frac {5}{p}}\right)}.$$

Проверка на простота

Гореспоменатата формула служи за проверка на простотата во смисла дека ако $$n\mid F_{n\,-~\!\left({\frac {5}{n}}\right)},$$ каде Лежандровиот симбол е заменет со Јакобиев симбол, тогаш ова докажува дека n е прост број, и ако не важи, дека n дефинитивно не е прост. Ако n е сложен број и ја задоволува формулата, тогаш n е Фибоначиев псевдопрост број. Кога m е голем – да речеме 500-битен број – тогаш можеме да го пресметаме F_m (mod n) делотворно со матричниот облик. Затоа,

$${\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}}\equiv {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{m}{\pmod {n}}.$$ Тука матричниот степен A^m се пресметува со помош на модуларно степенување, кој може да се прилагоди за матрици.

Фибоначиеви прости броеви

Фибоначиев прост број е Фибоначиев број што е прост. Првите неколку се:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ...

Пронајдени се Фибоначиеви прости броеви со илјадници цифри, но не е познато дали ги има бесконечно многу.

F_kn е делив со F_n, така што, освен F₄ = 3, секој Фибоначиев прост број мора да има прост индекс. Бидејќи постојат произволно долги низи од сложени броеви, така постојат и произволно долги низи од сложени Фибоначиеви броеви.

Ниеден Фибоначиев број поголем од F₆ = 8 не може да се разликува за 1 од прост број.

Единствениот нетривијален квадратен Фибоначиев број е 144. Атила Пете во 2001 г. докажал дека дека постои конечен број на Фибоначиеви броеви од совршен степен. Во 2006 г. И. Бижо, М. Мињот и С, Сиксек докажале дека 8 и 144 е единствените такви нетривијални совршени броеви.

Единствените триаголни Фибоначиеви броеви се 1, 3, 21 и 55, кои ги претпоставил Вернер Хогат, а ги докажал Луо Минг.

Ниеден Фибоначиев број не може да биде совршен број. Поопшто, ниеден Фибоначиев број освен 1 не може да биде помножено совршен, и ниеден сооднос на два Фибоначиеви броја не може да биде совршен.

Прости делители

Со исклучок на 1, 8 и 144 (F₁ = F₂, F₆ и F₁₂) секој Фибоначиев број има прост множител that is not a множител of any smaller Фибоначиев број (Кармајклова теорема). Поради тоа, 8 и 144 (F₆ и F₁₂) се единствените Фибоначиеви броеви кои се производ од други Фибоначиеви броеви.

Деливоста на Фибоначиевите броеви со прост p е сврзана со Лежандровиот симбол ${\bigl (}{\tfrac {p}{5}}{\bigr )}$ кој се пресметува вака: $$\left({\frac {p}{5}}\right)={\begin{cases}0&{\text{ако }}p=5\\1&{\text{ако }}p\equiv \pm 1{\pmod {5}}\\-1&{\text{ако }}p\equiv \pm 2{\pmod {5}}.\end{cases}}$$

Ако p е прост број, тогаш $$F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}\quad {\text{и}}\quad F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}}.$$

На пример, $${\begin{aligned}{\bigl (}{\tfrac {2}{5}}{\bigr )}&=-1,&F_{3}&=2,&F_{2}&=1,\\{\bigl (}{\tfrac {3}{5}}{\bigr )}&=-1,&F_{4}&=3,&F_{3}&=2,\\{\bigl (}{\tfrac {5}{5}}{\bigr )}&=0,&F_{5}&=5,\\{\bigl (}{\tfrac {7}{5}}{\bigr )}&=-1,&F_{8}&=21,&F_{7}&=13,\\{\bigl (}{\tfrac {11}{5}}{\bigr )}&=+1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}$$

Не е познато дали постои прост p таков што

$$F_{p\,-~\!\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p^{2}}}.$$

Ваквите прости броеви (ако постојат) би се нарекувале Вол–Сун-Сунови прости броеви.

Исто така, ако p ≠ 5 е непарен прост број, тоаш: $$5{F_{\frac {p\pm 1}{2}}}^{2}\equiv {\begin{cases}{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\pm 5\right){\pmod {p}}&{\text{ако }}p\equiv 1{\pmod {4}}\\{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\mp 3\right){\pmod {p}}&{\text{ако }}p\equiv 3{\pmod {4}}.\end{cases}}$$

Пример 1. p = 7, во овој случај p ≡ 3 (mod 4) и имаме: $${\bigl (}{\tfrac {7}{5}}{\bigr )}=-1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}+3\right)=-1,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}-3\right)=-4.$$ $$F_{3}=2{\text{ и }}F_{4}=3.$$ $$5{F_{3}}^{2}=20\equiv -1{\pmod {7}}\;\;{\text{ и }}\;\;5{F_{4}}^{2}=45\equiv -4{\pmod {7}}$$

Пример 2. p = 11, во овој случај p ≡ 3 (mod 4) и имаме: $${\bigl (}{\tfrac {11}{5}}{\bigr )}=+1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}+3\right)=4,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}-3\right)=1.$$ $$F_{5}=5{\text{ и }}F_{6}=8.$$ $$5{F_{5}}^{2}=125\equiv 4{\pmod {11}}\;\;{\text{ и }}\;\;5{F_{6}}^{2}=320\equiv 1{\pmod {11}}$$

Пример 3. p = 13, во овој случај p ≡ 1 (mod 4) и имаме: $${\bigl (}{\tfrac {13}{5}}{\bigr )}=-1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {13}{5}}{\bigr )}-5\right)=-5,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {13}{5}}{\bigr )}+5\right)=0.$$ $$F_{6}=8{\text{ и }}F_{7}=13.$$ $$5{F_{6}}^{2}=320\equiv -5{\pmod {13}}\;\;{\text{ и }}\;\;5{F_{7}}^{2}=845\equiv 0{\pmod {13}}$$

Пример 4. p = 29, во овој случај p ≡ 1 (mod 4) и имаме: $${\bigl (}{\tfrac {29}{5}}{\bigr )}=+1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {29}{5}}{\bigr )}-5\right)=0,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {29}{5}}{\bigr )}+5\right)=5.$$ $$F_{14}=377{\text{ и }}F_{15}=610.$$ $$5{F_{14}}^{2}=710645\equiv 0{\pmod {29}}\;\;{\text{ и }}\;\;5{F_{15}}^{2}=1860500\equiv 5{\pmod {29}}$$

За непарен n, сите непарни прости делители на F_n се складни со 1 по модул 4, што значи дека сите непарни делители на F_n (како производи на непарни прости делители) се складни со 1 по модул 4.

На пример, $$F_{1}=1,\ F_{3}=2,\ F_{5}=5,\ F_{7}=13,\ F_{9}={\color {Red}34}=2\cdot 17,\ F_{11}=89,\ F_{13}=233,\ F_{15}={\color {Red}610}=2\cdot 5\cdot 61.$$

Сите познати множители на Фибоначиевите броеви F(i) за сите i < 50000 се собрани во релевантните збирки.

Периодичност по модул n

Ако членовите на Фибоначиевата низа се земат mod n, добиената низа е периодична со период од највеќе 6n. Должините на периодите за разни n ги образуваат т.н. Пизанови периоди. Утврдувањето на општа формула за Пизановите периоди е отворен проблем, кој како потпроблем има посебен случај на проблемот за наоѓање на мултипликативниот ред на модуларен цел број или на елемент на конечно поле. Меѓутоа, за секој еден n, Пизановиот период може да се најде како примерок на пронаоѓање на циклуси.

Воопштувања

Фибоначиевата низа е една од најпростите и најрано откриени низи дефинирани со рекурентен однос, и поточно со линеарна разликовна равенка. Сите овие низи може да се сметаат за воопштувања на Фибоначиевата низа. Особено, Бинеовата формула може да се воопшти до секоја низа која е решение на хомогена линеарна разликовна равенка со постојани коефициенти.

Еве примери кои во извесна смисла се блиски до Фибоначиевата низа:

• Воопштување на индексот до негативни цели броеви за добивање на негафибоначиевите numbers.
• Воопштување на индексот до реални броеви со изменет облик на Бинеовата формула.
• Почнување со други цели броеви. Ликини броеви имаат L₁ = 1, L₂ = 3, а L_n = L_n−1 + L_n−2. Низите без прости броеви ја користат Фибоначиевата рекурзија со други почетни точки за создавање на низи каде сите броеви се сложени.
• Поставување на бројот како линеарна функција (освен збирот) на двата претходни броја. Пеловите броеви имаат P_n = 2P_n−1 + P_n−2. Ако на коефициентот на претходната вредност му доделиме променлива вредност x, резултатот е низа од Фибоначиеви полиноми.
• Не ги собираме непосредно претходните броеви. Падовановата низа и Переновите броеви имаат P(n) = P(n − 2) + P(n − 3).
• Создавање на следниот број со собирање на 3 броја (трибоначиеви броеви), 4 броја (тетраначиеви броеви) или повеќе. Добиените низи се познати како Фибоначиеви броеви од n-чекор.

Примена

Математика

Фибоначиевите броеви се збирови од дијагоналите (со црвено) на лево подреден Паскалов триаголник.

Фибоначиевите броеви се јавуваат како збирови од биномни коефициенти во „плитките“ дијагонали на Паскаловиот триаголник: $$F_{n}=\sum _{k=0}^{\left\lfloor {\frac {n-1}{2}}\right\rfloor }{\binom {n-k-1}{k}}.$$ Ова може да се докаже со проширување на производната функција $${\frac {x}{1-x-x^{2}}}=x+x^{2}(1+x)+x^{3}(1+x)^{2}+\dots +x^{k+1}(1+x)^{k}+\dots =\sum \limits _{n=0}^{\infty }F_{n}x^{n}$$ и собирање на слични членови на $x^{n}$.

За да видиме како се користи формулата, можеме збировите да ги подредиме според бројот на присутни членови:

5	= 1+1+1+1+1
	= 2+1+1+1	= 1+2+1+1	= 1+1+2+1	= 1+1+1+2
	= 2+2+1	= 2+1+2	= 1+2+2

што е $\textstyle {\binom {5}{0}}+{\binom {4}{1}}+{\binom {3}{2}}$, каде ги избираме положбите ба k двојки од n−k−1 членови.

Примена на Фибоначиевата низа за набројување {1, 2}-ограничени композиции

Овие броеви исто така даваат решение за извесни набројувачки проблеми, од кои најчест е броењето на начини на запишување на даден број n како подреден збир од единици и двојки (наречен композиции); постојат F_n+1 начини да се изведе тоа (еквивалентно, воедно е бројот на домино-поплочувања на $2\times n$ правоаголник). На пример, постојат F₅₊₁ = F₆ = 8 начини да се качиме на скала со 5 скалила, правејќи по еден или два чекора наеднаш:

5	= 1+1+1+1+1	= 2+1+1+1	= 1+2+1+1	= 1+1+2+1	= 2+2+1
	= 1+1+1+2	= 2+1+2	= 1+2+2

Илустрацијата покажува дека 8 може да се разложи на 5 (бројот на начини да се искачат 4 скалила, проследен од единечен чекор) плус 3 (бројот на начини да се искачат 3 скалила, проследен од двоен чекор). Истата постпака се применува рекурзивно до еден чекор, кој може да се искачи на само еден начин.

Фибоначиевите броеви се среќаваат на различни начини меѓу разни двоични низи, или еквивалентно, меѓу подмножествата на дадено множество.

• Бројот на двоични низи со должина n без последователни единици е Фибоначиевиот број F_n+2. Н апример, од 16-те двоични низи со должина 4, има F₆ = 8 без последователни единици — тие се 0000, 0001, 0010, 0100, 0101, 1000, 1001 и 1010. Таквите низи се двоични претставници на фибинарни броеви. Еквивалентно, F_n+2 е бројот на подмножества S на {1, ..., n} без последователни цели броеви, т.е. оние S за кои {i, i + 1} ⊈ S за секој i. Биекција со збировите до n+1 го заменува 1 со 0, а 2 со 10, а последната нула се испушта.
• Бројот на двоични низи со должина n без непарен број од последователни единици е Фибоначиевиот број F_n+1. На пример, од 16-те двоични низи со должина 4, постојат F₅ = 5 без непарен број во последователни единици — тие се 0000, 0011, 0110, 1100, 1111. Еквивалентно, бројот на подмножества S на {1, ..., n} без непарен број на последователни цели броеви е F_n+1. Биекцијата на двата збира до n го заменува 1 со 0, а 2 со 11.
• Бројот на двоични низи со должина n без парен број на последователни нули or единици е 2F_n. На пример, од 16-те двоични низи со должина 4, постојат 2F₄ = 6 без парен број на последователни нули или единици — тие се 0001, 0111, 0101, 1000, 1010, 1110. Има еквивалентен исказ за подмножества.
• Јуриј Матијасевич успеал да покаже дека Фибоначиевите броеви може да се дефинираат со Диофантова равенка, што го довело да го реши Хилбертовиот десетти проблем.
• Фибоначиевите броеви исто така претставуваат пример за потполна низа. Ова значи дека секој позитивен цел број може да се запише како збир од Фибоначиеви броеви, каде ниеден број не се повторува.
• Меѓутоа, секој позитивен цел број може да е запише на единстен начин како збир од еден или повеќе различни Фибоначиеви броеви така што збирот нема да има два последователни Фибоначиеви броја. Ова е познато како Цекендорфова теорема, а збирот од Фибоначиеви броеви кој ги задоволува тие услови се нарекува Цекендорфово претставување. Цекендорфовото претставување на еден број може да послужи за да се добие неговото Фибоначиево кодирање.
• Почнувајќи од 5, секој втор Фибоначиев број е должината на хипотенузата на правоаголен триаголник со целобројни страни, или, со други зборови, најголемиот број во Питагорина тројка, добиен од формулата $$(F_{n}F_{n+3})^{2}+(2F_{n+1}F_{n+2})^{2}={F_{2n+3}}^{2}.$$ Низата од Питагорини триаголници добиени од оваа формула има страни со должини (3,4,5), (5,12,13), (16,30,34), (39,80,89), ... . Средната страна на секој од овие триаголници е збир од трите страни на претходниот триаголник.
• Фибоначиевиот куб е ненасочен граф со Фибоначиев број на јазли кој е предложен како мрежна топологија за напоредна обработка.
• Фибоначиевите броеви се јавуваат во лемата за прстенот, со што се докажува врската помеѓу теоремата за насложување на кругови и конформните пресликувања.

Информатика

Фибоначиево дрво со висина 6. Рамнотежните множители се со зелено; висините со црвено.

• Фибоначиевите броеви се важни во анализата на пресметковната временска сложеност на Евклидовиот алгоритам за одредување на најголем заеднички делител од два цели броја: најлошата влезна вредност за овој алгоритам е пар од последователни Фибоначиеви броеви.
• Фибоначиевите броеви се користат во повеќефазната верзија на алгоритамот за подредување со спојување каде неподредениот список се дели на два списока чии должини одговараат на последователни Фибоначиеви броеви — со делење на списокот така што двата дела ќе бидат со должина во приближниот сооднос на φ. Познатата книга „Уметноста на сметачкото програмирање“ опишува примена на полифазното подредување со спојување за уреди со магнетна лента.
• Фибоначиевото дрво е бинарно стебло чии поддрва (рекурзивно) се разликуваат по висина за точно 1. Затоа, тоа е АВЛ-дрво, со најмалку јазли за дадена висина — „најтенкото“ АВЛ-дрво. Овие дрва имаат број на темиња кои се Фибоначиев број минус еден, важен факт во анализата на АВЛ-дрвата.
• Фибоначиевите броеви се користат од некои генератори на пседвослучајни броеви.
• Фибоначиевите броеви се јавуваат во анализата на податочната структура на Фибоначиев куп.
• Еднодимензионалниот метод на оптимизација наречен Фибоначиева техника на пребарување користи Фибоначиеви броеви.
• Фибоначиевата бројна низа изборното беззагубно збивање во звучноподатотечен формат IFF 8SVX кај сметачите „Амига“. Бројната низа го компандира изворниот звучен бран слично на логаритамските методи како μ-законот.
• Некои агилни екипи користат изменета низа наречена „изменета Фибоначиева низа“ за плански покер, како алатка за проценување. Планскиот покер е формален дел од размерената агилна рамка (SAFe).
• Фибоначиево кодирање
• Негафибоначиево кодирање

Во природата

Цветна глава на жолта камилица: распореденост во 21 (сини) и 13 (тиркизни) спирали. Ваквиот распоред со последователни Фибоначиеви броеви се јавува кај најразлични растенија.

Фибоначиевата низа се јавува во природата, како кај разгранувањето на дрвата, распоредот на листовите на дршката, плотчињата на ананасот, цветањето на артичоката, листовите на многулисната алоја (Aloe polyphylla), распореденоста на шишарката, и семејната лоза на медоносните пчели. Јоханес Кеплер го забележал присуството на Фибоначиевата низа во природата, и со него го образложил петаголниот облик на некои цветови во врска со златниот пресек. Полските маргаритки најчесто имаат ливчиња во количина на Фибоначиеви броеви. Во 1830 г. Карл Фридрих Шимпер и Александар Браун откриле дека парастихиите (спирална филотаксија) на растенијата често се изразени како дропки со Фибоначиеви броеви.

Пшемислав Прушинкевич ја изнел идејата дека вистинските случаи може да се сфатат како израз на извесни алгебарски константи ограничувања на слободни групи, поточно како извесни Линденмајерови граматики.

Илустрација на Фогеловиот модел за n = 1 ... 500

Хелмут Фогел во 1979 г. предложил модел за образецот на цветчиња во главата на сончоглед. This has the form

$$\theta ={\frac {2\pi }{\varphi ^{2}}}n,\ r=c{\sqrt {n}}$$

каде n е индексниот број на цветчето, а c е константниот размерувачки множител; така, цветчињата лежат на Фермаова спирала. Аголот на разидување, околу 137,51°, е златен агол, кој ја дели кружницата со златен пресек. Бидејќи пресекот е ирационален, ниедно цветче нема сосед под точно ист агол кон средиштето, па затоа тие се ефикасно насложени. Бидејќи рационалните приближувања до златниот пресек се од обликот F( j):F( j + 1), најблиските соседи на број n на цветче се оние со n ± F( j) за истиот индекс j, што зависи од r, растојанието од средиштето. Сончогледот и сличните цветови често имаат спирали од цветчиња насочени надесно или налево во износ на соседни Фибоначиеви броеви, обично сметани од најнадворешниот опсег на полупречници.

Фибоначиевите броеви исто така се јавуваат во родословијата на пчелите (кои се хаплодиплоиди), согласно следниве правила:

• Ако јајцето е положено но не е оплодено, се раѓа мажјак (или трут кај медоносните пчели).
• Но ако јајцето е оплодено, се раѓа женка.

Така, машката пчела секогаш има еден родител, а женската два. Ако го проследиме родословието на било која машка пчела (1 пчела), таа ќе има 1 родител (1 пчела), 2 од следното поколение, 3 од тоа пред него, 5 од тоа пред него и тн. Оваа низа од броеви на родители е Фибоначиева низа. Бројот на предци на секое ниво, F_n, е бројот на женски предци, кој е F_n−1, плус бројот на машки предци, кој е F_n−2. Ова е под неостварливата претпоставка дека предците од секое ниво не се во сродство.

Слично е забележано дека бројот на можни предци на наследната линија по X-хромозом во дадено поколение на предците исто така следи Фибоначиевата низа. Машкото има X-хромозом, кој го добил од мајката, и Y-хромозом, кој го добил од таткото. Машкото се смета за „почеток“ на неговиот X-хромозом ($F_{1}=1$), и во родителското поколение, неговиот X-хромозом доаѓа од еден родител ($F_{2}=1$). Мајката на машкото добила еден X-хромозом од нејзината мајка (бабата на синот по мајка), и еден од нејзинио татко (дедото на синот по мајка), така што двајца претходници (баби/дедовци) допринеле за X-хромозомот на машкиот потомок ($F_{3}=2$). Дедото по мајка го добил неговиот X-хромозом од мајка му, а бабата по мајка ги добила нејзиниот X-хромозоми од двајцата родители, така што три прародители придонеле кон X-хромозомот на машкиот потомок ($F_{4}=3$). Пет пра-прародители придонеле за X-хромозомот на машкиот потомок ($F_{5}=5$) и тн.

Друго

• Во оптиката, кога еден светлински сноп ќе падне под агол низ две напластени проѕирни плочи од различни материјали (со различен показатели на прекршување) тој може да одбие од три површини: горната, средната и долната на двете плочи. Бројот на различни патеки на сноповите што имаат k одбивања, за k > 1, еthe k-тиот Фибоначиев број. (Меѓутоа, кога k = 1, има три патеки на одбивање, а не две, по една за секоја од трите површини.)
• Степените на Фибоначиево повлекување наоѓаат широка примена во техничка анализа за тргувањето на финансискиот пазар.
• Бидејќи множителот на претворање 1,609344 за милји во километри е близок до златниот пресек, со разложување на растојанието во милји на збир од Фибоначиеви броеви доаѓаме многу блиску до еден километар кога Фибоначиевите броеви ќе се заменат со нивните наследници. Оваа постапка се сведува на префрлање на регистар на бројна основа 2 во златнопресечна основа φ. За да претвориме од километри во милји, регистарот го поместуваме надолу по Фибоначиевата низа.
• Измерените вредности на напоните и струите во бесконечното коло на верижни отпорници (наречено и отпорничка скала или бесконечно последователно напоредно коло) следат Фибоначиева низа. Меѓурезултатите од собирањето на наизменичната низа и напоредните отпори даваат дропки сочинети од последователни Фибоначиеви броеви. Еквивалентниот отпор на целото коло е еднаков на златниот пресек.
• Браш и др. 2012 покажуваат како воопштена Фибоначиева низа може да се поврзе со полето на економијата. Особено, покажано е како воопштената Фибоначиева низа влегува во проблемите на контролната функција на динамичката оптимизација со конечен хоризонт со една состојбена и една контролна променлива. Постапката е илустрирана во примерот на Брок–Мирмановиот модел за економски раст.
• Марио Мерц ја вклучил Фибоначиевата низа во некои од неговите уметнички дела почнувајќи од 1970 г.
• Јосиф Шилингер (1895–1943) разработил систем на компонирање кој се служи со Фибоначиеви интервали во некои од неговите мелодии; нив ги сметал за музички пандан на сложената хармонија што се забележува во природата. Погл. и Фибоначиева низа § Белешки.
• Во разработката на програми Фибоначиевите броеви често се користат од агилни екипи што работат во скрум-рамка за одредување на големината на артиклите во производен заостаток.

Поврзано

• Златен пресек
• Фибоначиева спирала
• Фибоначиев збор
• Вајтхофова табела

Наводи

Наведени дела

• Ball, Keith M (2003), „8: Fibonacci's Rabbits Revisited“, Strange Curves, Counting Rabbits, and Other Mathematical Explorations, Princeton, NJ: Princeton University Press, ISBN 978-0-691-11321-0.
• Beck, Matthias; Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics, New York: Springer, ISBN 978-1-4419-7022-0.
• Bóna, Miklós (2011), A Walk Through Combinatorics (3. изд.), New Jersey: World Scientific, ISBN 978-981-4335-23-2.
• Borwein, Jonathan M.; Borwein, Peter B. (јули 1998), Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, Wiley, стр. 91–101, ISBN 978-0-471-31515-5
• Lemmermeyer, Franz (2000), Reciprocity Laws: From Euler to Eisenstein, Springer Monographs in Mathematics, New York: Springer, ISBN 978-3-540-66957-9.
• Livio, Mario (2003) [2002], The Golden Ratio: The Story of Phi, the World's Most Astonishing Number (Прво поголемо мекоподвезно. изд.), New York City: Broadway Books, ISBN 0-7679-0816-3
• Lucas, Édouard (1891), Théorie des nombres (француски), 1, Paris: Gauthier-Villars.
• Sigler, L. E. (2002), Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation, Sources and Studies in the History of Mathematics and Physical Sciences, Springer, ISBN 978-0-387-95419-6

Надворешни врски

• Фибоначиева низа на Ризницата ^?
• Фибиначиевите броеви, Теоријата на Елиот и тргувањето со хартии од вредност, Владимир Јорданов, Математички омнибус, 2021 (македонски)
• Видеопрезентација за Фибоначиевата низа и златниот пресек — ОУ „Живко Брајковски“, Скопје (YouTube) (македонски)