Ciąg Fibonacciego.

Zbiór informacji o elementarnych zagadnieniach matematyki, klasyfikowanych najczęściej jako "ciekawostki" właśnie...
Awatar użytkownika
Tomasz Rużycki
Użytkownik
Użytkownik
Posty: 2970
Rejestracja: 8 paź 2004, o 17:16
Płeć: Mężczyzna
Lokalizacja: Suchedniów/Kraków
Podziękował: 4 razy
Pomógł: 293 razy

Ciąg Fibonacciego.

Post autor: Tomasz Rużycki »

1. Rekurencyjne określenie ciągu Fibonacciego.

\(\displaystyle{ F_1=1}\)
\(\displaystyle{ F_2=1}\)
\(\displaystyle{ F_{n+1}=F_{n}+F_{n-1}}\)

Kilka pierwszych wyrazów ciągu: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Jest to prosta rekurencja - każda liczba zależy od dwóch poprzednich - jest ich sumą.

2. Postać jawna ciągu Fibonacciego.

\(\displaystyle{ F_n=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2}\right)^n-\left( \frac{1-\sqrt{5}}{2}\right) ^n\right) }\)

Jest to tak zwany wzór Bineta. Otrzymujemy go przez rozwiązanie rekurencji z punktu 1-szego, ale o tym może innym razem:)

3. Tożsamości.

\(\displaystyle{ F_1+F_2+...+F_n=F_{n+2}-1}\)

\(\displaystyle{ F_1+F_3+...+F_{2n-1}=F_{2n}}\)

\(\displaystyle{ F_2+F_4+...+F_{2n}=F_{2n+1}-1}\)

\(\displaystyle{ F_1-F_2+F_3-F_4+...+(-1)^{n+1}F_n=(-1)^{n+1}F_{n-1}+1}\)

\(\displaystyle{ F_1^2+F_2^2+F_3^2+...+F_n^2=F_n F_{n+1}}\)

\(\displaystyle{ F_{n+m}=F_{n-1}F_m+F_n F_{m+1}}\)

\(\displaystyle{ F_{2n}=F_{n+1}^2-F_{n-1}^2}\)

\(\displaystyle{ F_n^2=F_{n-1}F_{n+1}+(-1)^{n+1}}\)

\(\displaystyle{ F_1 F_2+F_2 F_3+...F_{2n-1}F_{2n}=F_{2n}^2}\)

\(\displaystyle{ F_1 F_2 + F_2 F_3+... + F_{2n}F_{2n+1}=F_{2n+1}^2-1}\)

\(\displaystyle{ nF_1+(n-1)F_2+...+2F_{n-1}+F_n=F_{n+4}-(n+3)}\)

\(\displaystyle{ F_1+2F_2+...+nF_n=nF_{n+2}-F_{n+3}+2}\)

\(\displaystyle{ NWD(F_n, F_{n+1})=1}\)

\(\displaystyle{ NWD(F_m,F_n)=F_{NWD(m,n)}}\)

\(\displaystyle{ \mbox{Jeśli }n|m, \mbox{ to } F_n|F_m}\)

\(\displaystyle{ \sum\limits_{k=0}^{n-1}{n\choose k}F_{n-k}=F_{2n}}\)

\(\displaystyle{ F_{3m} = F_m^{3} + F_{m+1}^{3} - F_{m-1}^{3}}\)

\(\displaystyle{ F_{n}^4 = 1+ F_{n-2}F_{n-1}F_{n+1}F_{n+2}}\)

\(\displaystyle{ \binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{1}+\ldots= F_{n+1}.}\)

\(\displaystyle{ \phi^n=F_{n}\phi+F_{n-1}, \ (n\geq 2) \mbox{ gdzie } \phi \mbox{ spełnia zależność }\phi^2=\phi+1}\)

\(\displaystyle{ \left[\begin{array}{cc} 1 & 1 \\ 1 & 0\end{array}\right]^{n} = \left[\begin{array}{cc} f_{n+1} & f_{n} \\ f_{n} & f_{n - 1}\end{array}\right]}\)



