Ciąg kwadratów, których długości boków są kolejnymi liczbami Fibonacciego
Ciąg
Fibonacciego
–
ciąg
liczb naturalnych
określony
rekurencyjnie
w sposób następujący:
- Pierwsze dwa wyrazy ciągu równe są 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 [1].
Wyrazy 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ł 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
. Nazywanie tego ciągu jako ciąg Fibonacciego spopularyzował w XIX w.
Edward Lucas
[2].
Wzór Bineta
Jawny wzór na n-ty wyraz ciągu Fibonacciego możemy otrzymać np. korzystając z metody
funkcji tworzących
.
Zdefiniujmy ciąg i dla tego ciągu fn 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:
gdzie
wówczas tak więc
Podstawiając otrzymujemy ostatecznie tzw. wzór 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)
Kilka mniej znanych twierdzeń na temat ciągu Fibonacciego:
- Z wyjątkiem jednocyfrowych liczb Fibonacciego (liczb występujących w 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 n dla których zachodzi podzielność n | Fn. 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 Fn 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 Fn 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
Można zrobić to jeszcze szybciej dzięki zależności:
Ponieważ równocześnie:
to
indukcyjnie
:
A ponieważ istnieją bardzo wydajne algorytmy
potęgowania macierzy
, możemy wyliczyć dowolny wyraz ciągu Fibonacciego za pomocą logarytmicznej ilości mnożeń. Stanowi to ogromny kontrast wobec wykładniczej ilości (co prawda szybszych) dodawań najbardziej naiwnej metody.
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
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
- Dowód (zakładający istnienie takiej granicy):
Jest ona także pierwiastkiem wielomianu x² − x − 1 oraz równania x + x−2 = 2
Zauważmy, że w powyższym dowodzie informacja o początkowych wyrazach ciągu czy też jakichkolwiek innych nie była wykorzystywana. Przeto 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
[3] 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[4]. 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 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−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[5]. 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 T(n) jest n-tym wyrazem ciągu 'Tetranacciego'). Jest ona pierwiastkiem wielomianu x4 − x³ − x² − x − 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 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[6] 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 stretty - 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[7]. 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[8].
Ciąg Fibonacciego w kulturze popularnej
Przypisy
- ↑ 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
- ↑
Liczby Fibonacciego
- ↑
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.
- ↑
FAQ for The Da Vinci Code
(
ang.
). [dostęp 2010-03-16].
Zobacz też
Linki zewnętrzne