szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 lut 2005, o 16: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 14:58 
Użytkownik

Posty: 4395
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 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 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
 rosnący ciąg geometryczny - zadanie 2
Rosnący ciąg geometryczny ma parzystą liczbę wyrazów. Wszystkie wyrazy ciągu są dodatnie, a ich suma jest 5 razy większa od sumy o numerach nieparzystych. a) Wyznacz iloraz ciągu . b) Wiedząć dodatkowo, że iloczyn dwudziestu początkowych wyrazów teg...
 varianttsi  1
 Wykaz ze ciag (a_n) jest ciagiem arytmetyczny wtedy i tylko
Wykaz ze ciag (a _{n}) jest ciagiem arytmetycznym wtedy i tylko wtedy, gdy jego wykres zawiera sie w pewnej prostej y=ax+b Ja zrobilem tak: a_{n}=an+b \\ a _{n+1} =an+a+b \\ a...
 qwadrat  1
 ciąg arytmetyczny - zadanie 40
Miary kątów wielokąta tworzą ciąg arytmetyczny którego różnica równa się 4stopnie a miara największego kąta wynosi 172stopnie. ile boków ma tej wielokąt?...
 Bartosz89M  1
 ciąg arytm- def i wyznaczenie wyrazów
mam ciąg an o wyrazie ogólnym a_{n}= \frac{2n}{n+1} a) musze sprawdzić korzystając z def, czy ten ciag a_{n} jest ciągiem arytmetycznym. b) mam wyznaczyć wyraz ogólny ciągu arytmetycznego [te...
 tommassi  3
 ciag arytmetyczny i geometryczny - zadanie 17
suma trzech liczb tworzacych ciag arytmetyczny jest rowna 15. jezeli pierwsza liczbe pozostawimy bez zmian druga zwiekszymy o 4 trzecia o 20 to otrzymamy ciag geometryczny. wyznacz te liczby...
 tomi140  1
 kombinacje ciag dalszy
2.chce na polce ustawic 3powiesci historyczne,5kryminalow i 4powiesci fantastyczne.na ile sposobow moge to zrobic jesli chce zeby ksiazki jednego rodzaju staly obok siebie?...
 zosia18  12
 Znajdz x dla których podane log. tworzą ciąg arytmetyczn
Witam ! Proszę o pomoc w rozwiązaniu następującego zadania: Dla jakich x liczby: \log_227;\, \log_2x;\, \log_2\frac{1}{x} w podanej kolejności, tworzą ciąg arytmetyczny? Proszę o jakieś wskazówki, gotowe rozwiązanie - ...
 krzysiek_g  1
 Wyznacz te wartosci parametru p, dla ktorych ciag
Wyznacz te wartosci parametru p, dla ktorych ciag &#40;a_n&#41; o wyrazie ogolnym a_n=n^2+pn jest rosnący....
 orzi  2
 nierówność - ciąg sumy ułamków, który nie wiadomo jak ugryźć
Witam, \frac{1}{n+1} +\frac{1}{n+2} + \frac{1}{n+3} +...+ \frac{1}{3n+1} \ge 1 W ogóle nie wiem jak się do tego zabrać, jak w ogóle rozumieć ten ciąg? a co dopiero go dowieść?...
 matinf  3
 Wyznaczanie liczb by tworzyły ciąg arytmetyczny i geom.
Zadanie: Mając dane liczby 3 i 84, wyznacz takie liczby x, y by liczby 3, x, y tworzyły ciąg geometryczny, zaś liczby x,y,84 ciąg arytmetyczny. Zadanie 2: Kolejnymi wyrazami ciągu( a_{n})zaczynając od pierwszego są liczby: 4,11,25,53,109,221,445...
 XOla.  1
 Zależności z liczbami tworzącymi ciąg geometryczny
Witam Mam do zrobienia sporo zadań i każda pomoc z Waszej strony jest na wagę złota. Z góry bardzo dziękuję 1) Udowodnij, że jeśli a, b, c i d tworzą ciąg geometryczny, to: a) \left&#40;a^2+b^2+c^2\right&#41;\left&#40;b^2+c^2+d^2\right&...
 henzdz123  0
 ciąg rekurencyjny - zadanie 20
Proszę o pomoc w zadaniu... x_{1}=a x_{2}=b x_{n}= \frac{x_{n-1} + x_{n-2}}{2} Znaleźć \lim_{n \to \infty } x_{n} Z góry baaaardzo...
 wibajaku  2
 sprawdzic czy to ciag arytmetyczny
dany jest ciag o wyrazie ogolnym a_n = -2n + 6 wykaz ze to jest ciag arytmetyczny prosze mi powiedziec czy tutaj wystarczy jak oblicze a1 ; a2 i a3 a nastepnei podstawie do wzoru a2-a1=a3-a2? czy jest na to jakis...
 Atraktor  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com