Pozdrawiam,
--
Tomek Rużycki
Ostatnio zmieniony 5 wrz 2008, o 17:17 przez Tomasz Rużycki, łącznie zmieniany 1 raz.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Ciąg Fibonacciego.

Post autor: mol_ksiazkowy »

Suma kolejnych (więcej niż dwóch) wyrazów ciągu Fibonacciego nie jest wyrazem ciągu Fibonacciego:
\(\displaystyle{ F_n + F_{n+1}+…+F_{n+k} \neq F_m}\) dla \(\displaystyle{ k>1}\).
\(\displaystyle{ F_n = m^3}\) gdzie \(\displaystyle{ m, n \in \mathbb{N}}\) jest tylko gdy \(\displaystyle{ m=1}\) lub \(\displaystyle{ m=2}\).
W ciągu \(\displaystyle{ 8n+4}\) nie ma żadnej liczby Fibonacciego .
Jeśli \(\displaystyle{ F_n^2}\) dzieli \(\displaystyle{ F_m}\) tylko wtedy, gdy \(\displaystyle{ nF_n}\) dzieli \(\displaystyle{ F_m}\) gdy \(\displaystyle{ n>2}\).(Matijasewicz)
Jeśli \(\displaystyle{ k \in \mathbb{N}}\), to liczby \(\displaystyle{ kF_{n+2} + F_n}\) oraz \(\displaystyle{ kF_{n+3} + F_{n+1}}\) są względnie pierwsze.
Co ósmy wyraz ciągu Fibonacciego jest podzielny przez \(\displaystyle{ 7}\); itd.
Dowolne dwie kolejne liczby Fibonacciego (tj. \(\displaystyle{ F_n}\) i \(\displaystyle{ F_{n+1}}\)) są względnie pierwsze.
Interpretacja kombinatoryczna: to ilość takich podzbiorów zbioru \(\displaystyle{ \left\{ 1, ..., n \right\}}\), które nie mają żadnych kolejnych elementów. (np. gdy \(\displaystyle{ n=5}\) jest ich \(\displaystyle{ 13}\): \(\displaystyle{ \emptyset, \left\{ 1 \right\} , \left\{ 2 \right\} , \left\{ 3 \right\} , \left\{ 4 \right\} , \left\{ 5 \right\} , \left\{ 1, 3 \right\} , \left\{ 1, 4 \right\} , \left\{ 1, 5 \right\} , \left\{ 2, 4 \right\} , \left\{ 2, 5 \right\} , \left\{ 3, 5 \right\} , \left\{ 1, 3, 5 \right\}}\) ).
Jeśli nie uwzględni się tych podzbiorów, które maja w sobie elementy \(\displaystyle{ 1}\) oraz \(\displaystyle{ n}\), to uzyska się liczbę Lucasa \(\displaystyle{ L_n}\) (\(\displaystyle{ L_5 =11}\) ).

c. F: \(\displaystyle{ 1, \ 1, \ 2, \ 3, \ 5, \ 8 , \ 13, \ 21, \ 34, \ 55, \ 89, \ 144, \ 233, \ 377, \ 610, \ 987, \ 1597, \ 2584, \ 4181, \ 6765 , \ 10946, \ 17711…}\)
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.
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, … Wynika to z tego, że definicja \(\displaystyle{ F_n}\) wielokrotnie odwołuje się do wartości poprzednich wyrazów ciągów. Drzewo wywołań takiego algorytmu dla parametru \(\displaystyle{ n}\) musi mieć co najmniej \(\displaystyle{ F_n}\) liści o wartości \(\displaystyle{ 1}\).
Ukryta treść:    
Zarówno wzór rekurencyjny jak i Lucasa jest więc nieefektywny. (chcąc np. obliczyć \(\displaystyle{ F_{30}}\)) trzeba zrobić 29 operacji dodawania coraz to większych liczb, bądź też sumowania 14 składników, które trzeba obliczać osobno*:
\(\displaystyle{ F_n = {n - 1 \choose 0} + {n - 2 \choose 1} +…+ {n - j \choose j-1} + {n - j-1 \choose j}}\) gdzie \(\displaystyle{ j=\left\lfloor \frac{n-1}{2} \right\rfloor}\)
tj. tzw. wzór Lucasa.
*Inną metodą może być tu użycie ciągu Lucasa (np. \(\displaystyle{ F_{30}=F_{15}L_{15}}\)) itp.

