szukanie zaawansowane
 [ 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
Instytut Matematyczny, Uniwersytet Wrocławski
Mężczyzna Offline
PostNapisane: 29 lip 2013, o 15:58 
Użytkownik

Posty: 4527
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
 ciag arytmetyczny - zadanie 4
jedenesty wyraz ciągu arytmetycznego jest trzy razy większy od szóstego. Suma kwadratów trzech wyrazów tego ciągu równa się 35. Wyznacz liczbę n, dla której suma początkowych wyrazów tego ciągu jest równa 280. zupełnie nie wiem jak się za to zabrać i...
 adamlip  3
 zadanie z ciąg arytmetyczny i geometryczny
Suma trzech liczb tworzących ciąg arytmetyczny jest równa \frac{3}{4}. Jeśli drugą z tych liczb powiększymy sześć razy a ostatnią o 2\frac {3}{4}, to liczby te w podanej kolejności, utworzą ci...
 cortez901  1
 Ciąg geometryczny wykaż ciąg stały
Wykaż że jeśli w ciągu geometrycznym suma pierwszego i trzeciego wyrazu jest rowna sumie drugiego i czwartego wyrazu to jest to ciąg stały...
 gaba2512  1
 Ciąg geometryczny - zadanie 139
wzor na dowolny wyraz ciagu a _{n}=a _{1} *q ^{n-1} czyli 4000=a _{1}*q ^{4} 4=a _{1}*q obliczając mamy a _{1...
 Maul  8
 ciag arytmetyczny+ciag geometryczny
zad.1. Trzy liczby tworzą ciąg geometryczny. Jeżeli drugą z nich zwiększymy o 8, to otrzymamy ciąg arytmetyczny. Jeżeli trzeci wyraz otrzymanego ciągu arytmetycznego zwiększymy o 64, to znów otrzymamy ciąg geometryczny. Wyznacz te liczby. zad.2. trz...
 Kumek  2
 ciąg geometryczny z sinusami
ciąg geometryczny z sinusami...
 laracroft69  5
 ciąg arytmetyczny - zadanie 114
oblicz sumę dwudziestu jeden początkowych wyrazów ciągu arytmetycznego, w którym a1=42 i r=-3 Zgóry dziękuję za pomoc...
 mOnI$$  1
 Ciąg arytmetyczny - równośc i suma?
Dany jest ciąg arytmetyczny, w ktorym a_{3}=15a_{11}=-17 Dla jakich n zachodzi równość 7a_{n}=a_{1}+a_{2}+a_{3}+...+a_{n-1}? Oblicz sumę 50 początkowych ujemnych w...
 marta8  1
 Dany jest ciąg geometryczny
Dany jest ciąg geometryczny &#40;a _{n}&#41; w którym a _{1}= 7 i q=3 .Wyznacz wszystkie wyrazy tego ciągu które należą do zbioru rozwiązań nierówności \frac{x-203}{x-21} ...
 wnoros89  1
 ciąg arytmetyczny - zadanie 99
Długość boków trójkąta prostokątnego tworzą ciąg arytmetyczny. Wyaż,że różnica tego ciągu jest równa długości promienia okręgu wpisanego w ten trójkąt....
 zaczus  1
 ciąg arytmetyczny i geometryczny - zadanie 3
Bardzo proszę o pomoc w tych zadaniach: 1) Trzy liczby, które tworzą ciąg arytmetyczny, dają w sumie 39. Jeśli od pierwszej i od trzeciej liczby odjąć 3, a od drugiej 5, to otrzymane różnice utworzą ciąg geometryczny. Podaj liczby tworzące ciąg ar...
 wlazlkotek  1
 ciag geometryczny - zadanie 21
w pewnym ciągu geometrycznym a6= 5 i a8= 10. jakie mogą być wyrazy a1, a7, a10 tego ciągu.? prosiłabym jeżeli w ogóle byłaby tak możliwość, i ktoś poświeciłby chwilkę czasu nad rozwiązaniem całego zadania. bo w żaden sposób sama tego nie potrafię ...
 mademoiselle  1
 trójkąt i ciąg - zadanie 3
Wykaż, że jeśli miary kątów trójkąta są kolejnymi wyrazami ciągu geometrycznego o ilorazie 2 to między bokami a,b,c zachodzi równość \frac{1}{a} = \frac{1}{b} + \frac{1}{c}-- 5 lut 2009, o 20:14 --1/a = 1/b + 1/c...
 git66  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com