[ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 lut 2005, o 17:31 
Gość Specjalny
Avatar użytkownika

Posty: 2973
Lokalizacja: Suchedniów/Kraków
1. Rekurencyjne określenie ciągu Fibonacciego.

F_1=1
F_2=1
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.

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

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.

F_1+F_2+...+F_n=F_{n+2}-1

F_1+F_3+...+F_{2n-1}=F_{2n}

F_2+F_4+...+F_{2n}=F_{2n+1}-1

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

F_1^2+F_2^2+F_3^2+...+F_n^2=F_n F_{n+1}

F_{n+m}=F_{n-1}F_m+F_n F_{m+1}

F_{2n}=F_{n+1}^2-F_{n-1}^2

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

F_1 F_2+F_2 F_3+...F_{2n-1}F_{2n}=F_{2n}^2

F_1 F_2 + F_2 F_3+... + F_{2n}F_{2n+1}=F_{2n+1}^2-1

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

F_1+2F_2+...+nF_n=nF_{n+2}-F_{n+3}+2

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

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

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

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

F_{3m} = F_m^{3} + F_{m+1}^{3} - F_{m-1}^{3}

F_{n}^4  = 1+ F_{n-2}F_{n-1}F_{n+1}F_{n+2}

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

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

\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
Góra
Mężczyzna Offline
PostNapisane: 29 lip 2013, o 15:58 
Użytkownik

Posty: 4216
Lokalizacja: Kraków
Cytuj:
Tomasz Rużycki napisał(a):
1. Rekurencyjne określenie ciągu Fibonacciego.

F_1=1
F_2=1
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ą.

Cytuj:
Kilka mniej znanych twierdzeń na temat ciągu Fibonacciego:
· 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 n dzieli się przez k, to liczba F_n dzieli się przez F_k. Zachodzi jeszcze: 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: gcd(F_m, F_n)= F_{gcd(m, n)}
· 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 N to 5^m | F_{5^m}

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

c. F: 1, \ 1, \ 2, \ 3, \ 5, \ 8 , \ 13, \ 21, \ 34, \ 55, \ 89, \ 144, \ 233, \  377, \ 610, \ 987, \ 1597, \ 2584, \ 4181, \ 6765 , \ 10946, \ 17711…

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

Cytuj:
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 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.
Ukryta treść:    


Zarówno wzór rekurencyjny jak i Lucasa jest więc nieefektywny. (chcąc np. obliczyć 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*:
F_n = {n - 1 \choose 0} + {n - 2 \choose 1} +…+ {n - j \choose j-1}  + {n - j-1 \choose j} gdzie j=\lfloor \frac{n-1}{2} \rfloor
tj. tzw. wzór Lucasa.
*Inną metodą może być tu użycie ciągu Lucasa (np. F_{30}=F_{15}L_{15}) itp.

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

F_{n} jest więc taką liczbą całkowitą, która jest najbliżej n tego wyrazu ciągu a_n = \frac{\phi^n}{\sqrt{5}}.
np. F_8 =21 zaś a_8 = \frac{\phi^8}{\sqrt{5}}= \frac{21\phi + 13}{\sqrt{5}} \approx 21,01
Ukryta treść:    

Można też określić F_n gdy n jest liczbą całkowitą ujemną, tj. F_{ - n} = F_n (-1)^{n+1} dla n>0 i wtedy F_{n+1} = F_{n}+ F_{n-1} dla n \in Z.

\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} dla n>1 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}}
arctg(F_{2n+1}) + arctg(F_{2n+2})= arctg(F_{2n})
F_{2n}= F_{n+1}^2 - F_{n-1}^2
F_{2n+1}=F_n^2+ F_{n+1}^2
oraz F_{n+1}^2 - F_{n-2}^2 =4F_nF_{n-1}

Cytuj:
1) kwadrat każdego wyrazu ciągu Fibonacciego różni się od iloczynu wyrazów sąsiednich o \pm 1
2) dla każdych czterech kolejnych wyrazów iloczyny wyrazów skrajnych i środkowych różnią się o \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 1