Jeśli \(\displaystyle{ \phi = 1+ \frac{1}{1 + \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ ...}}}}}\) tj. \(\displaystyle{ \phi = 1+ \frac{1}{\phi}}\) tj. \(\displaystyle{ \phi = \frac{1+ \sqrt{5}}{2} \approx 1, 618}\) to
\(\displaystyle{ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - \left( -\phi \right) ^{-n} \right)}\) Binet;
Wynika to z tożsamości: \(\displaystyle{ F_{n+1} - xF_n = \left( 1-x \right) \left( F_n - xF_{n-1} \right) + \left( 1+x-x^2 \right) F_{n-1}}\)

\(\displaystyle{ F_{n}}\) jest więc taką liczbą całkowitą, która jest najbliżej \(\displaystyle{ n}\) tego wyrazu ciągu \(\displaystyle{ a_n = \frac{\phi^n}{\sqrt{5}}}\), np. \(\displaystyle{ F_8 =21}\) zaś \(\displaystyle{ a_8 = \frac{\phi^8}{\sqrt{5}}= \frac{21\phi + 13}{\sqrt{5}} \approx 21,01}\).
Ukryta treść:    
Można też określić \(\displaystyle{ F_n}\) gdy \(\displaystyle{ n}\) jest liczbą całkowitą ujemną, tj. \(\displaystyle{ F_{ - n} = F_n \left( -1 \right) ^{n+1}}\) dla \(\displaystyle{ n>0}\) i wtedy \(\displaystyle{ F_{n+1} = F_{n}+ F_{n-1}}\) dla \(\displaystyle{ n \in \mathbb{Z}}\).

\(\displaystyle{ \sum_{j=0}^{n-1} {n \choose k}F_{n-k} = F_{2n} \\
F_{3n} = F_{n+1}^3 + F_n^3 - F_{n-1}^3 \\
F_n^4 = 1+ F_{n-2}F_{n-1} F_{n+1}F_{n+2} \text{ dla } n>1 \text{ Casàro } \\
\sum_{k=0}^n \frac{F_{k+2}}{F_{k+1}F_{k+3}} = \frac{F_4}{F_2F_3} - \frac{F_{2n+4}}{F_{2n+2}F_{2n+3}} \\
\arctan \left( F_{2n+1} \right) + \arctan \left( F_{2n+2} \right) = \arctan \left( F_{2n} \right) \\
F_{2n}= F_{n+1}^2 - F_{n-1}^2 \\
F_{2n+1}=F_n^2+ F_{n+1}^2 \\
\text{ oraz } F_{n+1}^2 - F_{n-2}^2 =4F_nF_{n-1}}\)

1) Kwadrat każdego wyrazu ciągu Fibonacciego różni się od iloczynu wyrazów sąsiednich o \(\displaystyle{ \pm 1}\).
2) Dla każdych czterech kolejnych wyrazów iloczyny wyrazów skrajnych i środkowych różnią się o \(\displaystyle{ \pm 1}\).
3) Dla każdych kolejnych pięciu wyrazów kwadrat wyrazu środkowego, iloczyn jego wyrazów będących obok siebie i iloczyn skrajnych są kolejnymi liczbami naturalnymi.
4) Suma kolejnych wyrazów ciągu Fibonacciego jest liczbą Fibonacciego pomniejszoną o \(\displaystyle{ 1}\).
1) np. \(\displaystyle{ F_{13}^2 - F_{12}F_{14} = F_{13} \left( F_{11} + F_{12} \right) - F_{12} \left( F_{12} + F_{13} \right) = - \left( F_{12}^2 - F_{10}F_{13} \right) = 1}\)

