Șirul Fibonacci

Primii termeni sunt

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,.... .

Numerele Fibonacci sunt termenii unui șir de numere întregi în care fiecare termen este suma celor doi termeni anteriori cu

F1​=F2​=1,​ Fn​=Fn−1​+Fn−2​.​

Definiție

Expresie în formă închisă

Teoremă

Demonstrație

Formula (adesea numită formula lui Binet) provine dintr-un rezultat general pentru relațiile de recurență liniară, dar poate fi demonstrată direct prin inducție. Fie Gn​=(φⁿ-φⁿ)/√5​. Scopul este de a demonstra că F_n​=G_n​ prin inducție după n. Cazurile de bază sunt G₁​=G₂​=1, ceea ce este clar. Acum, să presupunem G_k​=F_k​ pentru orice k<n, unde n este cel puțin 3. Atunci

Fn​​=F_n−1​+F_n−2​=G_n−1​+G_n−2​=(φ^n-1-φ^n-1)/√5+(φ^n-2-φ^n-2)/√5=1/√​5(φⁿ⁻¹+φⁿ⁻²-φ^n-1-φ^n-2)=1/√​5​(φⁿ−φ^​n)=G_n​,​(ipoteză inductivă)

în cazul în care ultima linie vine de la faptul că φ și φ​ sunt cele două rădăcini ale ecuației x²=x+1. □​

Rețineți că pentru n≥1, termenul φ​ⁿ​/√5 este mic, cu siguranță între −0,3 și 0,3. Deci F_n​ este cel mai apropiat întreg de φⁿ/√5​.

Exemplu

Avem

​φ¹⁰​/√5=55,0036... ,φ^11​/√5=88,9977... ,

deci F₁₀​=55 și F_11​=89.

Demonstrație

​Replace this with a header

Probleme enumerative

Ca și numerele catalane, numerele Fibonacci numără mai multe tipuri de obiecte combinatoriale. Iată patru exemple.

Exemple

(1) F_n​ este numărul de compoziții ale lui n−1 constând din 1 și 2. (O compoziție a lui n−1 este o expresie a lui n−1 ca o sumă de părți, în cazul în care ordinea părților contează.) De exemplu

5=1+1+1+1+1=1+1+1+2=1+1+2+1=1+2+1+1=2+1+1+1=1+2+2=2+1+2=2+2+1,

deci F_6​=8.

(2) F_n​ este numărul de moduri de a pardosi cu dale un placaj 2×(n−1) cu 1×2 dale.

(3) F_n​ este numărul de șiruri binare de lungime n−2 fără 0 consecutiv .

(4) F_n​ este numărul de submulțimi ale lui {1,2,...,n−2} care nu conțin nicio pereche de numere consecutive.

Pentru a vedea că numerele Fibonacci numără aceste obiecte, lăsați numărul de obiecte egal cu G_n​ și arată că G_n​=G_n−1​+G_n−2​. Apoi verificați că F_1​=G₁​ și F₂​=G₂​, iar demonstrația este completă.

De exemplu, pentru a demonstra (4), începe cu G₁​=1,G₂​=1,G_3​=2,G4​=3, și apoi să presupunem S este o submulțime a lui { 1, 2, ... , n−2} fără numere consecutive în ea. Există G_n−1​ astfel de mulțimi S care nu conțin n−2. Dacă S conţine n−2, atunci nu conține n−3, deci S se obține prin luarea unei submulțimi a lui { 1, 2, ... , n−4} și înlocuirea cu n−2. Deci, există G_n−2​ astfel de mulțimi S. Acest lucru demonstrează că G_n​=G_n−1​+G_n−2​, după cum doriți.

Soluție

Soluție

Fie A (n) modalitățile prin care Clovnul poate urca n scări. Dacă decide să facă un pas pentru prima sa mutare, vor exista A(n-1) modalități de a urca restul. Dacă decide să facă doi pași pentru prima sa mutare, vor exista A(n-2) modalități de a urca restul. Astfel, A(n)=A(n-1)+A(n-2). Aceasta este formula șirului Fibonacci. Prin urmare, A(10)=F(11)=89.

Soluție

În general,

F(n)=F(n−1)+F(n−2)

astfel încât să puteți calcula înapoi prin a spune că:

F(n−2)=F(n)−F(n−1)

Acest lucru dă,

• F(−1)=1

• F(−2)=−1

• F(−3)=2

• F(−4)=−3

• F(−5)=5

Și, în general,

F_−n​=(−1)ⁿ⁺¹F_n​

Demonstrație

Iată o demonstrație rapidă prin inducție...

Luați în considerare n pozitiv.

Trivial adevărat pentru −n=0 și −n=−1. Să presupunem că este adevărat pentru F_−n+1​ și F_−n+2​, și vom arăta că este adevărat pentru F_−n​

• F_−n​=F_−n+1​−F_−n+2​ (după cum am văzut mai sus)

• F_−n​=(−1)ⁿF_n−1​−(−1)ⁿ⁺¹F_n−2​

• F_−n​=(−1)ⁿ⁺¹(F_n−1​+F_n−2​)

• F_−n​=(−1)ⁿ⁺¹Fn​

• C.C.T.D.

Deci

F(−8)=−F(8)=−21​

​

Identități care implică seria Fibonacci

Există destul de multe identități legate de diferite numere Fibonacci. De exemplu

F_n²​−F_n−1​F_n+1​=(−1)ⁿ⁺¹,

care are corolarul util că numerele fibonacci consecutive sunt relativ prime.

Demonstrație

