Ciąg Fibonacciego

Wykres funkcji dla pierwszych ośmiu wyrazów ciągu Fibonacciego $(F_{0}\dots F_{7})$

Ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący:

Pierwszy wyraz jest równy 0, drugi jest równy 1, każdy następny jest sumą dwóch poprzednich.

Formalnie:

$F_{n}:={\begin{cases}0&{\text{dla }}n=0;\\1&{\text{dla }}n=1;\\F_{n-1}+F_{n-2}&{\text{dla }}n>1.\end{cases}}$

Kolejne wyrazy tego ciągu nazywane są liczbami Fibonacciego. Zaliczanie zera do elementów ciągu Fibonacciego zależy od umowy – część autorów definiuje ciąg od $F_{1}=F_{2}=1$.

Pierwsze dwadzieścia wyrazów ciągu Fibonacciego to:

$F_{0}$	$F_{1}$	$F_{2}$	$F_{3}$	$F_{4}$	$F_{5}$	$F_{6}$	$F_{7}$	$F_{8}$	$F_{9}$	$F_{10}$	$F_{11}$	$F_{12}$	$F_{13}$	$F_{14}$	$F_{15}$	$F_{16}$	$F_{17}$	$F_{18}$	$F_{19}$
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

Ciąg został omówiony w roku 1202 przez Leonarda z Pizy, zwanego Fibonaccim, w dziele Liber abaci jako rozwiązanie zadania o rozmnażaniu się królików. Nazwę „ciąg Fibonacciego” spopularyzował w XIX w. Édouard Lucas.

Wzór Bineta

Jawny wzór na n-ty wyraz ciągu Fibonacciego podany w roku 1843 przez J.P.M. Bineta możemy otrzymać, korzystając z metody funkcji tworzących.

Niech

$f_{n}=F_{n+1}.$

Funkcja tworząca dla tego ciągu ma postać

$s(x)=\sum _{n=0}^{\infty }f_{n}x^{n}.$

Podstawiając $f_{n}=f_{n-1}+f_{n-2}$ otrzymujemy:

${\begin{aligned}s(x)&=1+x+\sum _{n=2}^{\infty }\left(f_{n-2}+f_{n-1}\right)x^{n}\\&=1+x+x^{2}\sum _{n=2}^{\infty }f_{n-2}x^{n-2}+x\sum _{n=2}^{\infty }f_{n-1}x^{n-1}\\&=1+x+x^{2}s(x)+x(s(x)-1)=1+xs(x)+x^{2}s(x).\end{aligned}}$

W szczególności,

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

Wyrażenie ${\frac {1}{1-x-x^{2}}}$ można przedstawić w prostszej postaci, mianowicie:

${\frac {1}{1-x-x^{2}}}=A/(1-ax)+B/(1-bx),$

gdzie:

$a={\frac {1+{\sqrt {5}}}{2}},$

$b={\frac {1-{\sqrt {5}}}{2}},$

$A={\frac {a}{a-b}},$

$B={\frac {-b}{a-b}}.$

Wówczas:

$s(x)=A\sum _{n=0}^{\infty }a^{n}x^{n}+B\sum _{n=0}^{\infty }b^{n}x^{n}=\sum _{n=0}^{\infty }{\frac {(a^{n+1}-b^{n+1})}{(a-b)}}x^{n},$

a stąd:

$f_{n}={\frac {(a^{n+1}-b^{n+1})}{(a-b)}}.$

Ponieważ $F_{n}=f_{n-1},$ wyprowadzony został ostatecznie tzw. wzór Bineta zwany czasem wzorem Eulera-Bineta:

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

Ponieważ drugi człon tego wyrażenia szybko zbiega do zera

$F_{n}\approx {\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}.$

Znaczenia kombinatoryczne

• liczba ciągów o wyrazach równych 1 lub 2, które sumują się do liczby $n$ jest równa $F_{n+1};$
• liczba pokryć planszy $2\times n$ kostkami domina $2\times 1$ jest równa $F_{n+1};$
• liczba ciągów binarnych bez kolejnych jedynek (równoważnie zer) jest równa $F_{n+2};$
• liczba podzbiorów zbioru $\{1,\ldots ,n\}$ bez kolejnych liczb jest równa $F_{n+2};$
• liczba ciągów binarnych bez nieparzystej długości ciągów jedynek jest równa $F_{n+1};$
• liczba ciągów binarnych bez parzystej długości ciągów zer lub jedynek jest równa $2F_{n}.$