4) np. jeśli \(\displaystyle{ F_1 + F_2 + F_3 = F_5 - 1}\) to \(\displaystyle{ F_1 + F_2 + F_3 +F_4 +F_5 = F_5 - 1 + F_4+ F_5 = F_5 - 1 + F_6 = F_7 - 1}\) itd.

\(\displaystyle{ \sum_{j=1}^n jF_j = \left( n+1 \right) F_{n+2} - F_{n+4} +2}\)
\(\displaystyle{ \left( F_n,F_{n+3} \right) ^2 + \left( 2F_{n+1}F_{n+2} \right) ^2 = F_{2n+3}^3}\)

\(\displaystyle{ F_n^2 - F_{n-r}F_{n+r}= \left( -1 \right) ^{n-r}F_r^2}\) Catalan

Rekurencja \(\displaystyle{ F_{n+1}}\) a \(\displaystyle{ F_{n}}\)
\(\displaystyle{ F_{n+1} = \lfloor \frac{F_n \left( 1+ \sqrt{5} \right) + 1}{2} \rfloor}\)

uogólnienie: \(\displaystyle{ F_{a}F_{b} - F_{c}F_{d}= \left( -1 \right) ^r \left( F_{a-r}F_{b-r} - F_{c-r}F_{d-r} \right)}\) o ile \(\displaystyle{ a+b=c+d}\)

\(\displaystyle{ \sum_{j=1}^n F_j^2 = F_nF_{n+1}}\)
Kwadraty o bokach równych liczbom Fibonacciego tworzą prostokąt Fibonacciego; wpisując w nie ćwiartki okręgów otrzyma się tzw. spiralę Fibonacciego.
\(\displaystyle{ \sum_{j=1}^n F_j^3 = \frac{1}{10}F_{3n+2} + \left( -1 \right) ^{n+1}\frac{3}{5}F_{n-1}+ \frac{1}{2}}\)

\(\displaystyle{ F_n^2 - F_{n-1}F_{n+1} = \left( -1 \right) ^{n+1}}\) lub równoważnie tak: \(\displaystyle{ \frac{F_{n+1}}{F_n} - \frac{F_{n}}{F_{n-1}}= \frac{ \left( -1 \right) ^n}{F_nF_{n+1}}}\) tj. \(\displaystyle{ \lim \frac{F_{n+1}}{F_n} = \phi}\) (oscylująco ale intensywnie; np. \(\displaystyle{ \frac{F_{10}}{F_9}= \frac{55}{34} \approx 1, 6176 \ \frac{F_{11}}{F_{10}}= \frac{89}{55} \approx 1, 6182 \ \frac{F_{12}}{F_{11}}= \frac{144}{89} \approx 1, 6179}\) etc.)
Tożsamość ta (Catalan z \(\displaystyle{ r=1}\)) wiąże się z tzw. zagadką brakującego kwadratu.

Formuła \(\displaystyle{ F_n}\) z liczbami zespolonymi: \(\displaystyle{ F_n= \prod_{k=1}^{n-1} \left( 1- 2i\cos \left( \frac{k\pi}{n} \right) \right)}\)

Funkcja \(\displaystyle{ f}\) ciągu Fibonacciego
\(\displaystyle{ f \left( z \right) =\sum_{j=1} F_jz^j = z+ z^2+ 2z^3 + 3z^4 +...=\frac{z}{1 - z - z^2}}\)

