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

Числата на Фибонàчи в математиката са елементи на числова редица, в която първите две числа са 0 и 1, а всяко следващо число се получава като сума на предходните две:

и така нататък:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, …

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

Те се дефинират рекурсивно по следния начин:

$F_{0}=0,\quad F_{1}=1,\quad F_{n}=F_{n-1}+F_{n-2}$,
където $\ n\geqslant 2,\ n\in \mathbb {Z}$.

Наречени са в чест на средновековния математик Леонардо Пизàно Биголо, известен като Леонардо Фибоначи. Понякога нулевият член $F_{0}$ се пропуска, така че редицата на Фибоначи започва с $F_{1}=F_{2}=1.$ Геометричното изображение на числата на Фибоначи са квадрати с нарастващи страни, разположени един до друг спираловидно, така че сумата от страните на два съседни квадрата е страна на следващия квадрат, както е показано на фигурите.

Спиралата на Фибоначи, съставена от кръгови дъги в квадратите от мозайката на Фибоначи, е приближение на златната спирала.

Ако в квадратите от мозайката на Фибоначи се начертаят кръгови дъги, съединяващи противоположните им ъгли, се получава спиралата на Фибоначи, която е приближение на златната спирала. Понякога числата на Фибоначи се разглеждат и за отрицателни стойности на $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_{7}$) начина за подреждане на дълги (червени) и къси срички (сиви) в каденция с дължина шест: пет ($F_{5}$) завършват с дълга сричка и осем ($F_{6}$) — с къса

Очевидно е, че $F_{-n}=(-1)^{n+1}F_{n}$.

Числата на Фибоначи могат да се бележат и с $U_{n}$.

Произход

Числата на Фибоначи са описани за първи път в индийската математика още през 200 г. пр.н.е. в труд на Пингала върху изброяването на възможни модели на санскритска поезия, образувани от срички с две дължини.

Италианският математик Леонардо Фибоначи публикува през 1202 г. редица от числа, всяко от които се получава като сума от предходните две, като първите две числа са 0 и 1: 0, 1, 1, 2, 3, 5, 8, 13, 21,… Той е научил за тази редица от числа по време на пътешествията си в страните от тогавашния Изток и редицата е била наречена на негово име, защото я е популяризирал.

Оказва се, че колкото по-големи са числата от редицата на Фибоначи, толкова отношението на двете последни числа се приближава до златното сечение и при граничен преход (при безкраен брой числа в редицата) става равно на стойността му $\varphi =1{,}61803\,\,39887\,\,49894\,\,84820\,\,45868\,\,34365\,\,63811\,\,77203\,\,09179\,\,80576\,\,\ldots$.

Често редицата на Фибоначи се свързва със следната задача, разглеждана от него за развитието на идеализирана (биологично нереалистична) популация от зайци:

Чифт зайци (мъжки и женски екземпляр) могат да произведат за единица време (напр. един месец) нов чифт зайци, които продължават да се размножават (в класическата задача на Фибоначи на новородения чифт зайци са му необходими два месеца, за да дадат първото си поколение, след което продължават да се размножават всеки месец). Колко е броят на живите чифтове зайци след определено време, ако никой не унищожава зайците? Отговорът се дава от последното число в редицата на Фибоначи. Разбира се, тази задача е чисто илюстративна:

Броят на двойките зайци образува редица на Фибоначи

• в началото на първия месец има само една новородена двойка (1);
• в края на първия месец все още има само една двойка зайци, но те вече са се чифтосали (1);
• в края на втория месец първата двойка ражда нова двойка и се чифтоса отново (2);
• в края на третия месец първата двойка ражда друга нова двойка и се чифтосва, а втората двойка само се чифтосва (3);
• в края на четвъртия месец първата двойка ражда друга нова двойка и се чифтосва, втората двойка ражда нова двойка и се чифтосва, третата двойка само се чифтосва (5);
• в края на n-тия месец броят на двойките зайци ще бъде равен на броя на двойките през предходния месец плюс броя на новородените двойки, което ще бъде същото като броя на двойките преди два месеца, т.е. $F_{n}=F_{n-2}+F_{n-1}.$

Тази задача може би е била и първата, която моделира нарастването при популация чрез степенна функция.

Оказва се обаче, че твърде много закономерности, наблюдавани в природата и в поведението на човека, могат да се опишат, макар и с някаква по-малка или по-голяма грешка, с числа от редицата на Фибоначи, въпреки че в някои случаи това обяснение може да изглежда преднамерено.

Всъщност алгоритъмът за образуване на поредното число от редицата на Фибоначи изразява факта, че следствието (последното число от реда) зависи от предисторията (причините) по конкретния за тази редица начин, а именно: последното число е сума от двете предходни числа. Така този алгоритъм се включва в категорията на т. нар. рекурентни формули. Доколко с алгоритъма на златното сечение могат да се обяснят природни и човешки феномени зависи именно от това, доколко тези явления се подчиняват на горната проста и същевременно съответстваща добре на здравия разум рекурентна зависимост на следствието от причините, които го пораждат. До Фибоначи основните алгоритми за описване на възпроизвеждащи формули са били аритметичната и геометричната прогресия.