Własności

Sumy wyrazów tworzące ciąg Fibonacciego na trójkącie Pascala.

Można też wyrazić wartości kolejnych elementów ciągu za pomocą symbolu Newtona:

$F_{n}=\sum _{k=1}^{\left\lfloor {\frac {n+1}{2}}\right\rfloor }{n-k \choose k-1}$

Zachodzą równości:

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

$\sum _{i=0}^{n}iF_{i}=nF_{n+2}-F_{n+3}+2$

Ciąg kwadratów, których długości boków są kolejnymi liczbami Fibonacciego

$\sum _{k=1}^{n}F_{k}^{2}=F_{n+1}F_{n}$ (równanie ilustruje rysunek)

$\sum _{k=1}^{n}F_{k}^{3}=(F_{3n+2}+(-1)^{n+1}6F_{n-1}+5)/10$

$F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}$

$F_{2n-1}=F_{n}^{2}+F_{n-1}^{2}$

$F_{n+1}F_{n-1}-F_{n}^{2}=(-1)^{n},$ tzw. zależność Cassiniego (1680), która leży u podstaw zagadki brakującego kwadratu oraz uogólniona wersja:

$F_{n}^{2}-F_{n-r}F_{n+r}=(-1)^{n-r}F_{r}^{2},$ tzw. zależność Catalana

$F_{n+1}F_{m}+F_{n}F_{m-1}=F_{m+n}$

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

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

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

$\sum _{k=0}^{n-1}{n \choose k}F_{n-k}=F_{2n}$

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

Dowód: W zapisie $2n+1$ jako sumy jedynek i dwójek jest nieparzysta liczba jedynek. Lewa strona równości stanowi zliczanie liczby zapisów $2n+1,$ w którym parametry $i$ i $j$ odpowiadają liczbie dwójek po prawej i lewej stronie środkowej jedynki.

Kilka mniej znanych twierdzeń na temat ciągu Fibonacciego:

• Z wyjątkiem jednocyfrowych liczb ciągu Fibonacciego zawsze cztery albo pięć następujących po sobie wyrazów ciągu ma tę samą liczbę cyfr w układzie dziesiętnym.
• Jedynymi liczbami w całym ciągu Fibonacciego, będącymi kwadratami liczb całkowitych są 0, 1 i 144^{[potrzebny przypis]}.
• Co trzecia liczba Fibonacciego jest podzielna przez 2, co czwarta – przez 3. Ogólniej: jeśli numer $n$ dzieli się przez $k,$ to liczba $F_{n}$ dzieli się przez $F_{k}.$ Dokładniej:

Jeśli $n=mq,$ to: $F_{n}=F_{m}\sum _{j=1}^{q}F_{m-1}^{j-1}F_{n-jm+1}.$

Zachodzi jeszcze silniejszy związek: największy wspólny dzielnik dwóch liczb Fibonacciego jest liczbą Fibonacciego, której numer jest równy największemu wspólnemu dzielnikowi numerów tych liczb: $\gcd(F_{m},\,F_{n})=F_{\gcd(m,\,n)}...$

• Każda niezerowa liczba całkowita ma wielokrotność będącą liczbą Fibonacciego.
• Istnieje nieskończenie wiele liczb $n,$ dla których zachodzi podzielność $n|F_{n}.$ W szczególności można pokazać, że jeśli $m\in \mathbb {N}$ to $5^{m}|F_{5^{m}}.$

Obliczanie liczb Fibonacciego

Teoretycznie wartości kolejnych wyrazów ciągu Fibonacciego mogą być obliczone wprost z definicji, jest to jednak metoda na tyle wolna, że stosowanie jej ma tylko sens dla niewielu początkowych wyrazów ciągu, nawet na bardzo szybkich komputerach. Wynika to z tego, że definicja $F_{n}$ wielokrotnie odwołuje się do wartości poprzednich wyrazów ciągów. Drzewo wywołań takiego algorytmu dla parametru $n$ musi mieć co najmniej $F_{n}$ liści o wartości 1. Ponieważ ciąg Fibonacciego rośnie wykładniczo, oznacza to wyjątkowo słabą wydajność.

