Ciąg 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:
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 [1].
Pierwsze dwadzieścia wyrazów ciągu Fibonacciego to:
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].
Spis treści
- 1 Wzór Bineta
- 2 Znaczenia kombinatoryczne
- 3 Własności
- 4 Obliczanie liczb Fibonacciego
- 5 Macierze liczb Fibonacciego
- 6 Graficzna reprezentacja dwójkowa
- 7 Złota liczba
- 8 Liczby pierwsze w ciągu Fibonacciego
- 9 Pokrewne ciągi
- 10 Ciąg Fibonacciego w biologii
- 11 Ciąg Fibonacciego w muzyce
- 12 Ciąg Fibonacciego w literaturze
- 13 Przypisy
- 14 Linki zewnętrzne
Wzór Bineta[edytuj | edytuj kod]
Jawny wzór na -ty wyraz ciągu Fibonacciego podany w 1843 r. 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 | edytuj kod]
- 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 | edytuj kod]

Można też wyrazić wartości kolejnych elementów ciągu za pomocą symbolu Newtona:
Zachodzą równości:
- (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:
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ą 0, 1 i 144[potrzebny przypis].
- Co trzecia liczba Fibonacciego jest podzielna przez 2, co czwarta – przez 3. Ogólniej: jeśli numer dzieli się przez to liczba dzieli się przez 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 | 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 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: i tak aż do 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 | edytuj kod]
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 | edytuj kod]

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]
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 | 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ć.
Jest ona także pierwiastkiem wielomianu oraz równania
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ą -tego odcinka ułamka łańcuchowego:
wartościami kolejnych odcinków są liczby:
Liczby pierwsze w ciągu Fibonacciego[edytuj | edytuj kod]
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
Zachodzą równości:
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: (gdzie jest -tym wyrazem ciągu „Tribonacciego”), czyli analogiem złotej liczby dla ciągu Fibonacciego. Jest ona pierwiastkiem wielomianu oraz równania 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: (gdzie jest -tym wyrazem ciągu „Tetranacciego”). Jest ona pierwiastkiem wielomianu oraz równania i wynosi ok. 1,92756.
Słowa Fibonacciego[edytuj | edytuj kod]
Ciąg słów Fibonacciego to ciąg słów
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. 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.
Przypisy[edytuj | edytuj kod]
- ↑ 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.
- ↑ Andrzej Lenda „Liczby Fibonacciego”.
- ↑ Ronald Graham, Donald Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: PWN, 2006, s. 326.
- ↑ Martin Gardner: Mathematics Magic and Mystery. Nowy York: Dover Publications, Inc., 1956.
- ↑ Harold Scott MacDonald Coxeter: Wstęp do geometrii starej i nowej. Warszawa: PWN, 1967.
- ↑ Henryk Pawłowski: Zadania z olimpiad matematycznych z całego świata. Teoria liczb, algebra i elementy analizy matematycznej. Toruń: Oficyna Wydawnicza „Tutor”, 2005, s. 206–207. ISBN 83-86007-21-4.
- ↑ A005478.
- ↑ A000073.
- ↑ A000078.
- ↑ Lendvai, Ernő (1971). Béla Bartók: An Analysis of His Music. London: Kahn and Averill.
- ↑ B. Schaeffer, Mały informator muzyki XX wieku, Kraków 1975, s. 121.
- ↑ T. Weselmann, Musica incrostata, Poznań 2003, s. 58–60.
Linki zewnętrzne[edytuj | edytuj kod]
- 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
|