Ciąg Fibonacciego [historia i autorzy]

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 nazywamy liczbami Fibonacciego. Kwestia, czy zaliczać zero do ciągu Fibonacciego, jest dyskusyjna. Część autorów rozpoczyna ciąg od .

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

Spis treści

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 i dla tego ciągu obliczmy wzór na jego n-ty wyraz.

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

Podstawiając otrzymujemy:

tak więc:

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

gdzie

wówczas tak więc

Podstawiając otrzymujemy ostatecznie tzw. formułę Bineta lub też wzór Eulera-Bineta:

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

Własności

Można też wyrazić wartości kolejnych elementów ciągu za pomocą symbolu Newtona :

Zachodzą równości:

(równanie ilustruje rysunek)
\sum_{k=1}^n F_k^3 = (F_{3n+2}+ (-1)^{n+1}6 F_{n-1}+5 )/10
, tzw. zależność Cassiniego (1680), która leży u podstaw zagadki brakującego kwadratu oraz uogólniona wersja:
, tzw. zależność Catalana

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

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

Ponieważ równocześnie:

to indukcyjnie:

lub w notacji wektorowej

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

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:

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

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

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

Zachodzą równości:

.
.
.
.
.

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 : (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"

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

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

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

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.

Pokaż ten artykuł na Wikipedia.pl

Tekst udostępniany na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Zobacz szczegółowe informacje o warunkach korzystania.
Zasady zachowania poufności. O Wikipedii. Korzystasz z Wikipedii tylko na własną odpowiedzialność. Materiał pochodzący z Wikipedii został zmodyfikowany poprzez ograniczenie liczby przypisów. Wikipedia® is a registered tradmark of the Wikimedia Foundation.

Kategorie dla tego artykułu