Tekst źródłowy strony Ciąg Fibonacciego

{{Wikiźródła|Ciąg Fibonacciego|tablicę ciągu Fibonacciego|tekst=nie}}
[[Plik:First members of Fibonacci sequence.svg|thumb|250px|Wykres funkcji dla pierwszych ośmiu wyrazów ciągu Fibonacciego <math>(F_0 \ldots F_7)</math>]]
'''Ciąg Fibonacciego''' – [[Ciąg (matematyka)|ciąg]] [[Liczby naturalne|liczb naturalnych]] określony [[rekurencja|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:
: <math>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}</math>

Kolejne wyrazy tego ciągu nazywane są '''liczbami [[Fibonacci]]ego'''<ref name="epwn-l">{{Encyklopedia PWN | id = 3932365 | tytuł = liczby Fibonacciego | data dostępu = 2021-10-03}}</ref>. Zaliczanie zera do elementów ciągu Fibonacciego zależy od umowy – część autorów definiuje ciąg od <math>F_1 = F_2 = 1</math><ref name="zero" group="uwaga">Zero jest zaliczane do ciągu Fibonacciego np. w książce {{cytuj książkę |nazwisko = Mostowski |imię = Andrzej |autor link = Andrzej Mostowski |nazwisko2 = Stark |imię2 = Marceli |autor link2 = Marceli Stark |tytuł = Elementy algebry wyższej |wydanie = 7 |wydawca = PWN |miejsce = Warszawa |seria = BM 16 |rok = 1974 |strony = 16}} Nie jest natomiast zaliczane do ciągu Fibonacciego w Wielkiej Encyklopedii Powszechnej PWN, 1964, tom 3, s. 636, [http://books.google.com/books?id=h7MYAAAAIAAJ&q=%22ci%C4%85g+Fibonacciego%22+%222,3,5,8,13%22&dq=%22ci%C4%85g+Fibonacciego%22+%222,3,5,8,13%22&lr=&pgis=1 link].</ref>.

Pierwsze dwadzieścia wyrazów ciągu Fibonacciego to:
{| class="wikitable" style="text-align: center"
|-
| <math>F_0</math>
| <math>F_1</math>
| <math>F_2</math>
| <math>F_3</math>
| <math>F_4</math>
| <math>F_5</math>
| <math>F_6</math>
| <math>F_7</math>
| <math>F_8</math>
| <math>F_9</math>
| <math>F_{10}</math>
| <math>F_{11}</math>
| <math>F_{12}</math>
| <math>F_{13}</math>
| <math>F_{14}</math>
| <math>F_{15}</math>
| <math>F_{16}</math>
| <math>F_{17}</math>
| <math>F_{18}</math>
| <math>F_{19}</math>
|-
| 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 [[Fibonacci|Leonarda z Pizy]], zwanego Fibonaccim<ref name="epwn">{{Encyklopedia PWN | id = 3900667 | tytuł = ciąg Fibonacciego | data dostępu = 2021-10-03}}</ref>, 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]]<ref>Andrzej Lenda, ''[http://www.ftj.agh.edu.pl/~lenda/cicer/FIBO.HTM Liczby Fibonacciego]'', ftj.agh.edu.pl [dostęp 2021-10-03].</ref>.

== Wzór Bineta ==
Jawny wzór na <math>n</math>-ty wyraz ciągu Fibonacciego podany w 1843 r. przez [[Jacques Philippe Marie Binet|J.P.M. Bineta]] możemy otrzymać, korzystając z metody [[Funkcja tworząca|funkcji tworzących]].

Niech
: <math>f_n = F_{n+1}.</math>

Funkcja tworząca dla tego ciągu ma postać
: <math>s(x)=\sum_{n=0}^\infty f_n x^n.</math>

Podstawiając <math>f_n = f_{n-1} + f_{n-2},</math> otrzymujemy:
: <math>\begin{align}
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 + x s(x) + x^2 s(x).
\end{align}</math>

W szczególności,
: <math>s(x) = \frac{1}{1 - x - x^2}.</math>

Wyrażenie <math>\frac{1}{1 - x - x^2}</math> można przedstawić w prostszej postaci, mianowicie:
: <math>\frac{1}{1 - x - x^2} = A/(1-ax) + B/(1-bx),</math>

gdzie:
: <math>a=\frac{1 + \sqrt{5}}{2},</math>
: <math>b=\frac{1 - \sqrt{5}}{2},</math>
: <math>A=\frac{a}{a-b},</math>
: <math>B=\frac{-b}{a-b}.</math>

Wówczas:
: <math>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,</math>

a stąd:
: <math>f_n = \frac{(a^{n+1} - b^{n+1})}{(a-b)}.</math>

Ponieważ <math>F_n=f_{n-1},</math> wyprowadzony został ostatecznie tzw. ''wzór Bineta'' zwany czasem ''wzorem Eulera-Bineta'':
: <math>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.</math>

Ponieważ drugi człon tego wyrażenia szybko zbiega do zera
: <math>F_n \approx \frac{1}{\sqrt 5}\left(\frac{1 + \sqrt 5}{2}\right)^n.</math>

== Znaczenia kombinatoryczne ==
* liczba ciągów o wyrazach równych 1 lub 2, które sumują się do liczby <math>n,</math> jest równa <math>F_{n+1},</math>
* liczba pokryć planszy <math>2 \times n</math> kostkami domina <math>2 \times 1</math> jest równa <math>F_{n+1},</math>
* liczba ciągów [[Dwójkowy system liczbowy|binarnych]] bez kolejnych jedynek (równoważnie zer) jest równa <math>F_{n+2},</math>
* liczba podzbiorów zbioru <math>\{ 1, \dots, n \}</math> bez kolejnych liczb jest równa <math>F_{n+2},</math>
* liczba ciągów binarnych bez nieparzystej długości ciągów jedynek jest równa <math>F_{n+1},</math>
* liczba ciągów binarnych bez parzystej długości ciągów zer lub jedynek jest równa <math>2 F_n.</math>

== Własności ==
[[Plik:PascalTriangleFibanacci.svg|thumb|300px|Sumy wyrazów tworzące ciąg Fibonacciego na [[trójkąt Pascala|trójkącie Pascala]].]]
Można też wyrazić wartości kolejnych elementów ciągu za pomocą [[symbol Newtona|symbolu Newtona]]:
: <math>F_n = \sum_{k=1}^{\left\lfloor \frac{n+1}2\right\rfloor}{n-k \choose k-1}</math>

Zachodzą równości:
: <math>\sum_{k=1}^n F_k = F_{n+2}-1</math>

: <math>\sum_{i=0}^n iF_i = nF_{n+2} - F_{n+3} + 2</math>
[[Plik:FibonacciBlocks.svg|thumb|300px|Ciąg kwadratów, których długości boków są kolejnymi liczbami Fibonacciego]]

: <math>\sum_{k=1}^n F_k^2 = F_{n+1}F_n</math> (równanie ilustruje rysunek)

: <math>\sum_{k=1}^n F_k^3 = (F_{3n+2}+ (-1)^{n+1}6 F_{n-1}+5 )/10</math>

: <math>F_{2n} = F_{n+1}^2 - F_{n-1}^2</math>

: <math>F_{2n-1} = F_n^2 + F_{n-1}^2</math>

: <math>F_{n+1}F_{n-1} - F_n^2 = (-1)^n,</math> tzw. zależność [[Giovanni Cassini|Cassiniego]] (1680)<ref>{{cytuj książkę |nazwisko = Graham |imię = Ronald |nazwisko2 = Knuth |imię2 = Donald |nazwisko3 = Patashnik |imię3 = Oren |tytuł = Matematyka konkretna |rok = 2006 |strony = 326 |wydawca = PWN |miejsce = Warszawa}}</ref>, która leży u podstaw [[Zagadka brakującego kwadratu|zagadki brakującego kwadratu]]<ref>{{cytuj książkę |nazwisko = Gardner |imię = Martin |tytuł = Mathematics Magic and Mystery |rok = 1956 |wydawca = Dover Publications, Inc. |miejsce = Nowy York}}</ref> oraz uogólniona wersja:

: <math>F_n^2 - F_{n-r}F_{n+r} = (-1)^{n-r}F_r^2,</math> tzw. zależność [[Eugène Charles Catalan|Catalana]]<ref>{{cytuj książkę |nazwisko = Coxeter |imię = Harold Scott MacDonald |tytuł = Wstęp do geometrii starej i nowej |rok = 1967 |wydawca = PWN |miejsce = Warszawa}}</ref>

: <math>F_{n+1}F_m + F_n F_{m-1} = F_{m+n}</math>

: <math>\sum_{i=0}^{n-1} F_{2i+1} = F_{2n}</math>

: <math>\sum_{i=1}^n F_{2i} = F_{2n+1} - 1</math>

: <math>\sum_{i=1}^n (-1)^{i+1} F_i = (-1)^{n+1} F_{n-1} + 1</math>

: <math>\sum_{k=0}^{n-1} {n \choose k} F_{n-k} = F_{2n}</math><ref>{{cytuj książkę |nazwisko = Pawłowski |imię = Henryk |tytuł = Zadania z olimpiad matematycznych z całego świata. Teoria liczb, algebra i elementy analizy matematycznej |rok = 2005 |wydawca = Oficyna Wydawnicza „Tutor” |miejsce = Toruń |strony = 206–207 |isbn = 83-86007-21-4}}</ref>

I otrzymujemy ostatecznie:
: <math>\sum_{i=1}^n \sum_{j=1}^n {n-i \choose j} {n-j \choose i} = F_{2n+1}</math>

'''Dowód:''' W zapisie <math>2n+1</math> jako sumy jedynek i dwójek jest nieparzysta liczba jedynek. Lewa strona równości stanowi zliczanie liczby zapisów <math>2n+1,</math> w którym parametry <math>i</math> i <math>j</math> 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 ciągu Fibonacciego, będącymi [[Potęgowanie|kwadratami]] [[liczby całkowite|liczb całkowitych]] są 0, 1 i 144<ref>{{cytuj |tytuł = Square Fibonacci Numbers etc |autor = John H.E. Cohn |czasopismo = Fibonacci Quarterly |wolumin = 2 |data = 1964 |s = 109–113 |url = http://math.la.asu.edu/~checkman/SquareFibonacci.html |język = en}}</ref>.
* Co trzecia liczba Fibonacciego jest podzielna przez 2, co czwarta – przez 3. Ogólniej: jeśli numer <math>n</math> dzieli się przez <math>k,</math> to liczba <math>F_n</math> dzieli się przez <math>F_k.</math> Dokładniej:
: Jeśli <math>n=mq,</math> to: <math>F_n = F_m \sum_{j=1}^q F_{m-1}^{j-1} F_{n-jm+1}.</math>

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: <math>\gcd(F_m,\,F_n) = F_{\gcd(m,\,n)}.</math>
* Każda niezerowa liczba całkowita ma wielokrotność będącą liczbą Fibonacciego.
* Istnieje nieskończenie wiele liczb <math>n,</math> dla których zachodzi podzielność <math>n | F_n.</math> W szczególności można pokazać, że jeśli <math>m\in\mathbb{N}</math> to <math>5^m | F_{5^m}.</math>

== 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 <math>F_n</math> wielokrotnie odwołuje się do wartości poprzednich wyrazów ciągów. [[Drzewo wywołań funkcji|Drzewo wywołań]] takiego algorytmu dla parametru <math>n</math> musi mieć co najmniej <math>F_n</math> 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: <math>F_0,</math> <math>F_1,</math> <math>F_2</math> i tak aż do <math>F_n,</math> 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ść obliczeniowa|złożoność liniową]] – o wiele lepszą od wykładniczej złożoności poprzedniej metody. Metoda ta może być postrzegana jako zastosowanie [[programowanie dynamiczne|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:
: <math>\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}.</math>

Ponieważ równocześnie:
: <math>\begin{bmatrix}
    1 & 1 \\
    1 & 0
\end{bmatrix} = \begin{bmatrix}
    F_2 & F_1 \\
    F_1 & F_0
\end{bmatrix},</math>

to [[indukcja matematyczna|indukcyjnie]]:
: <math>\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\geqslant 1</math>

lub w notacji wektorowej
: <math>\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}.</math>

A ponieważ [[mnożenie macierzy#potęgowanie macierzy|potęgowanie macierzy]] dla [[liczby naturalne|naturalnego]] wykładnika potęgi można przeprowadzić bardzo wydajnie [[algorytm szybkiego potęgowania|algorytmem szybkiego potęgowania]], możemy wyliczyć dowolny wyraz ciągu Fibonacciego z kosztem [[logarytm]]icznym względem <math>n,</math> tzn. obliczenie <math>F_n</math> wymaga ilości mnożeń <math>\Theta(\log n)</math> (symbol <math>\Theta</math> oznacza [[asymptotyczne tempo wzrostu]]).

* [[b:Kody źródłowe/Ciąg Fibonacciego|zobacz implementacje algorytmów obliczających wyrazy ciągu Fibonacciego]]

== Graficzna reprezentacja dwójkowa ==
[[Plik:Fibonnaci numbers-binary.png|frame|right|Ciąg Fibonacciego w [[dwójkowy system liczbowy|systemie dwójkowym]]]]
Jeśli kolejne wyrazy ciągu zapisać w [[Dwójkowy system liczbowy|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 [[fraktal]]a. Dla lepszej przejrzystości na rysunku obok wszystkie zera zastąpiono białymi punktami, a jedynki – czarnymi.

== Złota liczba ==
{{osobny artykuł|złoty podział}}
[[granica ciągu|Granicą ciągu]]
: <math>\frac{F_{n+1}}{F_n}, n \geq 1,</math>
czyli ciągu ilorazów kolejnych wyrazów ciągu Fibonacciego, jest tzw. [[złoty podział|złota liczba]] lub złota proporcja. Złota proporcja jest definiowana jako dodatnie rozwiązanie równania
: <math>\frac x 1 = \frac 1 {x - 1}</math> lub równoważnego <math>x = 1 + \frac 1 x</math>
i oznaczana grecką [[phi|literą φ]]. Mamy
: <math>\varphi = \frac{1+\sqrt{5}}{2} \approx 1{,}61803\,39887 \ldots</math>
Formalnie piszemy
: <math>\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi</math>.

=== Dowód zbieżności ciągu ilorazów ===
Udowodnimy, że granica ciągu <math>\varphi_n = \frac {F_{n+1}} {F_n}, n \geq 1</math> istotnie istnieje, a ponadto jest równa <math>\varphi</math>.

Z definicji złotej proporcji <math>\varphi = 1 + \frac 1 \varphi</math> oraz <math>\varphi > 0</math>. Stąd <math>\varphi > 1</math>. Ciąg Fibonacciego jest rosnący, więc <math>\varphi_n = \frac {F_{n+1}} {F_n} \geq 1</math>. Zobaczmy, że <math>\varphi_{n+1}=\frac {F_{n+2}}{F_{n+1}} = \frac{F_{n+1} + F_n}{F_{n+1}}=1+\frac{F_n}{F_{n+1}}=1+\frac 1 {\varphi_n}</math>. Łącząc powyższe fakty otrzymujemy, że
: <math>\left|\varphi_{n+1}-\varphi\right|=\left|\left(1 + \frac 1 {\varphi_n}\right)-\left(1 + \frac 1 \varphi\right)\right|=\left|\frac 1 {\varphi_n}-\frac 1 \varphi\right|=\left|\frac {\varphi - \varphi_n}{\varphi_n \varphi}\right|=\frac 1 {\varphi_n} \cdot \frac 1 \varphi \left|\varphi_n - \varphi\right|\leq \frac 1 \varphi\left|\varphi_n - \varphi\right|</math>
dla <math>n \geq 1</math> całkowitych. Zatem mamy
: <math>\left|\varphi_n-\varphi\right|\leq \frac 1 \varphi \left|\varphi_{n-1}-\varphi\right| \leq \frac 1 {\varphi^2} \left|\varphi_{n-2}-\varphi\right| \leq \cdots \leq \frac 1 {\varphi^{n-1}} \left|\varphi_1-\varphi\right|</math>
dla <math>n \geq 1</math> całkowitych. Nierówność <math>\varphi > 1</math> implikuje, że <math>\frac 1 {\varphi^{n-1}} \longrightarrow 0</math>. Stąd <math>\left|\varphi_n-\varphi\right|\longrightarrow 0</math>, a zatem <math>\varphi_n \longrightarrow \varphi</math>.

=== Uogólniony ciąg Fibonacciego i jego ciąg ilorazów ===
Ciąg
: <math>G_n = \begin{cases}
    a & \text{dla } n = 0 \\
    b & \text{dla } n = 1 \\
    G_{n-1}+G_{n-2} & \text{dla } n \geq 2
\end{cases}</math>,
gdzie <math>a</math> oraz <math>b</math> są ustalonymi liczbami zespolonymi, jest czasem nazywany uogólnionym ciągiem Fibonacciego. Spełnia on wzór
: <math>G_n = a \cdot F_{n-1} + b \cdot F_n</math>,
który będzie potrzebny do obliczenia granicy ciągu <math>\frac{G_{n+1}}{G_n}</math>. Przypomnijmy, że <math>\frac {F_{n+1}}{F_n}\longrightarrow\varphi</math> oraz <math>\frac {F_{n-1}}{F_n}\longrightarrow\varphi^{-1}</math>. Zobaczmy teraz, że
: <math>\lim_{n\to\infty}\frac {G_{n+1}}{G_n} = \lim_{n\to\infty}\frac {a\cdot F_n + b\cdot F_{n+1}}{a\cdot F_{n-1}+b\cdot F_n} = \lim_{n\to\infty}\frac {a + b\cdot \frac{F_{n+1}}{F_n}}{a\cdot \frac{F_{n-1}}{F_n}+b} = \frac {a + b \cdot \varphi} {a \cdot \varphi^{-1} + b} = \varphi</math>
o ile tylko <math>a\cdot\varphi^{-1}+b \neq 0</math>.

Jeśli <math>a\cdot\varphi^{-1}+b=0</math>, to albo <math>a=b=0</math>, albo <math>a\neq 0\neq b</math> oraz <math>\frac b a = -\varphi^{-1}</math>. W pierwszym przypadku <math>G_n = 0</math> dla wszystkich <math>n \geq 0</math> całkowitych, a wtedy wyrażenie <math>\frac{G_{n+1}}{G_n}=\frac 0 0</math> nie ma sensu. W drugim przypadku otrzymujemy ciąg geometryczny zadany wzorem
: <math>G_n = a \cdot \left(-\varphi\right)^{-n}</math>,
co daje <math>\frac {G_{n+1}}{G_n} = -\varphi^{-1}</math> dla wszystkich <math>n \geq 0</math> całkowitych. Wtedy w szczególności <math>\frac {G_{n+1}}{G_n} \longrightarrow -\varphi^{-1}</math>. Odnotujmy, że <math>-\varphi^{-1}</math> jest drugim, obok <math>\varphi</math>, z rozwiązań równania <math>x = 1 + \frac 1 x</math>.

=== Powiązania z ułamkami łańcuchowymi ===
Kolejne wyrazy ciągu: <math>\frac{F_{n+1}}{F_n}</math> są także wartościami <math>n</math>-tego odcinka [[ułamek łańcuchowy|ułamka łańcuchowego]]
: <math>\varphi = [1; 1, 1, 1, \dots] = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ldots}}},</math>

wartościami kolejnych odcinków są następujące liczby:
: <math>\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}}}}</math>