Първите 100 числа на Фибоначи

Пореден номер Число на Фибоначи 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 11 89 12 144 13 233 14 377 15 610 16 987 17 1597 18 2584 19 4181 20 6765 21 10946 22 17711 23 28657 24 46368 25 75025 26 121393 27 196418 28 317811 29 514229 30 832040 31 1346269 32 2178309 33 3524578 34 5702887 35 9227465 36 14930352 37 24157817 38 39088169 39 63245986 40 102334155 41 165580141 42 267914296 43 433494437 44 701408733 45 1134903170 46 1836311903 47 2971215073 48 4807526976 49 7778742049 50 12586269025

Пореден номер Число на Фибоначи 51 20365011074 52 32951280099 53 53316291173 54 86267571272 55 139583862445 56 225851433717 57 365435296162 58 591286729879 59 956722026041 60 1548008755920 61 2504730781961 62 4052739537881 63 6557470319842 64 10610209857723 65 17167680177565 66 27777890035288 67 44945570212853 68 72723460248141 69 117669030460994 70 190392490709135 71 308061521170129 72 498454011879264 73 806515533049393 74 1304969544928657 75 2111485077978050 76 3416454622906707 77 5527939700884757 78 8944394323791464 79 14472334024676221 80 23416728348467685 81 37889062373143906 82 61305790721611591 83 99194853094755497 84 160500643816367088 85 259695496911122585 86 420196140727489673 87 679891637638612258 88 1100087778366101931 89 1779979416004714189 90 2880067194370816120 91 4660046610375530309 92 7540113804746346429 93 12200160415121876738 94 19740274219868223167 95 31940434634990099805 96 51680708854858323072 97 83621143489848422977 98 135301852344706746049 99 218922995834555169026 100 354224848179261915075

Тъждества

Илюстрация на формулата за сумата от квадратите на първите n числа на Фибоначи

Някои съотношения:

• $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_{n}F_{n+3}=(-1)^{n}$
• $F_{1}^{2}+F_{2}^{2}+F_{3}^{2}+\dots +F_{n}^{2}=F_{n}F_{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+1}=C_{n}^{0}+C_{n-1}^{1}+C_{n-2}^{2}+\dots$, където $C_{n}^{k}$ са биномните коефициенти.

Някои по-общи формули:

• $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_{n}F_{kn+1}$
• $F_{n}=F_{l}F_{n-l+1}+F_{l-1}F_{n-l}$

Числата на Фибоначи сe представят от стойностите на континуанта върху набор от единици:

$F_{n+1}=K_{n}(1,\dots ,1),\quad \,$ т.е.

$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}}\qquad$ и $\qquad 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_{n}^{2}-F_{n-r}F_{n+r}=(-1)^{n-r}F_{r}^{2}$.

От тъждеството на Касини следва:

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

Свойства

• Най-големият общ делител (НОД) на две числа $F_{m}$ и $F_{n}$ e число на Фибоначи с индекс НОД на индексите $m$ и $n$, т.е. $(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 също е просто число. Но дори ако $m$ е просто число, $F_{m}$ не винаги е просто число, а най-малкият контрапример е $F_{19}=4181=37\cdot 113.$ Не е известно дали множеството от числа на Фибоначи, които са прости, е безкрайно.

Последователни наклони на равнината и графика на приближенията към златното сечение, изчислени чрез деление на всяко число на Фибоначи на предходното

Числата на Фибоначи — това е сумата от „малките“ диагонали (показани с червено) на триъгълника на Паскал

• $F_{n+k}=F_{n}.F_{k-1}+F_{k}.F_{n+1}$.
• Числа с кратни индекси се делят без остатък:
  ${\frac {F_{kn}}{F_{k}}}=m$ за всяко $n$; $\quad k,n,m$ са цели числа ($k,n,m$ ∈ ℤ).
• Отношенията ${\frac {F_{n+1}}{F_{n}}}$ са приближени дроби на златното сечение φ и по-специално $\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi$.
• Числовата редица на Фибоначи е специален случай на възвратна последователност, нейният характеристичен многочлен $x^{2}-x-1$ има корени $\varphi$ и $-{\frac {1}{\varphi }}$.
• Сумите на биномните коефициенти по диагоналите на триъгълника на Паскал са числа на Фибоначи по формулата:

$F_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }{n-k \choose k}.$

• Намиране на числото на Фибоначи $F_{n}$ чрез бинома на Нютон:

$F_{n}={1 \over 2^{n-1}}\sum _{k=0}^{\lfloor n/2\rfloor }{n \choose 2k+1}5^{k}.$

• През 1964 г. е доказано че единствените точни квадрати сред числата на Фибоначи са числата на Фибоначи с индекси 0, 1, 2, 12:

$F_{0}=0^{2}=0,$ $F_{1}=1^{2}=1,$ $F_{2}=1^{2}=1,$ $F_{12}=12^{2}=144.$

