Șirul Fibonacci

Șirul Fibonacci este un șir de numere întregi definit de o relație simplă de recurență liniară. Șirul apare în multe medii în matematică și în alte științe. În special, forma multor organisme biologice care apar în mod natural este guvernată de șirul Fibonacci și de ruda sa apropiată, raportul de aur.

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.

Fill in the Blank

O compoziție a lui n este exprimarea lui n ca o sumă de numere întregi pozitive care nu sunt neapărat distincte, unde ordinea contează. Rețineți că n = n este considerată o compoziție a lui n.

Fie C_n numărul de compoziții ale lui n cu nici o parte egală cu 1.

De exemplu, C₆ = 5 deoarece 6 = 6 = 4 +2 = 3 + 3 = 2 + 4 = 2 + 2 + 2 .

Găsiți C₁₅.

Soluție

Fill in the Blank

Un clovn poate urca o scară fie cu o treaptă, fie cu două trepte. De exemplu, el poate urca de la podea la prima treaptă și apoi la a treia sau poate urca de la podea la prima treaptă, apoi la a doua și apoi în cele din urmă la a treia.

Dacă o scară are 10 trepte, în câte moduri poate clovnul să o urce?

Clarificare:

• Când urcă de la al 9-lea pas la al 10-lea, el a urcat toată scara; adică ultimul pas este etajul al doilea.

• Ordinea în care urcă pe scară contează!

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.

Fill in the Blank

Numerele Fibonacci sunt date de

• F(0)=0

• F(1)=1

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

Deci, primele câteva sunt 0, 1, 1, 2, 3, 5, 8, 13.

Dacă generalizăm acest lucru la numerele negative, cât este F(−8)?

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. □

Fill in the Blank

Odată, un iepure și o broască țestoasă concurau într-o cursă.

Iepurele rapid ar putea sări într-o distanță tot mai mare similară cu (omițând primul termen 1), așa cum se arată mai sus: 1,2,3,5,8,13,....

Broasca țestoasă lentă s-ar putea rostogoli la o distanță tot mai mare ca o progresie aritmetică de 1 interval, așa cum se arată: 1,2,3,4,5,...

Deși aparent chiar și la primele trei etape, la scurt timp după aceea, iepurele a mers rapid înaintea adversarului său. Cu toate acestea, la un moment dat, iepurele, încrezător în victoria sa, sa oprit pentru un pui de somn. Mai târziu, broasca țestoasă și-a continuat traseul în același model și a întâlnit iepurele la aceeași distanță. Broasca țestoasă și-a continuat apoi efortul înainte de a câștiga în cele din urmă cursa.

Conform acestei povești, care este cea mai mică distanță posibilă de la început până la punctul de dormit al iepurelui?

Soluție

Fill in the Blank

Mi-am curățat recent mansarda și am găsit un set de cel puțin 14 bețe pe care un domn italian curios mi le-a vândut acum câțiva ani. Încercând din răsputeri să-mi dau seama de ce l-am cumpărat de la el, mi-am dat seama că setul are proprietatea incredibilă că nu există 3 bețe care pot forma un triunghi. În cazul în care setul are două bețe de lungime 1, care sunt cele mai mici, care este cea mai mică lungime posibilă a celui de-al 14-lea băț?

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.

Fill in the Blank

y²−xy−x²=1

Fie (x, y) soluțiile întregi nenegative la graficul hiperbolic de mai sus.

Dacă x+y = n pentru un pătrat perfect n, care este suma tuturor n-urilor posibile?

Indiciu: Singurele numere Fibonacci care sunt pătrate perfecte sunt 0, 1 și 144.

Soluție

Demonstrație

Fill in the Blank

$$\frac{1}{10}+\frac{1}{10^2}+\frac{2}{10^3}+\frac{3}{10^4}+\frac{5}{10^5}+\frac{8}{10^6}+...$$

Găsiți suma fracțiilor de mai sus, unde numitorii urmează o progresie geometrică, iar numărătorii urmează șirul Fibonacci.

Dacă răspunsul dumneavoastră este $$\frac{A}{B}$$ , unde A și B sunt numere întregi relativ prime pozitive, trimiteți răspunsul ca A + B.

Soluție

Fill in the Blank

$$\sum_{n=1}^{\infty}\frac{nF_n}{2^n}=k\sum_{n=1}^{\infty}\frac{F_n}{2^n}$$ .

Fie F_n​ al n-lea număr Fibonacci, unde F₀​=0, F₁​=1 și F_n​=F_n−1​+F_n−2​ pentru n = 2,3,4,. . . . . . .

Găsiți valoarea lui k ce satisface ecuația de mai sus.

Soluție

Fill in the Blank

0,00000000010000100002000030000500008000130002100034000550008900144...​

Cele de mai sus arată primele câteva cifre (de fapt 65) ale reprezentării zecimale a fracției $$\frac{1}{9.999.899.999}.$$ Dacă împărțim cifrele în partiții de 5, putem vedea că numerele formează un șir Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, ... Câte numere Fibonacci pozitive putem găsi înainte ca modelul să se rupă?

Notă: De exemplu, să presupunem că fracția este egală cu 0,000000000100001000020000300009... în locul celui dat în partea de sus. Apoi, ai putea găsi doar primele cinci numere Fibonacci, și anume 0, 1, 1, 2, 3. Deci, răspunsul dumneavoastră ar fi apoi că există 4 numere pozitive Fibonacci înainte de ruperea modelului.

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.

Fill in the Blank

În șirul Fibonacci, F_0​=1, F₁​=1, și pentru orice N>1, F_N​=F_N−1​+F_N−2​.

Câți dintre primii 2014 termeni Fibonacci se termină în 0?

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/