Istnieje równie prosta i znacznie szybsza metoda. Obliczamy wartości ciągu po kolei: $F_{0},$ $F_{1},$ $F_{2}$ i tak aż do $F_{n},$ za każdym razem korzystając z tego, co już obliczyliśmy. Nie trzeba nawet zapamiętywać wszystkich obliczonych dotychczas wartości, ponieważ wystarczą dwie ostatnie. Daje to złożoność liniową – o wiele lepszą od wykładniczej złożoności poprzedniej metody. Metoda ta może być postrzegana jako zastosowanie programowania dynamicznego.

 Fibonacci( n )
   if n=0 then return 0
   if n=1 then return 1
   f' ← 0
   f  ← 1
   for i ← 2 to n
     do
       m  ← f + f'
       f' ← f
       f  ← m
     end
   return f

Macierze liczb Fibonacciego

Można zrobić to jeszcze szybciej dzięki zależności:

${\begin{bmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n}\end{bmatrix}}\cdot {\begin{bmatrix}1&1\\1&0\end{bmatrix}}={\begin{bmatrix}F_{n+3}&F_{n+2}\\F_{n+2}&F_{n+1}\end{bmatrix}}$

Ponieważ równocześnie:

${\begin{bmatrix}1&1\\1&0\end{bmatrix}}={\begin{bmatrix}F_{2}&F_{1}\\F_{1}&F_{0}\end{bmatrix}},$

to indukcyjnie:

${\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}},\quad n\geq 1$

lub w notacji wektorowej

${\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}\times {\begin{bmatrix}F_{1}\\F_{0}\end{bmatrix}}$

A ponieważ potęgowanie macierzy dla naturalnego wykładnika potęgi można przeprowadzić bardzo wydajnie algorytmem szybkiego potęgowania, możemy wyliczyć dowolny wyraz ciągu Fibonacciego z kosztem logarytmicznym względem $n,$ tzn. obliczenie $F_{n}$ wymaga ilości mnożeń $\Theta (\log n)$ (symbol $\Theta$ oznacza asymptotyczne tempo wzrostu).

• zobacz implementacje algorytmów obliczających wyrazy ciągu Fibonacciego

Graficzna reprezentacja dwójkowa

Ciąg Fibonacciego w systemie dwójkowym

Jeśli kolejne wyrazy ciągu zapisać w systemie dwójkowym, jeden pod drugim, z wyrównaniem do prawej strony, to otrzymamy wydłużający się w dół trójkąt, którego elementy powtarzają się („czubek” pojawia się poniżej, przy prawej krawędzi, w coraz dłuższym rozwinięciu – pojawia się nad nim „biały trójkąt”), co czyni go podobnym do fraktala. Dla lepszej przejrzystości na rysunku obok wszystkie zera zastąpiono białymi punktami, a jedynki – czarnymi.

Złota liczba

Granica ciągu:

${\frac {F(n+1)}{F(n)}},$

czyli ilorazów sąsiadujących ze sobą wyrazów ciągu Fibonacciego, to tzw. złota liczba lub złota proporcja definiowana jako dodatnie rozwiązanie równania:

${\frac {x}{1}}={\frac {1}{x-1}}$ lub równoważnego $x=1+{\frac {1}{x}},$

czyli

$\lim _{n\to \infty }{\frac {F(n+1)}{F(n)}}=\phi ,$

$\varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}61803\,39887\ldots$

Dowód

Taka granica istnieje, gdyż ten ciąg jest nierosnący i ograniczony z dołu przez 0. Teraz należy wyłącznie ją obliczyć.

$x={\lim _{n\to \infty }{\frac {F(n+1)}{F(n)}}}$

$=\lim _{n\to \infty }{\frac {F(n)+F(n-1)}{F(n)}}$

$=\lim _{n\to \infty }\left({\frac {F(n)}{F(n)}}+{\frac {F(n-1)}{F(n)}}\right)$

$=1+\lim _{n\to \infty }{\frac {F(n-1)}{F(n)}}$

$=1+{\frac {1}{\displaystyle \lim _{n\to \infty }{\frac {F(n)}{F(n-1)}}}}$

$=1+{\frac {1}{x}}$

Jest ona także pierwiastkiem wielomianu x² – x – 1 oraz równania x + x⁻² = 2.

W powyższym dowodzie informacja o początkowych wyrazach ciągu czy też jakichkolwiek innych nie była wykorzystywana, dlatego dla dowolnego ciągu