== Liczby pierwsze w ciągu Fibonacciego ==
{{osobny artykuł|liczby pierwsze Fibonacciego}}

Niektóre z wyrazów ciągu Fibonacciego to [[liczby pierwsze]]<ref>[http://oeis.org/A005478 A005478].</ref>, początkowe to: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229. Problem, czy w ciągu Fibonacciego istnieje nieskończenie wiele liczb pierwszych, jak dotąd nie doczekał się rozstrzygnięcia (stan na styczeń 2023).

== Podobne ciągi ==
=== Ciąg Lucasa ===
Ciąg Lucasa jest pewną odmianą ciągu Fibonacciego, definiujemy go
: <math>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}</math>

Zachodzą równości:
: <math>L_n=F_{n-1}+F_{n+1}</math>
: <math>F_n = \tfrac{1}{5}(L_{n-1}+L_{n+1}).</math>
: <math>F_{n+1} = \tfrac{1}{2}(F_n+L_n).</math>
: <math>F_{2n} = F_n L_n.</math>
: <math>F_{m+n} = \tfrac{1}{2}(F_m L_n + F_n L_m).</math>
: <math>F_{m-n} = \tfrac{1}{2}(-1)^n(F_m L_n - F_n L_m).</math>

=== 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<ref>[http://oeis.org/A000073 A000073].</ref>.

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: <math>\frac{T(n+1)}{T(n)}</math> (gdzie <math>T(n)</math> jest <math>n</math>-tym wyrazem ciągu „Tribonacciego”), czyli analogiem złotej liczby dla ciągu Fibonacciego. Jest ona pierwiastkiem wielomianu <math>x^3 - x^2 - x - 1</math> oraz równania <math>x + x^{-3} = 2</math> 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<ref>[http://oeis.org/A000078 A000078].</ref>.

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: <math>\frac{T(n+1)}{T(n)}</math> (gdzie <math>T(n)</math> jest <math>n</math>-tym wyrazem ciągu „Tetranacciego”). Jest ona pierwiastkiem wielomianu <math>x^4 - x^3 - x^2 - x - 1</math> oraz równania <math>x + x^{-4} = 2</math> i wynosi ok. 1,92756.

=== Słowa Fibonacciego ===
{{Osobny artykuł|Słowa Fibonacciego}}
Ciąg [[słowa Fibonacciego|słów Fibonacciego]] to ciąg słów
: <math>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}</math>

== 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 – [[tkanka twórcza|merystemu]]. Każdy zawiązek nowego organu (zwany [[zawiązek|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 {{link-interwiki|Erno Lendvai|Q=Q284010}}<ref>Lendvai, Ernő (1971). ''Béla Bartók: An Analysis of His Music''. London: Kahn and Averill.</ref> wykrył wiele takich zależności w muzyce [[Béla Bartók|Beli Bartóka]], przede wszystkim w ''Muzyce na instrumenty strunowe, perkusję i czelestę'', gdzie w części 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ę [[serializm|serialną]], np.: [[Karlheinz Stockhausen]] ''Klavierstück IX'', [[Luigi Nono]] ''Il canto sospeso'', [[Cristóbal Halffter]] ''Fibonacciana''<ref>B. Schaeffer, ''Mały informator muzyki XX wieku'', Kraków 1975, s. 121.</ref>. Na ciągu Fibonacciego stosowanym równocześnie w przód i wstecz zbudowane jest ''Trio klarnetowe'' [[Krzysztof Meyer|Krzysztofa Meyera]]. Jednostką miary jest w tym utworze [[ćwierćnuta]], a kolejne odcinki różnią się obsadą, 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<ref>T. Weselmann, ''Musica incrostata'', Poznań 2003, s. 58–60.</ref>.

Ciąg Fibonacciego używany jest też przez twórców spoza muzyki klasycznej, np. zespół [[Tool]] wykonujący muzykę z pogranicza [[Rock progresywny|rocka]] i [[Metal progresywny|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]] [[Dan Brown|Dana Browna]] stanowi on element jednego z kodów, który muszą złamać główni bohaterowie. W powieści ''[[Gniazdo światów]]'' [[Marek S. Huberath|Marka Huberatha]] ciąg Fibonacciego jest podstawą struktury wszechświata, na której oparte są kolejne jego poziomy.

Istnieją też utwory poetyckie nawiązujące formą do ciągu Fibonacciego. Współczesny poeta polski [[Marcin Orliński]] (na potrzeby czasopisma satyrycznego) nazwał ten gatunek ''fibonagramem''<ref>{{Cytuj |autor = Marcin Orliński |tytuł = Gad zapił bezę |czasopismo = Przekrój |wolumin = 2019 |numer = 2}}</ref>. W obrębie ''fibonagramu'' wyróżnił ''fibonagram literowy'' (liczba liter w kolejnych wyrazach odpowiada wartości kolejnych wyrazów w ciągu) i ''fibonagram wyrazowy'' (liczba słów w wersie odpowiada wartości kolejnych wyrazów w ciągu).

== Uwagi ==
{{Uwagi}}

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
{{Commonscat|Fibonacci numbers}}

; Polskojęzyczne
* {{Pismo Delta | url = 2012/05/ciag-fibonacciego/ | autor = Joanna Jaszuńska | tytuł = Ciąg Fibonacciego | data = maj 2012 | data dostępu = 2024-10-30}}
* {{otwarty dostęp}} Antoni Długosz, ''[http://www.deltami.edu.pl/temat/matematyka/teoria_liczb/2016/12/29/Dywany_Antoniego/ Dywany Antoniego – nie tylko bajka o pewnych zastosowaniach ciągu Fibonacciego]'', deltami.edu.pl.
* {{otwarty dostęp}} Karol Gryszka, ''[http://www.deltami.edu.pl/2021a/02/2021-02-delta-art-03-gryszka.pdf Ułamki Fibonacciego]'', deltami.edu.pl [dostęp 2021-02-10] – artykuł m.in. o ciągu Fibonacciego w rozwinięciach dziesiętnych.
* {{otwarty dostęp}} ''[https://www.youtube.com/watch?v=chnQgMlvSs4 Ciąg Fibonacciego]'', [[Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej]] (MiNI [[Politechnika Warszawska|PW]]), kanał „Archipelag Matematyki” na [[YouTube]], 23 sierpnia 2017 [dostęp 2024-09-04].

; Anglojęzyczne
* {{MathWorld|adres=FibonacciNumber |tytuł=Fibonacci Number |data dostępu=12 grudnia 2020}}
* [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html Formuły związane z ciągiem Fibonacciego]
* [http://oeis.org/classic/A000045 Ciąg Fibonacciego] w [[On-Line Encyclopedia of Integer Sequences]]

{{Ciągi liczbowe}}
{{Typy liczb naturalnych}}
{{Stałe matematyczne}}

{{Kontrola autorytatywna}}

[[Kategoria:Teoria liczb]]
[[Kategoria:Teoria muzyki]]
[[Kategoria:Przykłady ciągów liczbowych|F]]