Ciąg Fibonacciego

Wykres funkcji dla pierwszych dziesięciu wyrazów ciągu Fibonacciego

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 & \mbox{dla } n = 0; \\ 1 & \mbox{dla } n = 1; \\ F_{n-1}+F_{n-2} & \mbox{dla } n > 1. \\ \end{cases}$

Kolejne wyrazy tego ciągu nazywamy liczbami Fibonacciego. Kwestia, czy zaliczać zero do ciągu Fibonacciego, jest dyskusyjna. Część autorów rozpoczyna ciąg od $F_1=1, F_2=1\;$.

Wyrazy $F_0,\dots, F_{19}$ ciągu Fibonacciego to:

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

Ciąg został podany w 1202 roku przez Leonarda z Pizy zwanego Fibonaccim w swoim 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.

Zdefiniujmy ciąg $f_n := F_{n+1}\,$ i dla tego ciągu $f_n$ obliczmy wzór na jego n-ty wyraz.

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:

$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)\,$

tak więc: $s(x) = \frac{1}{1 - x - x^2}$

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

gdzie $a={1 + \sqrt{5} \over 2}$ $b={1 - \sqrt{5} \over 2}$ $A={a \over a-b}$ $B={-b \over 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 {(a^{n+1} - b^{n+1}) \over (a-b)}x^n$ tak więc $f_n = {(a^{n+1} - b^{n+1}) \over (a-b)}$

Podstawiając $F_n=f_{n-1}\,$ otrzymujemy ostatecznie tzw. formułę Bineta lub też wzór 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$

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}^n{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}6 F_{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} = (-1)^{n+1} F_{n-1} + 1$

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

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ą 1 i 144.
• 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. 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₀, F₁, F₂ i tak aż do F_n, za każdym razem korzystając z tego, co już obliczyliśmy. Nie musimy 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 Fibonacci'ego

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\ge 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ż istnieją bardzo wydajne algorytmy potęgowania macierzy, możemy wyliczyć dowolny wyraz ciągu Fibonacciego za pomocą logarytmicznej ilości mnożeń.

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+\frac1x$

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 & \mbox{dla } n = 0; \\ b & \mbox{dla } n = 1; \\ G(n-1)+G(n-2) & \mbox{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 \Bbb 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 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \cdots}}}$

wartościami kolejnych odcinków są liczby:

$\frac{1}{1} = 1 \qquad \frac{2}{1} = 1+\frac{1}{1} \qquad \frac{3}{2} = 1+\frac{1}{1+ \frac{1}{1}} \qquad \frac{5}{3} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1}}} \qquad \frac{8}{5} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{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 & \mbox{dla } n = 0; \\ 1 & \mbox{dla } n = 1; \\ L(n-1)+L(n-2) & \mbox{dla } n > 1. \\ \end{cases}$

Zachodzą równości:

$L_n=F_{n-1}+F_{n+1}\,$

$F_n = \begin{matrix}\frac{1}{5}\end{matrix}(L_{n-1}+L_{n+1})$.

$F_{n+1} = \begin{matrix}\frac{1}{2}\end{matrix}(F_n+L_n)$.

$F_{2n} = F_n L_n\,$.

$F_{m+n} = \begin{matrix}\frac{1}{2}\end{matrix}(F_m L_n + F_n L_m)$.

$F_{m-n} = \begin{matrix}\frac{1}{2}\end{matrix}(-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³ − x² − x − 1 oraz równania x + x⁻³ = 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⁴ − x³ − x² − x − 1 oraz równania x + x⁻⁴ = 2 i wynosi ok. 1,92756.

Słowa Fibonacciego

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

$F_n = \begin{cases} b & \mbox{dla } n = 1; \\ a & \mbox{dla } n = 2; \\ F_{n-1} \cdot F_{n-2} & \mbox{dla } n > 2,\mbox{ gdzie } \cdot \mbox{ 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. Ciąg Fibonacciego przypisuje się proporcjom części w skrzypcach budowanym przez Antonio Stradivariego^{[potrzebne źródło]}. Przede wszystkim jednak 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 został użyty również we współczesnej muzyce. Zespół Tool 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

• Liczba Fibonacciego (ang.) w encyklopedii MathWorld
• Formuły związane z ciągiem Fibonacciego
• Ciąg Fibonacciego w On-Line Encyclopedia of Integer Sequences