Twierdzenie Każda liczba całkowita nieujemna \(\displaystyle{ n>2}\) jest sumą różnych wyrazów ciągu Fibonacciego
Istnieje więc (jednoznaczność rozkładu) system Fibonacciego:
\(\displaystyle{ n = \left( c_m c_{m-1}...c_2 \right) _F \iff n = \sum_{j=2}^m c_jF_j}\) oraz \(\displaystyle{ c_j \in \left\{ 0, 1 \right\}}\)
np. \(\displaystyle{ 1202 = F_{16}+ F_{12}+ F_{10}+ F_{7}+ F_{4}}\) a wiec \(\displaystyle{ 1202 = \left( 100010100100100 \right) _F}\). Rozkład taki jest łatwo wyznaczać: oblicza się największą liczbę Fibonacciego \(\displaystyle{ F_k}\) mniejszą od \(\displaystyle{ n}\) i wyznacza się w ten sam sposób rozkład \(\displaystyle{ n - F_k}\) etc.
(tu: \(\displaystyle{ k=16}\) gdyż \(\displaystyle{ F_{16}=987 < 1202}\) ale \(\displaystyle{ F_{17}> 1202}\))

algorytm

Kod: Zaznacz cały

a:=2; 
b:=1; 
for j:=1 to n do begin
    a:=a+b; 
    b:=a-b;
end;
fib:= b; 
słowo Fibonacciego
Jeśli \(\displaystyle{ F_n = \begin{cases} b &\text{dla } n=1 \\ a &\text{dla } n= 2\\ F_{n-1} \cdot F_{n-2} &\text{dla } n>2\end{cases}}\)
tj. np. \(\displaystyle{ F_3=F_2F_1 =ab \ F_4=F_3F_2 =aba \ F_5= F_4F_3=abaab}\) itd. Każde słowo \(\displaystyle{ F_n}\) składa się tylko z liter \(\displaystyle{ a}\) i \(\displaystyle{ b}\) i jest „językową sumą” dwóch poprzednich słów.

Uogólniony ciąg Fibonacciego
\(\displaystyle{ \begin{cases}f_0= a \\ f_1 = b\\ f_{n+2}=Af_{n+1}+ Bf_n\end{cases}}\)

tj. jeśli \(\displaystyle{ f_0= 0 \ f_1 = 1}\) oraz \(\displaystyle{ A = B= 1}\) to \(\displaystyle{ f_n = F_n.}\)

Jeśli \(\displaystyle{ A^2+ 4B \neq 0}\) to \(\displaystyle{ f_n= \frac{\alpha^n - \beta^n }{\alpha - \beta}b - \frac{\alpha^{n-1} - \beta^{n-1}}{\alpha - \beta}aB}\) gdzie \(\displaystyle{ \alpha}\) i \(\displaystyle{ \beta}\) spełniają \(\displaystyle{ x^2=Ax + B}\), \(\displaystyle{ \alpha \neq \beta}\). (zmiennej \(\displaystyle{ A}\) nie ma „jawnie” w tym wzorze, ale jest „ukryta” w \(\displaystyle{ \alpha}\) i \(\displaystyle{ \beta}\))
Jeśli \(\displaystyle{ A^2+ 4B = 0}\) to \(\displaystyle{ f_n = nb \left( \frac{A}{2} \right) ^{n-1} - \left( n-1 \right) \left( \frac{A}{2} \right) ^{n}}\)


ciąg Lucasa
\(\displaystyle{ \begin{cases} L_1 = 1\\ L_2 = 3 \\ L_{n+2}=L_{n+1}+ L_n \end{cases}}\)
Ciag Lucasa jest więc u.c. F (\(\displaystyle{ a=1 \ b=3 \ A=B=1}\)).

c. L: \(\displaystyle{ 1, \ 3, \ 4, \ 7, \ 11, \ 18, \ 29, \ 47, \ 76, \ , 123, \ 199, \ 322, \ 521, \ …}\)
Istnieje różne analogie (ale też i różnice) między \(\displaystyle{ F_n}\) a \(\displaystyle{ L_n}\) np.
\(\displaystyle{ L_n= \left( \frac{1+ \sqrt{5}}{2} \right) ^n + \left( \frac{ 1- \sqrt{5}}{2} \right) ^n = \lfloor \phi^n \rfloor}\) (Binet); uogólnienie na indeksy ujemne: \(\displaystyle{ L_{-n} = \left( -1 \right) ^nL_n}\) oraz np. \(\displaystyle{ L_n^2 - L_{n-1}L_{n+1} = 5 \left( -1 \right) ^n}\) lub \(\displaystyle{ \frac{L_{n+1}}{L_n} - \frac{L_{n}}{L_{n-1}}= \frac{5 \left( -1 \right) ^n}{L_nL_{n+1}}}\)

