Ciąg Fibonacciego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Wykres funkcji dla pierwszych dziesięciu wyrazów ciągu Fibonacciego

Ciąg Fibonacciegocią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\;[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[2].

Wzór Bineta[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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}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)[3], która leży u podstaw zagadki brakującego kwadratu[4] oraz uogólniona wersja:
F_n^2 - F_{n-r}F_{n+r} = (-1)^{n-r}F_r^2, tzw. zależność Catalana[5]
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} [6]

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 Fn dzieli się przez Fk. 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[edytuj | edytuj kod]

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: F0, F1, F2 i tak aż do Fn, 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 x2x − 1 oraz równania x + x−2 = 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[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: liczba pierwsza Fibonacciego.

Kilka początkowych wyrazów w ciągu Fibonacciego to także liczby pierwsze[7], 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[edytuj | edytuj kod]

Ciąg Lucasa[edytuj | edytuj kod]

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"[edytuj | edytuj kod]

Różni się od ciągu Fibonacciego tym, że każdy kolejny jego wyraz powstaje przez zsumowanie poprzednich trzech wyrazów zamiast dwóch[8]. 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 x3x2x − 1 oraz równania x + x−3 = 2 i wynosi ok. 1,83929.

Ciąg "Tetranacciego"[edytuj | edytuj kod]

Różni się od ciągu Fibonacciego tym, każdy kolejny jego wyraz powstaje przez zsumowanie poprzednich czterech wyrazów zamiast dwóch[9]. 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 x4x3x2x − 1 oraz równania x + x−4 = 2 i wynosi ok. 1,92756.

Słowa Fibonacciego[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[10] 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[11]. 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[12].

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[edytuj | edytuj kod]

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.

Wikimedia Commons

Przypisy

  1. Zero jest zaliczane do ciągu Fibonacciego np. w książce Andrzej Mostowski, Marceli Stark: Elementy algebry wyższej. Wyd. 7. Warszawa: PWN, 1974, s. 16, seria: BM 16. Nie jest natomiast zaliczane do ciągu Fibonacciego w Wielkiej Encyklopedii Powszechnej PWN, 1964, tom 3, s. 636, link
  2. Andrzej Lenda "Liczby Fibonacciego"
  3. Donald Graham, Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: PWN, 2006, s. 326.
  4. Martin Gardner: Mathematics Magic and Mystery. Nowy York: Dover Publications, Inc., 1956.
  5. Harold Scott MacDonald Coxeter: Wstęp do geometerii starej i nowej. Warszawa: PWN, 1967.
  6. Henryk Pawłowski: Zadania z olimpiad matematycznych z całego świata. Teoria liczb, algebra i elementy analizy matematycznej. Toruń: Oficyna Wydawnicza "Tutor", 2005. ISBN 83-86007-21-4.
  7. A005478
  8. A000073
  9. A000078
  10. Lendvai, Ernő (1971). Béla Bartók: An Analysis of His Music. London: Kahn and Averill.
  11. B. Schaeffer Mały informator muzyki XX wieku, Kraków 1975, s. 121.
  12. T. Weselmann Musica incrostata, Poznań 2003, s. 58-60.

Linki zewnętrzne[edytuj | edytuj kod]