Ciąg Fibonacciego: Różnice pomiędzy wersjami

[wersja przejrzana][wersja przejrzana]
Usunięta treść Dodana treść
B11Blanco (dyskusja | edycje)
znaczenie kombinatoryczne
Linia 100:
<math>F_n \approx \frac{1}{\sqrt 5}\left(\frac{1 + \sqrt 5}{2}\right)^n</math>
 
== Znaczenia kombinatoryczne ==
* liczba ciągów o wyrazach równych 1 lub 2, które sumują się do liczby <math>n</math> jest równa <math>F_{n+1}</math>;
* liczba pokryć planszy <math>2 \times n</math> kostkami domina <math>2 \times 1</math> jest równa <math>F_{n+1}</math>;
* liczba ciągów [[Dwójkowy system liczbowy|binarnych]] bez kolejnych jedynek (równoważnie zer) jest równa <math>F_{n+2}</math>;
* liczba podzbiorów zbioru <math>\{ 1, \ldots , n \}</math> bez kolejnych liczb jest równa <math>F_{n+2}</math>;
* liczba ciągów binarnych bez nieparzystej długości ciągów jedynek jest równa <math>F_{n+1}</math>;
* liczba ciągów binarnych bez parzystej długości ciągów zer lub jedynek jest równa <math>2 F_n</math>.
 
== Własności ==
Linia 135 ⟶ 143:
 
: <math>\sum_{k=0}^{n-1} {n \choose k} F_{n-k} = F_{2n} </math><ref>{{cytuj książkę | nazwisko = Pawłowski | imię = Henryk | tytuł = Zadania z olimpiad matematycznych z całego świata. Teoria liczb, algebra i elementy analizy matematycznej | rok = 2005 | wydawca = Oficyna Wydawnicza "Tutor" | miejsce = Toruń | strona = 206-207 |isbn = 83-86007-21-4}}</ref>
 
: <math>\sum_{i=1}^{n} \sum_{j=1}^{n} {n-i \choose j} {n-j \choose i} = F_{2n+2}</math>
'''Dowód''': W zapisie <math>2n+1</math> jako sumy jedynek i dwójek jest nieparzysta liczba jedynek. Lewa strona równości stanowi zliczanie liczby zapisów <math>2n+1</math>, w którym parametry <math>i</math> i <math>j</math> odpowiadają liczbie dwójek po prawej i lewej stronie środkowej jedynki.
 
Kilka mniej znanych twierdzeń na temat ciągu Fibonacciego:
* Z wyjątkiem jednocyfrowych liczb 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 [[Potęgowanie|kwadratami]] [[liczby całkowite|liczb całkowitych]] są 1 i 144.
* Co trzecia liczba Fibonacciego jest podzielna przez 2, co czwarta – przez 3. Ogólniej: jeśli numer ''n'' dzieli się przez ''k'', to liczba ''F<sub>n</sub>'' dzieli się przez ''F<sub>k</sub>''. Dokładniej:
: Jeśli <math>n=mq</math>, to: <math>F_n = F_m \sum_{j=1}^{q} F_{m-1}^{j-1} F_{n-jm+1}</math>.
Zachodzi jeszcze silniejszy związek: [[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: <math style="white-space:nowrap;">\gcd(F_m,\,F_n) = F_{\gcd(m,\,n)}.\ </math>.
* Każda niezerowa liczba całkowita ma wielokrotność będącą liczbą Fibonacciego.
* Istnieje nieskończenie wiele liczb <math>n</math>, dla których zachodzi podzielność <math> n | F_{n} </math>. W szczególności można pokazać, że jeśli <math>m\in\mathbb{N}</math> to <math>5^m | F_{5^m} </math>.