\(\displaystyle{ \begin{cases} L_1^2+ … +L_n^2=L_nL_{n+1}-2\\F_mL_n=F_{m+n} + \left( -1 \right) ^nF_{m-n}\\F_{m}F_n = \frac{1}{5} \left( L_{m+n} - \left( -1 \right) ^nL_{m-n} \right) \end{cases}}\)

oraz:
\(\displaystyle{ \begin{cases}L_1+ …+L_n=L_{n+2} - 3 \\ L_{1}+ L_3+ … L_{2n-3}+L_{2n-1}=L_{2n} -2\\ L_2+L_4+…+L_{2n-2}+L_{2n}=L_{2n+1}-1\\L_{n-1}+L_{n+1}=5F_n\end{cases}}\)

Funkcja \(\displaystyle{ g}\) ciągu Lucasa
\(\displaystyle{ g \left( z \right) =\sum_{j=1} L_jz^j = z+ 3z^2+ 4z^3 + 7z^4 +...=\frac{2-z}{1 - z - z^2}}\)
Ukryta treść:    
Zależności między \(\displaystyle{ F_n}\) a \(\displaystyle{ L_n}\) są np. takie:
\(\displaystyle{ \begin{cases}L_n=F_{n-1} + F_{n+1} \\ F_{2n}=F_nL_n\\ F_{m+n}=\frac{1}{2} \left( F_mL_n + F_nL_m \right) \\L_{n+1}=\frac{1}{2} \left( 5F_n + L_n \right) \\L_n^2 - 5F_n^2= 4 \left( -1 \right) ^n\end{cases}}\)

Ciąg Tribonaciego
\(\displaystyle{ \begin{cases}T_1= 1 \\ T_2 = 1\\ T_3=2 \\ T_{n+3}=T_{n}+ T_{n+1} + T_{n+2}\end{cases}}\)

c.T.: \(\displaystyle{ 1, \ 1, \ 2, \ 4, \ 7, \ 13, \ 24, \ 44, \ 81, \ 149, \ ...}\)

ciąg Padovana
\(\displaystyle{ 1, \ 1, \ 1, \ 2, \ 2, \ 3, \ 4, \ 5, \ 7, \ 9, \ 12 , \ 16, \ 21, \ 28, \ 37, \ 49, \ …}\)
\(\displaystyle{ P_{n}= P_{n-2}+ P_{n-3}}\) dla \(\displaystyle{ n \geq 3}\)

W przypadku rekurencji „3 x do tyłu”:
Twierdzenie
Jeśli \(\displaystyle{ f_{n+3} = A f_{n+2} + B f_{n+1}+ C f_{n}}\) oraz \(\displaystyle{ \begin{cases}f_0=a \\ f_{1}=b\\ f_{2}=c\end{cases}}\)
to: \(\displaystyle{ f_n = p \left( \alpha^n + \beta^n + \gamma^n \right) + q \left( \alpha^{n-1} + \beta^{n-1} + \gamma^{n-1} \right) + r \left( \alpha^{n-2} + \beta^{n-2} + \gamma^{n-2} \right)}\)
gdzie \(\displaystyle{ \alpha, \beta, \gamma}\) spełniają \(\displaystyle{ x^3 = Ax^2 + Bx+C}\) zaś \(\displaystyle{ p, q}\) i \(\displaystyle{ r}\) są zależne od \(\displaystyle{ A, B, C}\) i od \(\displaystyle{ a, b, c}\).
Ukryta treść:    
Formuły inne;
Ukryta treść:    
Ostatnio zmieniony 10 lip 2015, o 08:21 przez Afish, łącznie zmieniany 2 razy.
ODPOWIEDZ