$G_{n}:=G(n):={\begin{cases}a&{\text{dla }}n=0;\\b&{\text{dla }}n=1;\\G(n-1)+G(n-2)&{\text{dla }}n>1.\end{cases}}$

zachodzi wzór: $G_{n}=a\cdot F_{n-1}+b\cdot F_{n}.$ Czasem taki ciąg G również nazywany jest ciągiem Fibonacciego lub uogólnionym ciągiem Fibonacciego. Jeżeli, a i b nie są równocześnie zerami, to granica ciągu $\left({\frac {G(n+1)}{G(n)}}\right)_{n\in {\mathbb {N} }}$ jest taka sama jak dla oryginalnego ciągu Fibonacciego.

Kolejne wyrazy ciągu: ${\frac {F(n+1)}{F(n)}}$ są także wartością n-tego odcinka ułamka łańcuchowego: $\varphi =[1;1,1,1,...]=1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\cdots }}}}}}$

wartościami kolejnych odcinków są liczby:

${\cfrac {1}{1}}=1\qquad {\cfrac {2}{1}}=1+{\cfrac {1}{1}}\qquad {\cfrac {3}{2}}=1+{\cfrac {1}{1+{\cfrac {1}{1}}}}\qquad {\cfrac {5}{3}}=1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1}}}}}}\qquad {\cfrac {8}{5}}=1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1}}}}}}}}$

Liczby pierwsze w ciągu Fibonacciego

Kilka początkowych wyrazów w ciągu Fibonacciego to także liczby pierwsze, a mianowicie: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229. Wydaje się prawdopodobne, że liczb pierwszych w ciągu Fibonacciego istnieje nieskończenie wiele, lecz problem ten jak dotąd nie doczekał się rozstrzygnięcia.

Pokrewne ciągi

Ciąg Lucasa

Ciąg Lucasa jest pewną odmianą ciągu Fibonacciego, definiujemy go

$L_{n}:=L(n):={\begin{cases}2&{\text{dla }}n=0;\\1&{\text{dla }}n=1;\\L(n-1)+L(n-2)&{\text{dla }}n>1.\end{cases}}$

Zachodzą równości:

$L_{n}=F_{n-1}+F_{n+1}$

$F_{n}={\tfrac {1}{5}}(L_{n-1}+L_{n+1}).$

$F_{n+1}={\tfrac {1}{2}}(F_{n}+L_{n}).$

$F_{2n}=F_{n}L_{n}.$

$F_{m+n}={\tfrac {1}{2}}(F_{m}L_{n}+F_{n}L_{m}).$

$F_{m-n}={\tfrac {1}{2}}(-1)^{n}(F_{m}L_{n}-F_{n}L_{m}).$

Ciąg „Tribonacciego”

Różni się od ciągu Fibonacciego tym, że każdy kolejny jego wyraz powstaje przez zsumowanie poprzednich trzech wyrazów zamiast dwóch. Jego kilka początkowych wyrazów to: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890... Stała „Tribonacciego” jest granicą ciągu: ${\frac {T(n+1)}{T(n)}}$ (gdzie $T(n)$ jest $n$-tym wyrazem ciągu „Tribonacciego”), czyli analogiem złotej liczby dla ciągu Fibonacciego. Jest ona pierwiastkiem wielomianu $x^{3}-x^{2}-x-1$ oraz równania $x+x^{-3}=2$ i wynosi ok. 1,83929.

Ciąg „Tetranacciego”

Różni się od ciągu Fibonacciego tym, każdy kolejny jego wyraz powstaje przez zsumowanie poprzednich czterech wyrazów zamiast dwóch. Jego kilka początkowych wyrazów to: 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569... Stała „Tetranacciego” jest granicą ciągu: ${\frac {T(n+1)}{T(n)}}$ (gdzie $T(n)$ jest $n$-tym wyrazem ciągu „Tetranacciego”). Jest ona pierwiastkiem wielomianu $x^{4}-x^{3}-x^{2}-x-1$ oraz równania $x+x^{-4}=2$ i wynosi ok. 1,92756.

Słowa Fibonacciego

Ciąg słów Fibonacciego to ciąg słów

$F_{n}={\begin{cases}b&{\text{dla }}n=1;\\a&{\text{dla }}n=2;\\F_{n-1}\cdot F_{n-2}&{\text{dla }}n>2,{\text{ gdzie }}\cdot {\text{ oznacza sklejenie ciagow}}\end{cases}}$