1) np. F_{13}^2 - F_{12}F_{14} = F_{13}(F_{11} + F_{12} ) - F_{12}(F_{12} + F_{13}) = - (F_{12}^2 - F_{10}F_{13}) = 1

4) np. jeśli F_1 + F_2 + F_3 = F_5 - 1 to 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.

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

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

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

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

:arrow: \sum_{j=1}^n F_j^2 = F_nF_{n+1}
Cytuj:
Kwadraty o bokach równych liczbom Fibonacciego tworzą prostokąt Fibonacciego; wpisując w nie ćwiartki okręgów otrzyma się tzw. spiralę Fibonacciego.

\sum_{j=1}^n F_j^3 = \frac{1}{10}F_{3n+2} + (-1)^{n+1}\frac{3}{5}F_{n-1}+ \frac{1}{2}

F_n^2 - F_{n-1}F_{n+1} = (-1)^{n+1} lub równoważnie tak: \frac{F_{n+1}}{F_n} - \frac{F_{n}}{F_{n-1}}= \frac{(-1)^n}{F_nF_{n+1}} tj. \lim \frac{F_{n+1}}{F_n} = \phi (oscylująco ale intensywnie; np. \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 r=1) wiąże się z tzw. zagadką brakującego kwadratu.

Formuła F_n z liczbami zespolonymi: F_n= \prod_{k=1}^{n-1} (1- 2icos(\frac{k\pi}{n}))

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

algorytm
Cytuj:
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 F_n = \begin{cases} b \ dla \ n=1 \\ a \ dla \ n= 2\\ F_{n-1} \cdot F_{n-2} \ n>2\end{cases}
tj. np. F_3=F_2F_1 =ab \ F_4=F_3F_2 =aba \ F_5= F_4F_3=abaab itd. Każde słowo F_n składa się tylko z liter a i b i jest „językową sumą” dwóch poprzednich słów.

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

tj. jeśli f_0= 0 \ f_1 = 1 oraz A = B= 1 to f_n = F_n

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


ciąg Lucasa
\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 (a=1 \ b=3 \ A=B=1).

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

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

oraz:
\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 g ciągu Lucasa
g(z) =\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 F_n a L_n są np. takie:
\begin{cases}L_n=F_{n-1} + F_{n+1} \\ F_{2n}=F_nL_n\\ F_{m+n}=\frac{1}{2}(F_mL_n + F_nL_m)\\L_{n+1}=\frac{1}{2}(5F_n + L_n)\\L_n^2 - 5F_n^2= 4(-1)^n\end{cases}

Ciąg Tribonaciego
\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.: 1, \ 1, \ 2, \ 4, \ 7, \ 13, \ 24, \ 44, \ 81, \ 149, \ ...

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

W przypadku rekurencji „3 x do tyłu”:
Twierdzenie
Jeśli f_{n+3} = A f_{n+2} + B f_{n+1}+ C f_{n} oraz \begin{cases}f_0=a \\ f_{1}=b\\ f_{2}=c\end{cases}
to: f_n = p(\alpha^n + \beta^n + \gamma^n) + q(\alpha^{n-1} + \beta^{n-1} + \gamma^{n-1})  + r(\alpha^{n-2} + \beta^{n-2} + \gamma^{n-2})
gdzie \alpha, \beta, \gamma spełniają x^3 = Ax^2 + Bx+C zaś p, q i r są zależne od A, B, C i od a, b, c.

Ukryta treść:    

Formuły inne;
Ukryta treść:    
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ciąg Fibonacciego. - zadanie 3
Witam, mam problem ze zrozumieniem. Zad. Na ile sposobów można planszę 2xn pociąć na prostokąty o wymiarach 2x1. Wiem dlaczego odpowiedź to n-1. Nie rozumiem tylko, dlaczego napisano, że w tym zadaniu zastosowanie ma ciąg Fibonacciego....
 Kvothe  10
 Ciąg Fibonacciego. - zadanie 2
