Ciąg Fibonacciego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Wykres funkcji dla pierwszych ośmiu wyrazów ciągu Fibonacciego (F0 .. F7)

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:

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 F1 = F2 = 1[1].


Pierwsze dwadzieścia wyrazów 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ł 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[2].

Wzór Bineta[edytuj]

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

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

Podstawiając otrzymujemy:

W szczególności,

Wyrażenie można przedstawić w prostszej postaci, mianowicie:

gdzie

Wówczas

a stąd

Ponieważ , wyprowadzony został ostatecznie tzw. wzór Bineta zwany czasem wzorem Eulera-Bineta:

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

Znaczenia kombinatoryczne[edytuj]

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

Własności[edytuj]

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 :

Zachodzą równości:

Ciąg kwadratów, których długości boków są kolejnymi liczbami Fibonacciego
(równanie ilustruje rysunek)
, tzw. zależność Cassiniego (1680)[3], która leży u podstaw zagadki brakującego kwadratu[4] oraz uogólniona wersja:
, tzw. zależność Catalana[5]
[6]

Dowód: W zapisie jako sumy jedynek i dwójek jest nieparzysta liczba jedynek. Lewa strona równości stanowi zliczanie liczby zapisów , w którym parametry i 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ą 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. Dokładniej:
Jeśli , to: .

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

  • Każda niezerowa liczba całkowita ma wielokrotność będącą liczbą Fibonacciego.
  • Istnieje nieskończenie wiele liczb , dla których zachodzi podzielność . W szczególności można pokazać, że jeśli to .

Obliczanie liczb Fibonacciego[edytuj]

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 wielokrotnie odwołuje się do wartości poprzednich wyrazów ciągów. Drzewo wywołań takiego algorytmu dla parametru musi mieć co najmniej 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 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[edytuj]

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

Ponieważ równocześnie:

to indukcyjnie:

lub w notacji wektorowej

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 , tzn. obliczenie wymaga ilości mnożeń (symbol oznacza asymptotyczne tempo wzrostu).

Graficzna reprezentacja dwójkowa[edytuj]

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]

Granica ciągu:

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 :

lub równoważnego

czyli

.

Dowód[edytuj]

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

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

zachodzi wzór: 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 jest taka sama jak dla oryginalnego ciągu Fibonacciego.

Kolejne wyrazy ciągu: są także wartością n-tego odcinka ułamka łańcuchowego:

wartościami kolejnych odcinków są liczby:

Liczby pierwsze w ciągu Fibonacciego[edytuj]

 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]

Ciąg Lucasa[edytuj]

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

Zachodzą równości:

.
.
.
.
.

Ciąg "Tribonacciego"[edytuj]

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 : (gdzie 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]

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 : (gdzie 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]

 Osobny artykuł: Słowa Fibonacciego.

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

Ciąg Fibonacciego w biologii[edytuj]

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]

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[potrzebny przypis]. 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]

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.

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. Ronald Graham, Donald 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]