Ciąg Fibonacciego w biologii

W kształtach wielu roślin widać linie spiralne. Na przykład na owocu ananasa 8 takich linii biegnie w jedną stronę, a 5 lub 13 w przeciwną. Na tarczy słonecznika może się krzyżować 55 spiral z 89 (liczby te bywają większe). Również różyczki kalafiora ułożone są spiralnie.

U większości roślin takie organy, jak łodyga, liście czy kwiaty rozwijają się z małego, centralnie usytuowanego skupiska komórek – merystemu. Każdy zawiązek nowego organu (zwany primordium) wyrasta z merystemu w innym kierunku, pod pewnym kątem w stosunku do zawiązka, który pojawił się wcześniej. Okazuje się, że u wielu roślin ten kąt jest taki sam i że to właśnie dzięki niemu powstają wspomniane linie spiralne. Ten kąt to w przybliżeniu 137,5 stopnia (jest to tak zwany „Złoty kąt”). „Złotego kąta” nie da się wyrazić ułamkiem zwykłym. Jego dopełnienie do 360 stopni wynosi w przybliżeniu 5/8 kąta pełnego, dokładniej jest to 8/13 kąta pełnego, jeszcze dokładniej 13/21 i tak dalej (oparcie na liczbach Fibonacciego), ale żaden ułamek zwykły nie odpowiada mu ściśle.

Kiedy pojawiają się kolejne zawiązki, to jeśli każdy następny utworzy z poprzednim wspomniany „złoty kąt”, nigdy nie dojdzie do tego, by dwa z nich (lub więcej) rozwijały się w tym samym kierunku. Dzięki temu organy nie wyrastają z merystemu promieniście, lecz układają się w linie spiralne.

Ciąg Fibonacciego w muzyce

Niektórzy muzykolodzy dopatrują się istnienia ciągu Fibonacciego w utworach muzycznych oraz w budowie instrumentów. Zależności takie występują w utworach muzycznych – najczęściej w proporcjach rytmicznych. Węgierski muzykolog Erno Lendvai wykrył wiele takich zależności w muzyce Beli Bartóka, przede wszystkim w Muzyce na instrumenty strunowe, perkusję i czelestę, gdzie w cz. I kolejne odcinki formy zaczynają się w następującym porządku:

• zakończenie ekspozycji – t. 21,
• początek stretto – t. 34,
• kulminacja części – t. 55,
• koniec części – t. 89.

W drugiej połowie XX wieku ciąg Fibonacciego stosowany był przez niektórych kompozytorów do proporcjonalnego porządkowania rytmu lub harmonii. Szczególnie często sięgali do niego kompozytorzy stosujący technikę serialną, np.: Karlheinz Stockhausen Klavierstück IX, Luigi Nono Il canto sospeso, Christobal Halffter Fibonacciana. Na ciągu Fibonacciego stosowanym równocześnie w przód i wstecz zbudowane jest Trio klarnetowe Krzysztofa Meyera. Jednostką miary jest w tym utworze ćwierćnuta, a kolejne odcinki różnią się obsadą. I tak np.:

• kolejne odcinki grane przez fortepian mają długość: 89, 55, 34, 21, 13 ćwierćnut,
• wszystkie instrumenty razem grają: 21, 34, 55, 89, 144 ćwierćnut.

Ciąg Fibonacciego używany jest też przez twórców spoza muzyki klasycznej, np. zespół Tool wykonujący muzykę z pogranicza rocka i metalu progresywnego w albumie Lateralus w tytułowym utworze użył ciągu Fibonacciego do stworzenia linii wokalnej.

Ciąg Fibonacciego w literaturze

Motyw ciągu Fibonacciego wykorzystany został także w utworach literackich. W książce Kod Leonarda da Vinci Dana Browna stanowi on element jednego z kodów, który muszą złamać główni bohaterowie. W powieści Gniazdo światów Marka Huberatha ciąg Fibonacciego jest podstawą struktury wszechświata, na której oparte są kolejne jego poziomy.

Linki zewnętrzne

• Antoni Długosz, Dywany Antoniego – nie tylko bajka o pewnych zastosowaniach ciągu Fibonacciego
• Liczba Fibonacciego (ang.) w encyklopedii MathWorld
• Formuły związane z ciągiem Fibonacciego
• Ciąg Fibonacciego w On-Line Encyclopedia of Integer Sequences