Witam, Jestem po wykładzie na którym był 'omówiony' ciąg Fibonacciego. Mam takie zadania : Zadanie 1.1. Gałezie dziela sie na stare i młode. Od kazdej starej po roku oddziela sie nowa młoda gałazka, a kazda młoda gałazka robi sie stara. Prosze pokaz...
 Fengson  4
 Ciąg na dziś - ograniczenie i monotoniczność
Zadanie brzmi tak: Niech ciąg {a(n)} będzie zadany indukcyjnie: a_1=\frac{3}{2} ,a_{n+1}=\sqrt{3\cdot a_n-2} dla n\geq1 Wykazać, że jest on ograniczony z góry prze...
 Anonymous  3
 Czy ciąg an jest zbiezny jesli tak wyznacz granice
a) a_n \begin{cases} \sqrt{ 5^{n} + 6^{n}} &amp; \text{dla } n \le 12 \\ \left&#40; 1- \frac{2}{n} \right&#41; ^{ \frac{n}{2} } &amp; \text{dla } n &gt;12\end{cases} tutaj wychodza mi inne granicedla 1 czesc 4 dla dr...
 Miris  1
 Dwie funkcje i ciąg
4. Liczby x _{1}, x _{2} są pierwiastkami równania x ^{2}+x+A=0, a liczby x _{3} ,x _{4} są pierwiastkami...
 Konikov  1
 Ciag(an)
dzieki:)...
 orzi  7
 ciag do kwadratu
Można też w ten sposób \begin{cases} a_{1}+a_{2}+a_{3}=26 \\ a_{1}^{2}+a_{2}^{2}+a_{3}^{2}=364 \end{cases}\\ \begin{cases} a_{1}+a_{2}+a_{3}=26 \\ \left&#40; a_{1}+a_{2}+a_{3}\right&#41;^2-2\left&#40; a_{1}a_{2}+a_{1}a_{3}+a_{2}a_{3...
 Doonioo  3
 Ciąg geometryczny - zadanie 194
W pewnym ciągu sumę początkowych n wyrazów można obliczyć ze wzoru S_n= 5&#40;1-2^{n}&#41;. Wykaż że jest to ciąg geometryczny....
 Ciennieba  1
 ciąg arytmetyczny - zadanie 261
Sprawdź, czy ciąg a_{n}=kn+p jest arytmetyczny, jeśli jest to wylicz wyraz pierwszy i różnicę....
 ja93  1
 Uzupełnij ciąg geometryczny
Uzupelnij brakujace wielkosci , wiedzac ze ciag &#40;a_{n}&#41; jest ciagiem geometrycznym o ilorazie q a) a_1=? , q= \frac{1}{2} , [t...
 andzia8834  4
 ciag geometryczny - zadanie 10
m=6 n=4 Wyznacz liczbe k tak aby liczby m,n,k byly odpowiednio pierwszym,drugim i trzecim wyrazem ciagu geometrycznego...
 salvadorek  1
 ciąg rekurencyjne - zadanie 2
Cześć 1. Jak można sobie poradzić w wyznaczeniu granicy, jeżeli mamy ciąg zadany rekurencyjnie. 2. Kiedy jest tak, że kres górny będą granicą?...
 tukanik  3
 Ciąg arytmetyczny i geometryczny w jednym
Trzy liczby, których suma jest równa 93, tworzą ciąg geometryczny. Te same liczby stanowią pierwszy, drugi i siódmy wyraz ciągu arytmetycznego. Wyznacz te liczby.Błagam o pomoc....
 Bebe1234  3
 [Java] Ciąg Fibonacciego - zadanie 2
Dostałam za zadanie napisać w Javie program który będzie liczył sumę ciągu Fibonacciego. Siedzę nad tym już dwa dni, nie mam pojęcia jak to zrobić. Moi znajomi też nie. Jeżeli są tu jakieś mądre głowy bardzo proszę o pomoc. To moje 3 zajęcia z językó...
 Dex-terowa  9
 sprawdz czy liczby tworza ciag
mam wielka prosbe o pomoc jestem głabem matematycznym i otwarcie sie do tego przyznaje sprawdz czy liczby: a=\frac{1}{2} b=\frac{1}{3} c=\frac{1}{6} tworza c...
 karolajna121  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com