• Производната функция на редицата на Фибоначи е:

$x+x^{2}+2x^{3}+3x^{4}+5x^{5}+\dots =\sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}},$
в частност, 1/998,999 = 0,001001002003005008013021…

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

$z(x,y)=2xy^{4}+x^{2}y^{3}-2x^{3}y^{2}-y^{5}-x^{4}y+2y$ върху множеството от неотрицателни цели числа $x$ и $y$.

• Произведението и частното на всеки две различни числа на Фибоначи, различни от 1, никога не са числа на Фибоначи.
• Периодът на числата на Фибоначи по модул естествено число $n$ се нарича период на Пизано Периодите на Пизано $\pi (n)$ образуват последователността

1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … .

В частност, последните цифри на числата на Фибоначи образуват периодична редица с период $\pi (10)=60$, последната двойка цифри на числата на Фибоначи образуват редица с период $\pi (100)=300$, последните три цифри имат период $\pi (1000)=1500$, последните четири имат период $\pi (10000)=15000$, последните пет имат период $\pi (100000)=150000$ и така нататък.

• Естествено число $N$ е число на Фибоначи, ако и само ако $5N^{2}+4$ или $5N^{2}-4$ е квадратно число.
• Няма аритметична прогресия с дължина, по-голяма от 3, състояща се от числа на Фибоначи.
• Числото на Фибоначи $F_{n+2}=F_{n+1}+F_{n}$ е равно на броя на наредените набори с дължина $n$ от нули и единици, в които няма две съседни единици. Освен това, $F_{n+1}$ е равно на броя на такива наредени набори, започващи с нула, а $F_{n}$ е равно на броя на такива наредени набори, започващи с единица.
• Произведението на произволни $n$ последователни числа на Фибоначи се дели на произведението на първите $n$ числа на Фибоначи.
• Безкрайната сума от реципрочните стойности на числата на Фибоначи се сближава; нейната сума („обратната константа на Фибоначи“) е равна на $3,359884...$

Приложение

Числата на Фибоначи се появяват неочаквано често в математиката, дотолкова, че има цяло списание, посветено на тяхното изучаване – „Fibonacci Quarterly“. Приложенията на числата на Фибоначи включват компютърни алгоритми като техниката за търсене на Фибоначи и структурата от данни на купчината на Фибоначи, както и графове, наречени кубове на Фибоначи, използвани за свързване на паралелни и разпределени системи. Те се появяват и в геометрични закономерности в природата, като разклоняване на дървета, подреждане на листата на стъблото (филотаксис), кълнове на плодове на ананас, цъфтеж на артишок и подреждане на прицветниците на шишарка, въпреки че не се срещат при всички видове.

Числата на Фибоначи също са силно свързани със златното сечение: формулата на Моавър – Бине изразява n-тото число на Фибоначи чрез n и златното сечение и предполага, че съотношението на две последователни числа на Фибоначи се стреми към златното сечение с увеличаване на n. Числата на Фибоначи също са тясно свързани с числата на Люка, които се подчиняват на същата рекурентна връзка и с числата на Фибоначи образуват допълваща се двойка от редици на Люка.

Връзка със златното сечение

Формула на Моавър – Бине

Явната формула за редицата на Фибоначи е открита независимо от френските математици Абрахам дьо Моавър през 1718 г. и Жак Филип Мари Бине през 1843 г. Въпреки това тя е била известна и на математиците Леонард Ойлер и Даниел Бернули междувременно; последният предоставя това, което се смята за първото доказателство през 1728 г.

$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}}$

Оттук

$F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}={\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]$

Числата ⁠$\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}}.$

Изчисляване чрез закръгляване

Тъй като ${\textstyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$ за всички n ≥ 0, числото F_n е най-близкото цяло число до ${\frac {\varphi ^{n}}{\sqrt {5}}}$. Следователно може да се намери чрез закръгляване, използвайки функцията за най-близко цяло число $\lfloor \,\cdot \,\rceil$:

$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.$

Вместо това се използва функция скобка, която дава най-големия индекс на число на Фибоначи, коeто не е по-голямо от $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$, и $\log _{10}(\varphi )=0,208987\ldots$.

Формула за приближение за големи числа

Влиянието на $\psi$ бързо се приближава до нула; например $-\psi /{\sqrt {5}}\approx +0{,}276$. Това може да се използва за съкращаване на изчислението, като просто се пропусне малкото число $-\psi ^{n}/{\sqrt {5}}$ и се закръгли останалото $\varphi ^{n}/{\sqrt {5}}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}/{\sqrt {5}}$ до най-близкото цяло число. Използвайки Гаусовата функция за закръгляване $\lfloor \,\cdot \,\rfloor$, това може да се формулира по следния начин:

$F_{n}={\Bigg \lfloor }{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}{\Bigg \rfloor }$ за всяко $n\geq 0$.

Вижте също

• Купчина на Фибоначи
• Куб на Фибоначи
• Техника за търсене на Фибоначи
• Златно сечение
• Филлотаксис

Външни препратки

Сайт с информация за числото Фи ((en))