După cum este tipic, demonstrația cea mai cu picioarele pe pământ a acestei identități este prin inducție. Este clar pentru n=2, 3, și acum să presupunem că este adevărat pentru n. Atunci

F_n+1²​−F_n​F_n+2​​=F_n+1²​−F_n​(F_n​+F_n+1​)=F_n+1​(F_n+1​−F_n​)−F_n²​=F_n+1​F_n−1​−F_n^2​=−(−1)ⁿ⁺¹=(−1)ⁿ⁺²,​

deci este adevărat pentru n+1. □

Soluție

Soluție

Deoarece primele două bețe au lungime 1, pentru a forma un triunghi este necesar ca al treilea băț să aibă o lungime l₃​<2, din cauza inegalității triunghiului. Astfel, cea mai mică valoare posibilă pentru l₃​, care nu formează un triunghi cu celelalte bețe, este 2. Continuând cu același raționament, deducem că, în cazul în care al n-lea băț are lungimea l_n​ și al (n+1)-lea băț are lungimea l_n+1​, atunci, pentru a forma un triunghi, al (n+2)-lea băț trebuie să aibă o lungime care satisface l_n+2​<l_n+1​+l_n​.

Pe măsură ce căutăm cea mai mică valoare posibilă care nu satisface inegalitatea anterioară, concluzionăm că lungimea l_n+2​ este l_n+1​+l_n​. Vedem că așa este definit șirul lui Fibonacci. Prin urmare, căutăm f₁₄​, care este 377.

Soluție

Demonstrație

Soluție

Soluție

Soluție

Proprietăți de divizibilitate

Identitatea (1) de mai sus poate fi utilizată pentru a arăta că, dacă a∣b, atunci F_a∣F_b​. De fapt, mai mult este adevărat:

cmmdc(F_a​, F_b​)=F_{cmmdc(a, b)​}.

Acest lucru rezultă din (1) și un proces similar algoritmului lui Euclid; scriem a=bq+r, 0≤r<b, atunci

cmmdc(F_a​, F_b​)​=cmmdc(F_bq+r​, F_b​)=cmmdc(F_bq​F_r+1​+F_bq−1​F_r​, F_b​)

=cmmdc(F_bq−1​F_r​, F_b​)(fiindcă F_b​∣F_bq​)

=cmmdc(F_r​, F_b​),​​(pentru că cmmdc(F_bq−1​, F_bq​)=1)​

și așa mai departe.

Exemplu

Avem cmmdc(F₁₀​,F₁₅​)=cmmdc(55, 610)=5=F_5​.

Rețineți că această discuție implică faptul că, dacă F_p​ este prim, atunci p este prim sau p=4. Inversa nu este adevărată (F₂​=1, F₁₉​=37⋅113), și, de fapt, nu se știe dacă există infinit de multe numere prime p astfel încât F_p​ este prim.

Soluție

Notați formula cmmdc(F_n​, F_x​)=F_{cmmdc(n. x)}​ pentru F_0​=1, F1​=₁, și pentru orice N>1, F_N​=F_N−1​+F_N−2. Acum, rețineți că F₁₅​ este primul Fibonacci >0 dividabil cu 10. utilizați formula cmmdc și vă permite să vedeți câteva

cmmdc(F₁₅​, F_30​)=F_{cmmdc(15,30)​}=F₁₅​=0(mod 10)

cmmdc(F₃₀​, F₄₅​)=F_{cmmdc(30, 45)}​=F₁₅​=0(mod 10)

cmmdc(F₄₅​, F_60​)=F_{cmmdc(45, 60)}​=F₁₅​=0(mod 10)

​deoarece cmmdc dintre acestea sunt 0 mod 10 aceste capete cu zero. dar orice n divizibil cu 15 obiceiul se termină cu 0. Există 134 de multipli ai lui 15 de la 1 la 2015.

Teorema lui Zeckendorf

O reprezentare Zeckendorf a unui întreg pozitiv este o expresie a întregului ca o sumă de (cel puțin unu) numere Fibonacci distincte neconsecutive. De exemplu 41=34+5+2 este o reprezentare Zeckendorf a lui 41.

Teoremă

Fiecare întreg pozitiv are exact o reprezentare Zeckendorf.

Demonstrație

Pentru a arăta mai întâi că nu pot exista mai multe reprezentări, utilizați identitățile de la punctul (3) de mai sus pentru a vedea că suma oricăror numere Fibonacci neconsecutive al căror număr este cel mai mare F_n​ nu poate fi mai mare decât F_n+1​ (rețineți că F₁​ și F₃​ sunt numere Fibonacci consecutive deoarece F₁​=F₂​). Apoi, să presupunem că există două reprezentări Zeckendorf ale unui întreg și să scădem toate numerele Fibonacci comune în cele două sume. Apoi, cele două sume rezultate sunt încă egale și constau din două mulțimi incoerente de numere Fibonacci. Să presupunem că cel mai mare număr Fibonacci din prima sumă este F_a​ iar cel mai mare număr Fibonacci din a doua sumă este F_b​; să presupunem fără pierderea generalității că a<b. Atunci, prima sumă este mai mică decât F_a+1​ dar a doua sumă este în mod clar ≥F_b​, deci nu pot fi egali.

Demonstrația implică faptul că reprezentarea Zeckendorf poate fi găsită luând întotdeauna cel mai mare număr Fibonacci mai mic decât n, scăzând-o și repetând procesul.

Această teoremă are aplicații în teoria codării.

Bibliografie

Secvența Fibonacci. Brilliant.org. 10:59, 4 iunie 2023, de la https://brilliant.org/wiki/fibonacci-series/