Ciąg Fibonacciego

Z Wikipedii

Ciąg kwadratów, których długości boków są kolejnymi liczbami Fibonacciego

Zobacz w Wikiźródłach tablicę ciągu Fibonacciego

Ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący:

$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:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.

[edytuj] 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 $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. wzór 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$

[edytuj] Własności

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

$F_n = \sum_{k=1}^n{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$

$\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$

$F_{n+1}F_{m} + F_n F_{m-1} = F_{m+n}\,$

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

[edytuj] 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 $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: F₀, F₁, F₂ i tak aż do F_n, 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:

$\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$

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.

Zobacz w Wikiźródłach implementacje algorytmów obliczających ciąg Fibonacciego

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

[edytuj] Złota liczba

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}$

Dowód (zakładający istnienie takiej granicy):

$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 x² − x − 1 oraz równania x + x⁻² = 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

$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}}}}$

[edytuj] Liczby pierwsze w ciągu Fibonacciego

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

[edytuj] Pokrewne ciągi

[edytuj] Ciąg Lucasa

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

[edytuj] 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^[3]. 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 x³ − x² − x − 1 oraz równania x + x⁻³ = 2 i wynosi ok. 1.83929.

[edytuj] 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^[4]. 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 x⁴ − x³ − x² − x − 1 oraz równania x + x⁻⁴ = 2 i wynosi ok. 1.92756.

[edytuj] 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. \\ \end{cases}$

[edytuj] 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^{[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^[5] 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^[6]. 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.^[7]

[edytuj] 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. U wielu roślin kwiatowych, których wzrost następuje wzdłuż linii spiralnych, liczba płatków wyraża się którąś z liczb Fibonacciego. Jaskry mają po 5 płatków, kwiaty sangwinarii po 8 płatków, kwiaty wielu gatunków z rodzaju starzec po 13, astry często po 21, niektóre złocienie po 34, a aster nowoangielski po 55 lub po 89. Ponadto liczby Fibonacciego często powtarzają się w opisach budowy owoców i warzyw. Na przykład przekrój poprzeczny banana jest pięciokątem.

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

[edytuj] Zobacz też

przegląd zagadnień z zakresu matematyki

[edytuj] Linki zewnętrzne

[zero-0] 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

[1] A005478

[2] A000073

[3] A000078

[4] Lendvai, Ernő (1971). Béla Bartók: An Analysis of His Music. London: Kahn and Averill

[5] B. Schaeffer Mały informator muzyki XX wieku, Kraków 1975, s. 121.

[6] T. Weselmann Musica incrostata, Poznań 2003, s. 58-60.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Ciąg Fibonacciego

Z Wikipedii

Spis treści

[edytuj] Wzór Bineta

[edytuj] Własności

[edytuj] Obliczanie liczb Fibonacciego

[edytuj] Graficzna reprezentacja dwójkowa

[edytuj] Złota liczba

[edytuj] Liczby pierwsze w ciągu Fibonacciego

[edytuj] Pokrewne ciągi

[edytuj] Ciąg Lucasa

[edytuj] Ciąg "Tribonacciego"

[edytuj] Ciąg "Tetranacciego"

[edytuj] Słowa Fibonacciego

[edytuj] Ciąg Fibonacciego w muzyce

[edytuj] Ciąg Fibonacciego w biologii

Przypisy

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Widok

Osobiste

Szukaj

Nawigacja

Dla czytelników

Dla edytorów

Utwórz książkę

Narzędzia

W innych językach