Фибоначиева низа — низа каде секој член е збир од претходните два члена. Броевите во оваа низа се нарекуваат Фибоначиеви броеви (симбол: ). Првичните елементи на низата се и , иако многу автори вклучуваат нулти елемент .Richard A. Brualdi, Introductory Combinatorics, Fifth edition, Pearson, 2005Peter Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994 Почнувајќи од , низата гласи 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
мини|300п|Квадрати со страни чии должини се последователни Фибоначиеви броеви: 1, 1, 2, 3, 5, 8, 13 и 21 Овие броеви биле присутни во индиската математика уште во стариот век. Во 200 г. п.н.е. Пингала ги опишува во дело за набројување на можните обрасци во санскритска поезија од слогови со две должини. Наречени се по италијанскиот математичар Леонардо Пизански, наречен Фибоначи, кој ја вовел низата во западноевропската математика во неговото дело „Книга за абакот“ од 1202 г.
Фибоначиевите броеви се јавуваат неочекувано често во математиката, до тој степен што постои научно списание Fibonacci Quarterly посветено на нив. Тие се применуваат во сметачките алгоритми како Фибоначиевата техника на пребарување и податочната структура „Фибоначиев куп“ и графови наречени Фибоначиеви кубови користени за меѓусебно поврзување на напоредни и распределени системи. Се јавуваат и во биологијата: разгранувањето на дрвата, распоредот на листови на дршка, плодните изданоци на ананасот, цветањето на артичоката и распоредот на припероците на шишарките (иако не кај сите видови).
Фибоначиевите броеви се исто така силно поврзани со златниот пресек: Бинеовата формула го изразува -тиот Фибоначиев број користејќи и златниот пресек, со што покажува дека соодносот на два последователни Фибоначиеви броја тежнее кон златниот пресек со зголемувањето на . Фибоначиевите броеви се во блиско сродство со Ликините броеви, кои го задоволуваат истиот рекурентен однос и со Фибоначиевите броеви образуваат комплементен пар на Ликини низи.
Дефиниција мини|Фибоначиевата спирала: приближување на златната спирала создадено со цртање на кружни лакови што ги поврзуваат спротивните агли на квадратите во Фибоначиевото поплочување.
Фибоначиевите броеви може да се дефинираат со рекурентниот однос
и
за .
Според некои постари дефиниции, вредноста на се изоставува, така што низата почнува од
Првиот 21 Фибоначиев број е: {| class="wikitable" style="text-align:right" ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! |- | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 |6765
Фибоначиевата низа може да се прошири на негативни целобројни индекси следајќи го истиот рекурентен однос во негативна насока : , и for . Речиси сите нивни својства не зависат од позитивноста или негативноста. Вредностите за позитивните и негативните индекси го задоволуваат односот:
Историја
Индија мини|Тринаесет () начини на распоредување на долги и кратки слогови во такт со должина шест. Одум () завршуваат со краток слог, а пет () со долг.
Фибоначиевата низа се јавува во индиската математика во врска со санскритската прозодија. Во санскритската поетска традиција имало интерес да се набројат сите обрасци на долги (Д) слогови со траење од 2 единици, сопоставени со кратки (К) слогови со траење од 1 единица. Набројувајќи ги разните обрасци на последователни Д и К со дадено вкупно траење води до Фибоначиеви броеви: бројот на обрасци со траење единици е .
Низата ја познавал уште индискиот математичар Пингала ( 450 –200 п.н.е.). Синг ја наведува Пингалината криптична формула мисрау ча („се мешаат двете“) и се толкува дека бројот на обрасци за нагласоци () се добива со додавање недно [К] кон случаи и едно [Д] кон случаи. Барата Муни исто така покажува познавање на низата во делото „Натја шастра“ ( 100 – 350). Меѓутоа, најјасно излагање на низата добиваме во делото на Вираханка ( 700), чија сопствена работа е изгубена, но е цитарана од Гопала ( 1135):
Варијациите во двата претходни метри [е варијацијата] ... На пример, за [метар на траење] од четири, при мешање на варијациите во метрите од два [и] три, добиваме пет. [ги разработува примерите 8, 13, 21] ... Вака треба да се проследи постапката за сите матра-врти [прозодиски комбинации].
Низата му била позната и на Хемачандра ( 1150), кој напишал дека „збирот од последниот и претпоследниот е бројот ... на следната матра-врта.“
Европа мини|исправено=1.25|Страница од Фибоначиевата „Книга за абакот“ со 13 ставки на Фибоначиевата низа.
Фибоначиевата низа за првпат се јавува во „Книга за абакот“ (Liber Abaci, 1202) на Леонардо Фибоначи, каде се користи за пресметување на прирастот на популацијата на зајаци. Дибоначи го разгледува прирастот на идеализирана (биолошки неостварлива) популација на зајаци, под претпоставка дека: новородениот размножувачки пар зајаци се ставени во поле; секој пар се пари на старост од еден месец, и на крајот од вториот месец секогаш раѓаат свој пар зајаци; и зајаците никогаш не умираат, туку продолжуваат бесконечно да се размножуваат. Дибоначи поставил математички проблем за зајаците: колку пара ќе има за една година?
На крајот од првиот месец се парат, но и понатаму останува еден пар. На крајо од вториот месец создаваат нов пар, така што има 2 пара во полето. На крајот од третииот месец првичниот пар создава втор пар, но за вториот, женката допрва ќе биде бремена во претстојниот месец, така што има вкупно 3 пара. На крајот од четвртиот месец првичнипт пар создал уште еден нов пар, а парот роден пред два месеци исто создава прв свој пар, така што има 5 пара.
На крајот од -тиот месец, бројот на парови е еднаков на бројот на зрели парови (т.е. бројот на парови во месец ) плус бројот на парови што живееле претходниот месец (месец ). Бројот во -тиот месец е -тиот Фибоначиев број.
Називот „Фибоначиева низа“ е воведен во XIX век од теоретичарот Едуар Лика.
мини|лево|исправено=1.5|Решение на Фибоначиевиот проблем со зајаците: Во растечко идеално население, бројот на парови сочинува Фибоначиева низа. На крајот од n-тиот месец, бројот на парови е еднаков на F
Поврзаност со златниот пресек
Израз од затворен облик Како секоја низа дефинирана од хомогена линеарна рекуренција со постојани коефициенти, Фибоначиевите броеви имаат израз од затворен облик. Extract of page 260 Позната е како Бинеова формула, наречена по францускиот математичар Жак Филип Мари Бине, иако веќе им била позната на Абрахам де Моавр и Даниел Бернули:
каде е златниот пресек, а е неговиот конјугат,
Броевите и се двете решенија на квадратната равенка , т.е. , и затоа ги задоволуваат идентитетите и .
Бидејќи , Бинеовата формула може да се запише како
За да се увиди врската помеѓу низата и овие константи, да забележиме дека and исто така се корени од така што степените на и ја задоволуваат Фибоначиевата низа. До други зборови,
Следува дека за сите вредности и , низата дефинирана од
ја задоволува истата рекуренција. Ако се изберат и така што и тогаш добиената низа мора да биде Фибоначиева низа. Ова е исто со барањето и да го задоволат системот на равенки:
кој има решение
давајќи ја бараната формула.
Земајќи ги почетните вредности и како произволни константи го решаваме системот на равенки и до го добиваме општото решение
Особено, ако го избереме , тогаш -тиот елемент на низата е блископриближен на -тиот степен на за доволно големи вредности на . Ова се јавува кога и , што ја дава низата од Ликини броеви.
Пресметување со заокружување Бидејќи за сите , бројот е најблискиот цел број до . Затоа, него можеме да го најдеме со заокружување, користејќи се со најблиската целобројна функција:
Впрочем, грешкат апри заокружување набргу станува мнногу мала со порастот на , помала од 0,1 за , и помала од 0,01 за . Оваа формула можеме лесно да ја инвертираме за да го најдеме индексот на Фибоначиев број :
Наместо тоа, ја користиме долната цела вредност што ни го дава најголемиот индекс на Фибоначиев број кој не е поголем од :
каде , , and .
Величина Бидејќи F е асимтотска на , бројот на цифри во е асимптотски на . Како последица од тоа, за секој цел број постојат или 4 или 5 Фибоначиеви броеви со децимални цифри.
Поопшто земено, претставено на бројната основа , бројот на цифри во е асимптотски на
Граница на последователни количници Јоханес Кеплер забележал дека соодносот на последователни Фибоначиеви броеви конвергира. Напишал дека „како што е 5 спрема 8 така е 8 спрема 13, практично, и како што е 8 спрема 13, така е 13 спрема 21, речиси“, и заклучил дека овие соодноси се доближуваат до златниот пресек :
Оваа конвергенција важи без оглед на почетните вредности and , освен ако . Ова може да се провери со Бинеовата формула. На пример, првичните вредности 3 и 2 ја создаваат низата 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... . Соодносот на последователни елементи во оваа низа ја покажува истата конвергенција кон златниот пресек.
Општо речено, , бидејќи соодносите меѓу последователни Фибоначиеви броеви се доближува до .
Разложување на степени Бидејќи златниот пресек ја задоволува равенката
овој израз може да послужи за разложување повисоки степени како линеарна функција од пониски степени, кои пак може да се разложат сè до линеарна комбинација од и 1. Добиените рекурентни односи даваат Фибоначиеви броеви како линеарни коефициенти:
Оваа равенка може да се докаже со индукција на :
За , исто така важи дека и воедно важи дека
Овие изрази важат и за доколку Фибоначиевата низа F се прошири на негативни цели броеви користејќи го Фибоначиевото правило
Распознавање Бинеовата формула дава доказ дека позитивниот целоброен е Фибоначиев број ако и само ако барем еден од или е совршен квадрат. Ова следува затоа што Бинеовата формула, која може да се запише како , може да се помножи со и да се реши како квадратна равенка во преку квадратната формула:
Кога ќе го споредиме тоа со , следува дека
Поконкретно, левата страна е совршен квадрат.
Матричен облик Еден дводимензионален систем на линеарни разликовни равенки што опишува Фибоначиевата низа е
поинаку запишано
што дава . Сопствените вредности на матрицата се и што одговараат на соодветните сопствени вектори
Бидејќи првичната вредност е
следува дека -тиот елемент ќе биде
Оттука, -тиот елемент во Фибоначиевата низа може непосредно да се распознае како израз од затворен облик:
Еквивалентно, истата пресметка може да се направи со дијагонализација на при употреба на нејзиното сопствено разложување:
каде
Така, изразот од затворен облик за -тиот елемент во Фибоначиевата низа е даден од
што повторно дава
Матрицата има детерминанта −1, и затоа претставува унимодуларна матрица.
Ова својство може да се разбере како претстава на непрекината дропка за златниот пресек :
Конвергентите на непрекинатата дропка за се соодноси на последователните Фибоначиеви броеви: е -тиот конвергент, а -виот конвергент може да се најде од рекурентниот однос . Матрицата образувана од последователни конвергенти на секоја непрекината дропка има детерминанта of +1 or −1. Матричната претстава го дава следниов израз од затворен облик за Фибоначиевите броеви:
За даден , оваа матрица може да се пресмета во аритметички операции, користејќи го методот на степенување со квадрирање.
Ако ја земеме детерминантата од двете страни на оваа равенка го добиваме Касиниевиот идентитет,
Покрај тоа, бидејќи за секоја квадратна матрица , може да се изведат следните идентитети (се добиваат од два различни коефициента на матричен производ, и можеме лесно да го изведеме вториот од првиот заменувајќи го со ),
Особено, со ,
Последниве два идентитета ни даваат начин за пресметување на Фибоначиеви броеви рекурзивно во аритметички операции. Ова одговара на времето за пресметување на -тиот Фибоначиев број од матричната формула со затворен облик, но со помалку излишни чекори ако избегнеме повторна пресметка на веќе пресметан Фибоначиев број (рекурзија со мемоизација).
Комбинаторни идентитети
Комбинаторни докази