Numerele Lui Fibonacci

INTRODUCERE

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …Iată un șir de numere care va fi în centrul lucrării de față ,un șir de numere atât de cunoscut,șirul lui Fibonacci.

Izvorât din celebra problemă a iepurilor de casă,veche de peste 800 de ani, șirul lui Fibonacci ramâne până în prezent unul dintre cele mai atractive capitole ale matematicii elementare.

Despre Fibonacci putem spune că,pe o perioadă de aproape 2000 de ani,între Diophantus și Fermat,a fost probabil cel mai mare geniu al teoriei numerelor.

Fibonacci,pe nume Leonardo Pisano, fiul lui Guilielmo și membru al familiei Bonacci ,s-a născut în Italia dar educația și-a primit-o în Africa de Nord unde tatăl său avea un post diplomatic.Slujba tatălui său era să reprezinte negustorii din Republica Pisa care făceau comerț în Bugia,mai târziu numită Bougie și acum numită Bejaia. Bejaia este un port mediteranean în Algeria de nord-est.Orașul se află la gura râului Wadi Soummam lânga Mount Gouraya și Cape Carbon. Fibonacci a învățat matematica în Bugia și a călătorit mult cu tatăl său,realizând care sunt enormele avantaje ale sistemelor matematice folosite în țările pe care le vizitau.

Fibonacci și-a încheiat călătoriile în jurul anului 1200 și tot în acea perioada s-a întors în Pisa.Acolo a scris texte importante ce au avut rolul de a relansa tehnicile matematice antice,iar contributia sa personala a fost una semnificativa. Fibonacci a trăit în perioada în care tiparul nu exista , așa că lucrările sale erau scrise de mână și singurul fel în care puteai să obții o copie a uneia dintre acestea era să faci o copie tot de mână. Dintre cărțile lui avem încă copii ale Liber abaci (1202), Practica geometriae (1220), Flos (1225) și Liber quadratorum. Luând în considerare că relative puține copii de mână au fost făcute,suntem norocoși că avem acces la ele. Oricum, este știut că au fost și alte scrieri care ,din nefericire, s-au pierdut. Cartea sa despre aritmetica comercială Di minor guisa s-a pierdut ca și comentariul asupra Elementelor lui Euclid ce conținea tratarea numerică a numerelor iraționale.

Pe atunci imperiul Roman era condus de Frederick al II-lea. Acesta a fost încoronat rege al Germaniei în 1212 și apoi împarat roman de către Papa în Biserica Sfantul Petre din Roma în Noiembrie 1220. Frederick al II-lea a susținut Pisa în conflictele sale cu Genova pe mare și pe uscat și până în 1227 a încercat să-și consolideze puterea în Italia. Controlul de stat a fost introdus asupra comerțului și manufacturierilor și cei ce trebuiau să fie implicați în acest proces erau instruiți la Universitatea din Napoli pe care Frederick a fondat-o în acest scop în 1224.

Frederick a aflat de lucrările lui Fibonacci de la învățăceii de la curtea sa care corespondau cu Fibonacci înca de la întoarcerea acestuia în Pisa în jurul anului 1200. Printre aceștia se aflau și Michael Scotus care era astrologul curții, Theodorus Physicus filozoful curții și Dominicus Hispanus care i-a sugerat lui Frederick să-l întâlneasca pe Fibonacci .

Johannes din Palermo, alt membru al curții lui Frederik al II-lea, a prezentat câteva probleme pe care Fibonacci le studia.Trei dintre acestea au fost rezolvate de Fibonacci și soluțiile au fost date în Flos care i-a fost trimisă lui Frederick al II-lea.

Liber abaci, publicată în 1202 după ce Fibonacci se întoarce în Italia, i-a fost dedicată lui Scotus. Cartea este bazată pe aritmetica și algebra pe care Fibonacci le-a studiat în timpul călătoriilor sale.Cartea ,care a fost foarte copiată și imitată,introducea sistemul zecimal de numere hindu-arabice și folosirea numerelor arabe în Europa, dar mai conținea și studiul ecuațiilor liniare.

A doua parte a Liber abaci conține o larga colecție de probleme adresate comercianților. Acestea au legătură cu prețul mărfurilor,calcularea profitului într-o tranzacție,convertirea banilor, și probleme ce își au originea în China.

O problemă din a treia parte a Liber abaci a condus la introducerea numerelor Fibonacci și a șirului Fibonacci :

Un om a pus o pereche de iepuri într-un loc înconjurat peste tot de ziduri. Câte perechi de iepuri se pot produce din acea pereche într-un an dacă se presupune că în fiecare lună fiecare pereche dă naștere unei noi perechi care din a doua lună devine și ea productivă?

Numărul perechilor de iepuri la începutul fiecărei luni este 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Șirul rezultat este 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … (Fibonacci a omis primul termen în Liber abaci). Acest șir, în care fiecare număr este suma precedentelor două,s-a dovedit a fi foarte folositor și apare în multe domenii ale matematicii și științei. Fibonacci Quarterly este un jurnal modern dedicat studierii acestui șir și a problemelor în care acesta apare.

Multe alte probleme sunt date în partea a treia ,inclusiv acest tip:

Un paianjen face în urcarea sa pe perete, în timpul zilei, un număr de pași și înapoi parcurge un număr fixat de pași în fiecare noapte.Câte zile îi trebuie să urce până sus?

Mai sunt și probleme ce implică numere perfecte sau probleme cu sumări de serii aritmetice și geometrice.

Fibonacci tratează numere precum 10 în partea a patra ,cu aproximarea ratională și construcția geometrică.

Importanța lui Fibonacci

De la problemele comerciale ale lui Fibonacci putem invata multe despre societatea în care a trait. De exemplu,sociologii si economistii pot descoperi ca piperul era foarte intalnit pe vasele de marfa din Pisa,si ca ,colonia pisana din Constantinopl avea legaturi mai ales cu Egiptul.

Dupa moartea lui Fibonacci,influenta sa a ramas pentru multe secole si putem spune ca matematica chiar nu a cunoscut nici un progres timp de 300 de ani.

Ce am mostenit noi de la Fibonacci?Numerele hindu-arabice au fost in mod sigur importante pentru extinderea comertului. De o si mai mare imporatanta a fost impactul asupra stiintelor si a matematicii a noului sistem de numeratie pe care el l-a facut cunoscut.

In mod straniu ,Fibonacci este cel mai amintit pentru sirul ce ii poarta numele,dar care,a fost tratat de el destul de superficial.Matematicienii moderni ne asigura insa ca acest nume nu va fi usor uitat.

Numeroase lucrari scrise despre numerele lui Fibonacci, mult mai multe carti în care numele acestuia si sirul descoperit acum mai bine de 800 de ani sunt amintite, multe informatii ce pot fi gasite prin intermediul internetului, site-uri si reviste dedicate matematicianului.Cu multe dintre acestea am facut cunostinta si am incercat ca în lucrarea de fata sa adun tot ceea ce este mai important si interesant legat de sirul Fibonacci.

Am inceput cu un scurt istoric,iar în capitolele ce urmeaza voi continua cu

prezentarea sirului, a principalelor sale proprietati.Identitati extrem de interesante ,multe dintre ele foarte cunoscute, vor aparea.Nu voi uita nici de numerele lui Lucas,numere Mersenne, triunghiul lui Pascal, numarul de aur, dreptunghiuri cu sectiunea de aur, iar legaturile dintre acestea vor fi treptat dezvaluite.

In final vom vedea cateva aplicatii si vom descoperi în ce fel se regasesc aceste numere în geometrie, natura, arta.

Capitolul I

Teorema lui E. Lucas – D.H. Lehmer

1.1.Șirurile lui Lucas

Fie P,Q numere întregi ce satisfac:

D = P²- 4Q > 0 (1)

Atunci rădăcinile ecuației: X² – PX + Q = 0 sunt: (2)

deci 

Acum definim:

deci primele câteva valori sunt 

Șirurile

sunt numite șirurile lui Lucas, unde 

Pentru (P,Q) = (1,-1), Un sunt numerele lui Fibonacci și Vn numerele lui Lucas. Pentru (P,Q) = (2,-1) numerele Pell și numerele Pell-Lucas sunt obținute.

Șirul lui Lucas satisface relațiile generale de recurență următoare:

Dacă luăm n =1 atunci obținem :

Alte identități ar fi :

Avem că:

dacă

unde

Acest lucru îl folosim în demonstrația testului Lucas – Lehmer.

Înainte de a prezenta acest test (teorema Lucas –Lehmer) vom încerca să introducem numerele Mersenne.

1.2. Numere Mersenne

Un numar Mersenne este un număr de forma

unde n este întreg. Primele câteva numere Mersenne sunt 1, 3, 7, 15, 31, 63, 127, 255, … Corespunzând la 12,112,1112,11112,… în baza 2.

Numerele Mersenne sunt de asemenea numerele obținute luând x = 1 într-un polinom Fermat.

Primele câteva polinoame Fermat sunt;

Polinoamele Fermat satisfac

unde sunt numite numerele Fermat.

Pentru a întelege mai bine cum stau lucrurile cu polinoamele Fermat vom prezenta pe scurt șirul polinoamelor lui Lucas.Pentru a înțelege mai bine cine sunt polinoamele Fermat prezentăm în continuare șirul polinoamelor lui Lucas.

Un șir de polinoame Lucas este o pereche de polinoame generalizate

unde

rezolvând obtinem

Punând n= 0

rezultând

Cel mai folosit șir este pentru k = 0,obținând

Polinoamele w satisfac urmatoarea relație de recurență

Cazuri speciale ale polinoamelor W(x) și w(x) sunt date în urmatorul tabel.

Numărul cifrelor D ale unui număr Mersenne Mn este

unde pentru n foarte mare :

Numărul de cifre ale lui Mn este același cu numărul de cifre ale lui , adică 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, … .

Numărul factorilor primi ai lui Mn pentru n = 1, 2, … sunt 0, 1, 1, 2, 1, 3, 1, 3, 2, 3, 2, 5, 1, 3, 3, 4, 1, 6, … ,si primele câteva descompuneri

Pentru ca un număr Mersenne Mn să fie prim, n trebuie să fie prim.Toate numerele prime știute Mersenne Mp cu p prim sunt libere de pătrate.Se bănuieste însă că nu toate Mp sunt așa.

1.3. Numere Mersenne prime

Un prim Mersenne este un număr Mersenne, i.e. un număr de forma :

care este prim. Pentru ca Mn să fie prim,n trebuie să fie și el prim. Acest lucru este adevărat deoarece dacă n este compus, n = rs atunci poate fi scris ca , care îl are întotdeauna ca factor pe .

Primele câteva numere Mersenne prime sunt 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, … corespunzătoare indicilor n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, … .

Oricum, găsirea numerelor Mersenne prime este o mare provocare.Tabelul de mai jos ne dă indicele p al numerelor Mp cunoscute,împreuna cu numărul de cifre,anul descoperirii,și numele celui care l-a descoperit.

1.4. Teorema lui E. Lucas si D.H. Lehmer

Teoremă. Un număr Mp, p fiind un prim impar, este prim dacă și numai dacă este divizor al termenului al (p-1)-lea din șirul s1, s2,…, unde s1=4, sk = s2k-1 – 2, k=1,2,…

Demonstrație :

Fie a = 1+ , b = 1- .

Avem a + b = 2, ab = -2, a – b = 2 .

Definim șirurile un, vn (n =1,2,…) de numere naturale prin un = , vn =

Aceste formule implică că pentru orice n = 1, 2, …, avem:

un = Cn1 + Cn3 3 + Cn5 32 +…, v n = 2 1+ Cn2 3 + Cn4 32 + … .

Astfel pentru orice k, l avem :

(1) 2uk+l = ukvl + vkul

(-2)l+1 uk-l= ulvk – ukvl , pt. k>l

(3) u2k = ukvk

(4) u2k = v2k+ (-2)k+1

(5) v2k – 12 u2k = (-2)k+2

2vk+l = vkvl + 12uk . ul

Pentru un număr prim q impar notăm cu w(q) cel mai mare număr natural n astfel încât : q | un (există).

Vom demonstra acum următoarele trei leme :

Lema1 : Un număr prim impar q îl divide pe un, unde n este natural, dacă și numai dacă

w(q) | n.

Demonstratie :

Fie q un număr prim impar dat. Notăm cu S mulțimea numerelor n pentru care

q un. Din (1) si (2), dacă două numere, k și l, aparțin mulțimii S, atunci k+l este de asemenea un element al mulțimii, și, mai mult, dacă k > l atunci k – l aparține lui S. Observăm astfel că mulțimea S are urmatoarea proprietate : suma și diferența (pozitivă) a oricare două numere din S aparțin lui S. Fie d cel mai mare număr natural ce îi aparține lui S. Din prorietatea mai sus menționată a mulțimii S, deducem printr-o simplă inducție că numerele kd, k=1,2,…, sunt în mulțimea S. Pe de altă parte, presupunem că un număr n aparține lui S și că n împă numerele prime știute Mersenne Mp cu p prim sunt libere de pătrate.Se bănuieste însă că nu toate Mp sunt așa.

1.3. Numere Mersenne prime

Un prim Mersenne este un număr Mersenne, i.e. un număr de forma :

care este prim. Pentru ca Mn să fie prim,n trebuie să fie și el prim. Acest lucru este adevărat deoarece dacă n este compus, n = rs atunci poate fi scris ca , care îl are întotdeauna ca factor pe .

Primele câteva numere Mersenne prime sunt 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, … corespunzătoare indicilor n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, … .

Oricum, găsirea numerelor Mersenne prime este o mare provocare.Tabelul de mai jos ne dă indicele p al numerelor Mp cunoscute,împreuna cu numărul de cifre,anul descoperirii,și numele celui care l-a descoperit.

1.4. Teorema lui E. Lucas si D.H. Lehmer

Teoremă. Un număr Mp, p fiind un prim impar, este prim dacă și numai dacă este divizor al termenului al (p-1)-lea din șirul s1, s2,…, unde s1=4, sk = s2k-1 – 2, k=1,2,…

Demonstrație :

Fie a = 1+ , b = 1- .

Avem a + b = 2, ab = -2, a – b = 2 .

Definim șirurile un, vn (n =1,2,…) de numere naturale prin un = , vn =

Aceste formule implică că pentru orice n = 1, 2, …, avem:

un = Cn1 + Cn3 3 + Cn5 32 +…, v n = 2 1+ Cn2 3 + Cn4 32 + … .

Astfel pentru orice k, l avem :

(1) 2uk+l = ukvl + vkul

(-2)l+1 uk-l= ulvk – ukvl , pt. k>l

(3) u2k = ukvk

(4) u2k = v2k+ (-2)k+1

(5) v2k – 12 u2k = (-2)k+2

2vk+l = vkvl + 12uk . ul

Pentru un număr prim q impar notăm cu w(q) cel mai mare număr natural n astfel încât : q | un (există).

Vom demonstra acum următoarele trei leme :

Lema1 : Un număr prim impar q îl divide pe un, unde n este natural, dacă și numai dacă

w(q) | n.

Demonstratie :

Fie q un număr prim impar dat. Notăm cu S mulțimea numerelor n pentru care

q un. Din (1) si (2), dacă două numere, k și l, aparțin mulțimii S, atunci k+l este de asemenea un element al mulțimii, și, mai mult, dacă k > l atunci k – l aparține lui S. Observăm astfel că mulțimea S are urmatoarea proprietate : suma și diferența (pozitivă) a oricare două numere din S aparțin lui S. Fie d cel mai mare număr natural ce îi aparține lui S. Din prorietatea mai sus menționată a mulțimii S, deducem printr-o simplă inducție că numerele kd, k=1,2,…, sunt în mulțimea S. Pe de altă parte, presupunem că un număr n aparține lui S și că n împărțit la d dă restul r. Atunci n = td + r, unde t *+ și r < d.

Cazul t = 0 este imposibil, atât timp cât r, care e mai mic decât d, nu poate fi egal cu n și astfel nu poate aparține mulțimii S din cauza definiției lui d. În consecință, t este un număr natural și astfel td S, de unde, din prorietatea lui S, numărul r = n-td, ca diferentă a doua numere din mulțimea S, cu n > td, trebuie să aparțină lui S ; acest lucru contrazice definiția lui d. De aici tragem concluzia că r = 0, ceea ce înseamnă că mulțimea S este doar mulțimea multiplilor pozitivi ai unui număr ce îi aparține. De aceea dacă un număr n aparține lui S, atunci w(q) | n și reciproc și demonstratia se încheie.

Lema 2 : Dacă q este un nr. prim > 3 atunci :

(7) q / uq – 3(q-1)/2

și

q / vq – 2

Demonstrație :

Pentru a demonstra (7) scriem :

uq = [( )q – ( )q] = q .3k

k+1

În suma din partea dreaptă coeficientii binomiali sunt toți divizibili cu numărul prim q, cu excepția ultimului, care este egal cu 1; de aici formula (7) se obține.

Pentru a demonstra (8) scriem :

vq =( )q +( )q = 2. . 3k

2k

În această sumă coeficienții binomiali, cu excepția celui dinâti, sunt divizibili prin q ; de aici se obține formula (8).

Lema 3 : Dacă pentru un număr prim q > 0 numărul w(q) există, atunci w(q) < q+1

Demonstrație : u1 = 1, v1 = 2

Din (1) si (2), pentru k=q si l=1, găsim 2uq+1= 2uq+vq si

-4uq-1 = 2 uq-vq, de unde -8uq+1. uq-1= 4u2q-v2q.

Dar, conform lemei 2, avem ca q ׀ u2q-3q-1 si

q ׀ v2q-4.

Dar q este prim > 3 și din Teorema lui Fermat obținem q ׀ 3q-1-1.

Avem deci că : q ׀ u2q-1 și rezultă că q ׀4u2q-v2q.

q ׀ 8uq+1, care pentru q > 3, implică q ׀ uq+1 sau q ׀ uq-1.

În primul caz, în virtutea lemei 1 obținem w(q) ≤ q+1 ; în cazul al doilea avem

w(q) ≤ q-1. Deci, în orice caz, w(q) ≤ q+1, care arată validitatea lemei 3.

Ne întoarcem acum la demonstrație suficienței condiției din teoremă. Să

presupunem că p este un prim impar și Mp│Sp-1. Atunci : Mp│ . Sp-1 (9)

Avem 2s1 = v2. Pentru un număr natural n presupunem că . Sn = , acest lucru fiind adevărat pentru n =1. Având sn+1 = s2n-2 rezultă că

. Sn+1 = . Sn 2 – = – , dar conform relației (4),

pentru k = 2n, avem : – . Deci . Sn+1 = . Formula .Sn = este deci dovedită prin inducție. Așa că, pentru n = p-1 avem :

(10) . Sp-1 = .

Folosind (10), obținem in (9) : (11) Mp │ ,

Și folosind (3), cu k = 2p-1 Mp │

Acum să-l considerăm pe q un prim arbitrar, divizor al lui Mp. Datorită faptului că p este prim numărul Mp =2p-1 nu este divizibil prin 3, avem q >3.Relația q│Mp și formula (12) conduc la q│ și prin urmare, din lema (1), avem w(q) │2p. Pe

de altă parte, w(q) nu divide 2p-1 pentru că, dacă ar fi așa, am avea, din lema (1),

q│ , pe când, din (5) cu k = 2p-1, q ar fi un divizor al unei puteri a lui 2 ceea ce

este imposibil odată ce q este prim > 3. Atunci w(q) = 2p. În virtutea lemei 3, avem că

2p≤ q+1, deci Mp ≤ q, ceea ce înseamnă că Mp este prim.

Suficiența condiției din teoremă este deci dovedită. Pentru a demonstra și necesitatea arătam urmatoarele:

Lema 4. Daca p este un număr prim de forma 12k+7, atunci p│3(p-1)/2 +1.

Demonstrație: Fie p un număr prim de forma 12k+7, unde k este un număr

întreg ≥1.Atunci p >3 și, din proprietățile simbolului lui Legendre, găsim că .

Din proprietățile simbolului lui Legendre avem că , de unde .

În același timp 3(p-1)/2 ≡ -1 (mod p), de unde p│3(p-1)/2, ceea ce căutam.

Ne întoarcem acum la demonstrația necesității condiției de necesitate din teoremă.

Presupunem că p este prim > 2 si că numărul q = Mp este de asemenea prim p > 2 8│2p = q+1. Atunci q= 8t+7, t întreg ≥ 0.

Avem că q-1= 2p-2 = 2(2p-1-1).

p-1 este par, i.e p-1 = 2s, unde s numar natural 2p-1-1 = (3+1)S – 1 = 3u, unde u este întreg. Atunci 3│2p-1-1│q-1 = 8t+6, de aici 3│t, i.e. t = 3k, unde k este întreg. De aici

q = 8t+7 = 24k+7. Din (4), pentru k =2p-1 se obtine:

(13) = – 4 – 1

Dar q = 24k+7 = 8.3k+7 q│M(q-1)/2, i.e. q│M2p-1-1 = – 1, de unde din (13) rezultă:

(14) q│ – + 4.

Dar, facând k = q în (6) și l = 1, si din q + 1 = 2p , avem

= vq.v1 + 12uq. u1 = 2vq + 12uq

Prin urmare,

= v2 +6uq = (vq – 2) + 6 (uq +1) – 4

Datorită faptului că q = 24k +7 putem aplica lema 4 lui q; deci q│3(q-1)/2 + 1, și atunci, din (7), q│uq+1 și, din (8), q│vq-2. Deci, din formula (15), q│ + 4, de unde, folosind (14),

q│ . Acest lucru, din (10), pentru q = Mp impar, arată că Mp│Sp-1, și aceasta

completează demonstrația condiției de necesitate.

Teorema este demonstrata.

Este usor de arătat că teorema este echivalentă cu următoarea teoremă a lui Lucas:

Teoremă: Un număr Mp, unde p este prim impar, este prim dacă și numai dacă Mp

este divizor al termenului al (p-1)-lea din șirul t1, t2, …, unde

tk+1 = 2t2k – 1, pentru k =1, 2, …

Capitolul II. Numerele Fibonacci și unele

proprietăți ale acestora

2.1.Cele mai simple proprietăți ale

numerelor lui Fibonacci

Avem deci șirul lui Fibonacci (Fn)n cu F1 = F2 = 1, și relația de recurență

Fn+1 = Fn + Fn-1

1.Să calculăm mai întâi suma primelor n numere din șirul lui Fibonacci. Vom demonstra că:

F1+ F2+…+Fn = Fn+2 –1. (1)

Într-adevăr, avem:

F1= F 3 -F 2,

F 2= F 4-F 3,

F 3= F 5-F 4,

……….

F n-1= F n+1-F n,

F n= F n+2- F n+1.

Adunând membru cu membru toate aceste egalități, obținem:

F 1+ F 2+ F 3+…+ F n = F n+2- F 2

și nu rămâne decât să ne amintim că F 2 = 1.

2. Suma termenilor de rang impar din șirul lui Fibonacci este:

F 1+ F 3+ F 5+…+ F 2n-1= F2n (2)

Pentru a demonstra această egalitate, vom scrie :

F 1= F 2,

F 3 = F 4- F 2,

F 5 = F 6- F 4,

………

F 2n-1= F 2n- F 2n- 2

Adunând membru cu membru aceste egalități, obținem tocmai ceea ce trebuie demonstrat.

3. Suma termenilor de rang par din șirul lui Fibonacci este :

F 2+ F 4+…+ F 2n = F 2n+1-1. (3)

În virtutea celor stabilite la punctul 1, avem :

F 1+ F 2+ F 3+…+ F 2n = F 2n+2 -1 ;

Scăzând membru cu membru egalitatea (2) din această egalitate obținem

F 2+ F 4+…+ F 2n = F 2n+2-1- F 2n – F 2n+1-1,

tocmai ceea ce trebuia demonstrat.

Scăzând mai departe membru cu membru egalitatea (3) din (2), obținem

F 1- F 2+ F 3- F 4+…+ F 2n-1- F 2n = – F 2n-1+1. (4)

Adăugând F 2n+1 la ambii membri ai egalității (4), avem :

F 1- F 2+ F 3- F 4+…- F 2n + F 2n+1 = F 2n+1 (5)

Comparând relațiile (4) și (5), obținem o expresie pentru suma numerelor lui Fibonacci, cu semne alternate :

F 1- F 2+ F 3- F 4+…+(-1)n+1 F n = (-1)n+1 F n-1+1. (6)

4. Am dedus formulele (1) și (2) prin însumarea membru cu membru a unei întregi serii de egalități evidente. Un alt exemplu de aplicare a acestei metode este deducerea formulei pentru suma pătratelor primelor n numere din șirul lui Fibonacci :

F 12+ F 22+…+ F fn2 = F 1 F n+1. (7)

Observăm că

F k F k+1- F k-1 F k= F k(F k+1- F k-1) = F k2.

Adunând membru cu membru egalitățile :

F k2= F 1 F 2,

F k2= F 1 F 2- F 1 F 2,

F k2= F 3 F 4- F 2 F 3,

………….

F k2= F n F n+1- F n-1 F n.

obținem relația (7).

5. Multe relații dintre numerele lui Fibonacci, pot fi demonstrate ușor prin metoda inducției complete.

Vom demonstra prin metoda inducției urmatoarea formulă importantă :

F n+m= F n-1 F m+ F n F m+1. (8)

Vom demonstra aceasta formulă, făcând inducția în raport cu m. Pentru m=1, această formulă devine

F n+1 = F n-1 F 1+ F n F 2= F n-1+ F n,

ceea ce este evident. Pentru m=2 formula (8) este de asemenea adevărată, pentru că
F n+2= F n-1 F 2+ F n F 3 = F n-1+2 F n = F n-1+ F n+ F n = F n-1+ F n.

Am demonstrat astfel baza inducției. Vom demonstra trecerea inductivă în felul următor : presupunând că formula (8) este adevărată pentru m=k și pentru m=k+1, vom demonstra că ea este adevarată și pentru m= k+2.

Considerăm deci

F n+k= F n-1 F k+ F n F k+1

și

F n+k+1= F n-1 F k+1+ F n F k+2.

Adunând membru cu membru ultimele două egalități, obținem :

F n+k+1= F n-1 F k+2+ F n F k+3,

tocmai ceea ce trebuia demonstrat.

Punând în formula (8) m = n, obținem

F 2n= F n-1 F n+ F n F n+1,

sau

F 2n= F n (F n-1+ F n+1), (9)

Din această egalitate se vede că F 2n este divizibil cu F n. In paragraful următor vom demonstra o afirmație mult mai generală

Deoarece

F n = F n+1- F n-1,

formula (9) poate fi trancrisă astfel :

F 2n= (F n+1- F n-1) (F n+1- F n-1),

sau

F 2n= F 2n+1- F 2n-1

adică, diferența pătratelor a două numere din șirul lui Fibonacci al căror rang diferă prin 2, este tot un număr din șirul lui Fibonacci.

În mod analog (punând m= 2n) putem arăta că

F 3n=( F n+1- F n-1) (F n+1- F n-1),

6. Acum să stabilim relația :

F 2n+1 = F n F n+2+(-1)n. (10)

Să aplicăm inducția . Pentru n = 1, relația (10) capătă forma :

F 22 = F 1 F3-1,

ceea ce este evident.

Presupunem acum că relația (10) este adevărată pentru un n oarecare. Adăugând în ambii membrii ai relației (10) produsul F n+1 Fn+2, obținem

F 2n+1+ F n+1 F n+2 = F n F n+2+ F n+1 F n+2+(-1)n,

sau

F n+1(F n+1+ F n+2) = F n+2(F n+ F n+1)+(-1)n,

Deci

F n+1 F n+3 = F 2n+1+(-1)n,

prin urmare

F 2n+2 = F n+1 Fn+3 +(-1)n+1,

Am fundamentat astfel trecerea inductivă, și formula (12) este demonstrată pentru orice n.

7. La fel cum am demonstrat proprietățile anterioare ale numerelor lui Fibonacci, pot fi stabilite și următoarele proprietăți ale acestor numere :

F 1 F 2+ F 1 F 2+ F 1 F 2+ … + F 2n-1 F 2n = F 22n,

F 1 F 2+ F 2 F 3+ F 3 F 4+ … + F 2n F 2n+1 = F 22n+1-1,

n F 1+(n-1) F 2+(n-2) F 3+ … +2 F n-1+ F n = F n+4 – (n+3).

8. Vom face acum o scurtă prezentare a triunghiului lui Pascal.

Triunghiul lui Pascal este un triunghi de numere aranjate pe linii astfel încât :

unde este coeficientul binomial.Triunghiul a fost studiat de B.Pascal,deși el fusese descris cu multe secole în urmă de matematicianul chinez Yanghui (cu 500 de ani mai devreme,de fapt) și de astronomul-poet Omar Khayyám.El este cunoscut în China sub denumirea de triunghiul lui Yanghui triangle. Începand cu n=0, triunghiul este:

Formula lui Pascal arată că fiecare linie este obținută adunând elementele de pe linia de deasupra:

Primul numar dupa 1 in fiecare rând le divide pe toate celelalte dacă acesta este prim.

Dacă adunăm numerele de pe diagonale,ca în figura de mai sus,obținem șirul lui Fibonacci:

și,în general,

Există o legătură între numerele lui Fibonacci și alte numere tot atât de importante, cum sunt coeficienții binomiali.

Asezăm coeficienții binomiali în triunghiul lui Pascal :

C00

C01 C11

C02 C12 C22

C03 C13 C23 C33

. . . . . . . . .

Adică

1

1 1

1 2 1

1 3 3 1

1 4 0 4 1

1 5 10 10 5 1

1 0 15 20 15 0 1

. . . . . . . . .

Liniile trasate între numerele acestui triunghi, care formeaza un unghi de 45º cu rândurile numerice, poartă denumirea de diagonalele ascendente ale triunghiului lui Pascal. De exemplu, liniile care unesc numerele 1, 4, 3, sau 1, 5, 6, 1 vor fi diagonale ascendente.

Vom arăta acum că suma numerelor aflate pe o diagonală ascendentă oarecare este un numar al lui Fibonacci.

In adevăr, prima diagonală ascendentă a triunghiului lui Pascal este1. Și a doua diagonală este 1. Pentru a demonstra propozitia care ne intereseaza, este suficiemt sa aratam ca suma numerelor care alcatuesc diagonalele a (n-2) si a (n-1)-a din triunghiul lui Pascal este egala cu suma numerelor de pe diagonala a n-a.

Pe diagonala a (n-2)-a sunt asezate numerele

C0n-3, C1n-4, C2n-5, …,

Iar pe a (n-1)-a, numerele

C0n-2, C1n-3, C2n-4, …,

Putem scrie suma tuturor acestor numere astfel :

C0n-2+ (C0n-3+ C1n-3)+(C1n-4+ C2n-4)+ (11)

Dar, pentru coeficientii binomiali, avem

C0n-2 = C0n-1= 1

si

Cik+ Ci+1k = =

= ∙

∙ = = Ci+1k+1.

Expresia (11) este deci egala cu

C0n-1+ C1n-2+ C2n-3+…,

adica, cu suma numerelor care se afla pe diagonala a n-a a triunghiului .

Din cele demonstrate si in baza formulei (1) obtinem imediat ca suma tuturor coeficientilor binomiali situati mai sus de diagonala a n-a ascendenta ddin triunghiului lui Pascal (inclusiv aceasta diagonala) este egala cu un+2-1.

Folosind formulele (2), (3), (4) si altele similare, vom putea obtine cu usurinta indentitatile care indica relatia dintre numerele lui Fibonacci si coeficientii binomiali.

2.2.Proprietățile numerelor lui Fibonacci ,din punct de vedere

al teoriei numerelor

Înainte de a continua studiul numerelor lui Fibonacci, aminti cateva dintre

cele mai simple cunostințe de teoria numerelor.

1. Vom da mai intai procedeul gasirii celui mai mare divizor comun al numerelor a si b.

Impartim a prin b cu rest. Presupunem ca rezultatul acestei impartiri este egal cu qo, iar restul, r1. Este evident ca a = bqo+ r1 si 0≤ r1<b. Observam ca pentru a<b, avem qo=0.

Impartim apoi pe b prin r1 si notam catul prin q1, iar restul cu r2. Evident, b= r1q1+

r2 si 0≤ r2< r1. Deoarece r1<b, atunci q1≠ 0. Impartind apoi r1 prin r2, gasim q2≠ 0 si r3 astfel, incat r1= q2r2+ r3 si 0≤ r3< r2.

Procedam in felul acesta pana cand acest process nu semai poate continua. Mai devreme sau mai tarziu procesul nostru trebuie sa se opreasca, deoarece toate numerele intregi r1, r2, r3,… sunt diferite intre ele, fiecare fiind mai mic decat b. Prin urmare, numarul lor nu este mai mare decat b si procesul de fectuare a impartirii trebuie sa se termine cel mai tarziu la etapa de rang b. Efectuarea impartirii poate fi intrerupta numai in cazul cand restul impartirii este egal cu zero, adica impartirea se face fara rest.

Procedeul descries mai sus poarta denumirea de algoritmul lui Euclid. Aplicand algoritmul lui Euclid numerelor a si b obtinem urmatorul sir de egalitati:

a = bqo + r1,

b = r1q1 + r2,

r1 = r2q2 + r3,

………….

rn-2 = rn-1qn-1 + rn, (1)

rn-1 = rnqn,

Sa examinam ultimul rest rn care este diferit de zero. Evident ca rn-1 este divizibil cu rn. Sa

Consideram acum penultima egalitate din relatiile (1). In membrul din dreapta al acestei egalitati, termini sunt divizibili cu rn si prin urmare si rn-2 este divizibil cu rn. In mod analog, ne convingem in mod succesiv (inductie) ca numerele rn-3, rn-4,… sunt divizibile cu rn. Asa dar, rn este divizorul comun al lui a si b. Vom arata ca rn este cel mai mare divizor comun a lui a si b. Pentru aceasta este sufficient sa aratam ca orice divizor comun a lui a si b va fi si un divizor a lui rn.

Fie d un divizor comun oarecare a lui a si b. Din prima egalitate (1) observam ca r1 trebuie sa se imparta la d. Insa, in baza celei de a doua egalitati (1), r2 se imparte deasemenea la d. In mod analog (inductie) dovedim ca r3 se imparte la d,… la fel rn-1 si in sfarsit rn.

Am demonstrate astfel ca algoritmul lui Euclid, aplicat numerelor naturale a si b, conduce in adevar la gasirea celui mai mare divizor comun al acestor numere. Vom nota cel mai mare divizor comun al numerelor a si b prin (a,b).

De exemplu, sa gasim (F20, F 15)= (6765,610):

6 765 = 610∙ 11+55,

610 = 55∙ 11+ 5,

55 = 5∙11.

Deci (F 20, F 15) = 5 = F 5. Faptul ca cel mai mare divizor comun a doua numere din sirul lui Fibonacci este tot un numar al lui Fibonacci, nu este intamplator. Vom demonstra ulterior ca acesta se intampla intotdeauna.

Sa stabilim cateva proprietati simple ale celui mai mare divizor comun a doua numere.

2. (a,bc) este divizibil prin (a,b). In adeavr, b si deci bc se imparte la (a,b); a este evident divizibil prin (a,b). Deci, potrivit punctului 1, si (a,bc) este divizibil prin (a,b).

3. (ac, bc) = (a, b) c.

4. Daca (a,c) =1, atunci (a,bc) = (a,b). In adevar, (a,bc) este-in virtutea

punctului 3 – un divizor al numerelor (ab, bc). Insa, tinand seama de punctual 4

(ab, bc) = (a, c) b =1.b=b.

Asa dar, b este divizibil prin (a, bc). Pe de alta parte, (a, bc) este un divizor a lui a. Prin urmare (a, bc)- tinand seama de punctual 1- este divizibil si cu (a,b). Deoarece insa, potrivit punctului 3, si (a,b) imparte pe (a, bc), rezulta ca (a, b)= (a, bc).

5. a se imparte la b daca (a, b) este egal cu b si numai in acest caz. Aceasta este evident.

6. Daca c se imparte la b, atunci (a, b) = (a+c, b).

Sa examinam acum unele proprietati ale numerelor lui Fibonacci, care se refera la divizibilitatea lor.

7. Teorema. Daca n se imparte la m,atuncisi Fn se imparte la Fm.

Demonstratie:

Presupunem ca n se imparte la m, adica n = mm1. Vom demonstra prin inductie.

Pentru m1 = 1, avem n=m, astfel incat in acest caz este evident ca F n este divizibil cu F m si consideram F m(m1+1) insa, F m(m1+1) = F mm1+m si in virtutea relatiei (10), avem

F m(m1+1) = F mm1-1+ F mm1 F m+1,

Este evident ca primul termen al membrului din dreapta al egalitatii se imparte prin Fm.

Al doilea termen este un multiplu de Fmm1, adica, potrivit ipotezei noasre, se imparte deasemenea prin Fm. Deci, si suma lor, adica Fm(m1+1) se imparte prin Fm. In acest fel teorema este demonstrata.

8.Problema privitoare la natura aritmetica a numerelor lui Fibonacci prezinta un mare interes; este vorba de divizorii lor. Vom arata ca daca n este un numar neprim si diferit de 4, Fn este deasemenea un numar neprim.

In adevar, cand n indeplineste aceste conditii, putem scrie n = n1n2 , unde

1< n1<n; 1< n2<n si, sau n1>2, sau n2>2. Presupunem-pentru a fixa ideile- ca n1>2. Tinand seama numai de teorema demonstrata mai sus, Fn se imparte prin Fn1, si

1< Fn1<Fn; aceasta inseamna ca Fn este un numar neprim.

9. Teorema. Numerele vecine din sirul lui Fibonacci sunt prime intre ele

Demonstratie. Presupunem, contrar afirmatiei teoremei, ca Fn si Fn+1 au un anumit divizor comun, d > 1.

Atunci si diferenta lor, Fn+1- Fn va fi divizibila cu d. Deoarece Fn+1- Fn = Fn-1, atunci si Fn-1 este divizibil cu d. In mod analog (inductie) aratam ca si Fn-2, Fn-3,… sunt divizibili cu d, si in sfarsit si F1 este divizibil cu d. Dar F1 =1, deci nu se poate divide la d > 1. Contradictia la care s-a ajuns demonstreaza teorema.

10. Teorema. Intre numerele lui Fiboncci are loc egalitate : (Fm, Fn) = F (m,n).

Demonstratie. Presupunem, pentru a fixa ideile, ca m > n. Aplicam algoritmul lui Euclid numerelor m si n:

m = nq0 + r1, unde 0 ≤ r1 ≤ n;

n = r1q1 + r2, unde 0 ≤ r2 ≤ r1;

r1= r2q2 + r3, unde 0 ≤ r3 ≤ r2;

. . . . . . . . . . .

rt-2 = rt-1 qt-1 + r1, unde 0≤ rt ≤ rt-1;

rt-1 = rt qt.

Dupa cum stim, rt este cel mai mare divizor comun al lui m si n.

Prin urmare, m = nq0 + r1, deci

(Fm, Fn) = (Fnq0+ r1, Fn),

sau

(Fm, Fn) = (Fnq0-1 Fr1+ Fnq0 Fr1+1, Fn),

sau in virtutea punctelor 8 si 7,

(Fm, Fn) = (Fnq0-1Fr1, Fn),

Adica, tinand seama de punctele 10 si 5

(Fm, Fn) = (Fr1, Fn).

Se arata in mod analog ca

(Fr1, Fn) = (Fr1, Fr2),

(Fr2, Fr1) = (Fr3, Fr2),

. . . . . . . .

(Frt-1, Frt-2) = (Frt, Frt-1).

Comparand succesiv toate aceste egalitati, obtinem

(Fm, Fn) = (Frt, Frt-1),

si deoarece rt-1 este divizibil cu rt, deci si Frt-1 se imparte la Frt, rezulta ca (Frt, Frt-1)- Frt. Observand, in sfarsit , ca rt = (m, n), obtinem ceeace se cerea.

Din relatia demonstarta rezulta, in particular, o teorema reciproca teoremei de la punctul 8: daca Fn se imparte prin Fm , atunci n se imparte prin m. In adevar daca Fn se imparte la Fm , atunci potrivit punctului 6

(Fn, Fm) = Fm .

Dar stim ca

(Fn, Fm) = F (n,m)

Comparand relatiile de mai sus obtinem:

Fm = F (n,m) ,

adica m =(n, m), ceeace inseamna ca n se imparte la m.

11. Reunind teorema de la punctul 8 si corolarul teoremei de la punctul 11, avem : un se imparte la um atunci, si numai atunci, cand n se imparte la m.

Cu urmare a acestui fapt putem reduce divizibilitatae numerelor lui Fibonacci la divizibilitatea rangului lor.

Sa cautam, de exemplu, cateva “criterii de divizibilitate” pentru numerele lui Fibonacci. Vom intelege prin criteriu de divizibilitate criteriul, potrivit caruia se poate determina daca un numar oarecare al lui Fibonacci se imparte sau nu la un anumit numar dat.

Un numar din sirul lui Fibonacci este divizibil cu 3 atunci, si numai atunci, cand rangul sau este divizibil cu 4.

Un numar din sirul lui Fibonacci este divizibil cu 4 atunci, si numai atunci, cand rangul sau este divizibil cu 6.

Un numar din sirul lui Fibonacci este divizibil cu 5 atunci, si numai atunci, cand rangul sau este divizibil cu 5.

Un numar din sirul lui Fibonacci este divizibil cu 7 atunci, si numai atunci, cand rangul sau este divizibil cu 8.

Cititorul poate demonstra usor aceste criterii de divizibilitate cu ajutorul afirmatiei mentionate la inceputul acestui punct si analizand respectiv al treila, al patrulea, al saselea, al cincelea, al optulea, etc. termen din sirul lui Fibonacci.

Totodata, cititorul va putea demonstra ca nu exista numere in sirul lui Fibonacci care , prin impartirea prin 8, sa dea restul 4, si ca nu exista numere in sirul lui Fibonacci, divizibile cu 17.

12. sa consideram acum un numar intreg oarecare m. Daca exista cel putin un numar un din sirul lui Fibonacci, care sa se imparta la m, atunci pot fi gasite oricate numere din sirul lui Fibonacci care sa se imparta la m. Vor fi de exemplu, numerele u2n, F3n, F4n, …

Este deaceea, interesant sa constatam daca pentru un numar dat m, exista un numar din sirul lui Fibonacci, care sa se imparta prin el. Se arata ca aceasta este posibil.

Sa notam prin k restul impartirii lui k prin m. Vom scrie sirul de perechi al acestei categorii de resturi:

< F1, F2>, < F2, F3>, < F3, F4>,…, < Fn, Fn+1>,…, (2)

Daca perechile < a1, b1> si < a2, b2> sunt considerate egale cand a1= b1 si a2= b2,

Atunci numarul tuturor perechilor de resturi diferite intre ele, obtinute prin impartirea cu m, este egal cu m2. Deoarece, daca sirul (2) consideram primi m2+1 termeni, atunci printre acestia exista neaparat termeni egali intre ei.

Presupunem ca < Fk, Fk+1> este prima pereche care se repeta in sirul (2). Vom arata ca acesta este perechea <1,1>. In adevar, presupunem dimpotriva, ca prima pereche care se repeta este o perechea < Fk, Fk+1> unde k > 1. Găsim in sirul (2) o pereche

< Fl, Fl+1> (l>k) egala cu perechea < Fk, Fk+1>. Deoarece Fl-1= Fl+1- Fl si Fk-1= Fk+1- Fk, iar

Fl+1= Fk+1 si Fl = Fk, resturile obtinute din impartirea lui Fl-1 si Fk-1 prin m sunt egale, adica: Fl-1= Fk-1. Insa, de aici rezulta ca si < Fk-1, Fk> o intalnim in sirul (2) inainte de

< Fk, Fk+1> si deaceea < Fk, Fk+1> nu este prima pereche care se repeta, ceeace contrazice ipoteza noastra. Deci, ipoteza k>1 nu este justa si deci rezulta k=1.

Asa dar, <1,1> este prima pereche din sirul (2), care se repeta. Presupunem ca ea se repeta ocupand rangul t (conform celor stabilite mai sus, putem considera ca

1< t <m2+1), adica < Ft, Ft+1>=<1,1>. Aceasta inseamna ca si Ft si Ft+1 dau restul 1 prin impartirea la m. Prin urmare, diferenta lor se imparte prin m fara rest. Insa

Ft+1- Ft = Ft-1,

astfel incat si termenul de rang (t-1) din sirul lui Fibonacci se imparte prin m.

In modul acesta am demonstrat urmatoarea teorema:

Teorema. Oricare ar fi numarul intreg m, printre primele m2 din sirul lui Fibonacci se gaseste cel putin unul care se imparte prin m.

Remarcam ca teorema demonstrata mai sus nu indica in niciun fel care anume numar din sirul lui Fibonacci se imparte prin m. Ea afirma numai ca primul numar din sirul lui Fibonacci care se imparte prin m nu este extrem de mare.

13. Daca m, q * ,atunci : (Fmq-1 , Fm ) = 1.

Demonstratie : Fie d = (Fmq-1 , Fm ). Deoarece d Fm ,iar Fm Fmq (pentru ca m mq) rezulta ca d Fmq-1 rezulta ca d (Fmq – Fmq-1 ) adica d Fmq-2. Deoarece d Fmq-1 si d Fmq-2 rezulta ca d (Fmq-1 – Fmq-2 ) adica d Fmq-3.

Continuand rationamentul din aproape,vom ajunge în final la concluzia d F2 si cum

F2 = 1, rezulta ca d = 1.

14. Daca m, n *, n ≥ m, sunt legate prin relatia n = mq + r, undeq, r * atunci avem egalitatea : (Fn , Fm ) = (Fm , Fr ).

Demonstratie : Avem :

(Fn , Fm ) = (Fmq+r , Fm ) = (Fmq-1 Fr + Fmq Fr+1 , Fm ).

Rezulta ca (Fmq-1 Fr + Fmq Fr+1 , Fm ) = (Fmq-1 Fr , Fm ).Conform lemei anterioare avem

(Fmq-1 , Fm ) = 1 si rezulta ca (Fmq-1 Fr , Fm ) = (Fr , Fm ).

Comparand egalitatile obtinute, rezulta ca (Fn , Fm) = (Fm , Fr) q.e.d.

2.3.Câteva identități cunoscute. Formula lui Binet

Identitatea lui d’Ocagne

unde Fn este un numar Fibonacci.

Identitatea lui Cassini

Pentru Fn al n-lea numar Fibonacci,

Această identitate a fost descoperită și de Simson și este un caz special al identității lui Catalan cu r = 1.

Identitatea lui Catalan

unde Fn este un numar Fibonacci.

Identitatea lui Gelin-Cesàro

Are loc:

unde Fn este un numar Fibonacci.

Reprezentarea Zeckendorf

Un număr scris ca sumă de numere Fibonacci neconsecutive ,

unde εk sunt 0 sau 1 și

Orice număr întreg pozitiv poate fi scris sub această formă în mod unic.

Teorema Zeckendorf

Șirul este complet,unde Fn este un numar Fibonacci.

Definiție:Un șir de numere V = {vn} este complet dacă fiecare întreg pozitiv n este suma unui subșir al lui V,i.e. există ai = 0 sau 1 astfel încât

Numerele lui Fibonacci sunt complete.De fapt, scotand din sir un numar obtinem tot un sir complet,dar daca scoatem doua nu se mai intampla acelasi lucru.(Honsberger 1985, pp. 123 and 126).Sirul numerelor prime cu elementul {1} adaugat,

este complet,chiar si atunci cand orice numere prime fiecare >7 sunt scoase,atat timp cat termenii scosi nu include doua prime consecutive (Honsberger 1985, pp. 127-128). Aceasta este o consecinta a Postulatului lui Bertrand :

Daca n > 3, atunci intotdeauna exista cel putin un prim p intre n si 2n-2.Echivalent cu,daca n > 1,atunci intotdeauna exista cel putin un numar prim p a.i. n <. p<2n.

Observatia a fost prima oara facuta de Bertrand in 1845. A fost demonstrata in 1850 de Cebasev,folosind metode elementare si este ,deci,cateodata cunoscuta drept Teorema lui Cebasev.

O extindere a acestui rezultat este ca daca n> k,atunci exista un numar continand un divizor prim n > k in sirul n + 1,…,n + k – 1. (Cazul n = k + 1 atunci corespunde postulatului lui Bertrand.)

Numarul numerelor prime dintre n si 2n – 2 pentru n = 1,2,… este 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 4, …pe cand numarul numerelor prime dintre n si 2n este 0, 1, 1, 2, 1, 2, 2, 2, 3, 4, 3, 4, 3, 3, … Pentru n = 1, 2, …, valorile lui NP(n),unde NP(n) da cel mai mic numar prim mai mare decat n, sunt 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13, 17, 17, 17, 17, 19, …

Formula lui Binet pentru numere Fibonacci

A fost gasita de Binet in 1843,desi rezultatul era stiut de Euler,Daniel Bernoulli si de Moivre cu mai mult de un secol in urma.

Vom demonstra aceasta formula :

Fie sirul (xn)n≥0 definit prin :

xn+2 = axn+1 + bxn ,n ,a,b ,b ≠ 0 si

x0 = p0 , x = p1 , unde p0 , p1 .

Stim ca exista un singur sir care satisface (1) si (2).Pentru a determina sirul (xn)n≥0 definit de relatia de recurenta liniara de ordinul doi cu coeficienti constanti (1) si conditia (2) , se folosesc urmatoarele teoreme ajutatoare :

Teorema1.Daca sirurile (αn)n≥0 si (βn)n≥0 indeplinesc conditia (1), atunci sirul cu termenul general c1αn + c2βn indeplineste aceeasi conditie.

Demonstratie.Deoarece αn+2 = aαn+1 + bαn si βn+2 = aβn+1 + bβn rezulta ca

c1αn+2 + c2βn+2 = a(c1αn+1 + c2βn+1) +b(c1αn + c2βn) .

Teorema 2.

Daca α este o radacina a ecuatiei r2 = ar + b are radacini reale, distincte r1, r2 atunci αn satisface relatia (1).

Demostratie. Cum α2 = aα + b, amplificand cu αn se obtine

αn+2 = aαn+1 + bαn c.c.t.d.

Definitie. Ecuatie (3) r2 = ar + b se numeste ecuatia caracteristica asociata relatiei de recureneta (1).

Teorema 3. Daca ecuatia caracteristica r2 = ar + b are radacini reale, distincte

c1 + c2 = p0

r1, r2 atunci sistemul admite solutia unica.

c1.r1 + c2.r2 = p1

1 1

Demonstratie. Deoarece Δ = r1 r2 = r2 – r1 ≠ 0, conform teoremei lui Cramer rezulta ca sistemul are solutie unica.

Teorema 4. Daca ecuatia caracteristica r2 = ar + b admite o radacina dubla α, atunci sirul cu termenul general αn satsiface conditia (1).

Demonstratie. In ipotezele preconizate

(n+2) α2 – a (n+1) α – bn = n (α2 – aα – b) + α (2α-a) = 0.

Amplificand prin αn deducem concluzia.

Teorema 5. Daca ecuatia caracteristica r2 = ar + b admite o radacina dubla α, atunci

c1 = p0

sistemul are solutia unica

c1. α + c2. α = p1

Demonstratie. Deoarece b ≠ 0 rezulta α ≠ 0 si atunci c1 = p0 si

Teorema 6. Daca ecuatia r2 = ar + b are doua radacini reale distincte r1 si r2, atunci sirul care satisface conditiile (1) si (2) are termenul general de forma (4) xn = c1. r1n+ c1.r2n,

unde c1, c2 se determina in mod unic din conditiile initiale.

Demonstratie. Din teorema 2 rezulta r1n si r2n ca verifica conditia (1) si din teorema 1 rezulta xn = c1. r1n+ c1.r2n, verifica conditia (1) .

Relatie x0 = p0 si x1 = p1 determina unic c1, c2 prin teorema 3.

Teorema 7.Daca ecuatia caracteristica r2 = ar + b ,cu Δ < 0 are radacinile

r1 = R(cos t + i sint) atunci sirul care satisface conditiile (1) si (2) are termenul general de forma xn = Rn(c1 cos nt + c2 sin nt) ,unde c1 si c2 se determina în mod unic din conditiile initiale.

Demonstratie.Conform teoremei 2 sirul de numere complexe zn = r1n verifica ecuatia caracteristica de recurenta deci,conform formulei lui Moivre :

Rn+2[cos(n+2)t + i sin(n+2)t] = aRn+1[cos(n+1)t + i sin(n+1)t] + bRn [cos nt + i sin nt].

Separand partile reale si cele imaginare deducem egalitatile în :

Rn+2 cos(n+2)t = Rn+1 cos(n+1)t + Rn cos nt ,

Rn+2 sin(n+2)t = Rn+1 sin(n+1)t + Rn sin nt.

Amplificand aceste egalitati cu c1 , c2 si sumand deducem ca sirul de numere reale

xn = Rn(c1 cos nt + c2 sin nt) satisface relatia de recurenta .

Conditiile initiale revin la c1 = p0 si R(c1 cos nt + c2 sin nt) = p1.

Arece sint ≠ 0gasim c1 = p0 si .

Teorema 8. Daca ecuatia caracteristica r2 = ar + b admite o radacina dubla α, atunci sirul care satisface conditiile (1) si (2) are termenul general de forma (5) xn = c1. αn+ c2.n. αn,

unde c1 si c2 se determina in mod unic din conditiile initiale.

Demonstratie. Din teoremele 1, 2 si 4 rezulta ca sirul cu termenul general

xn = c1. αn+ c2.n. αn satisface conditia (1).

Relatiile x0 = p0 si x1 = p1 determina c1, c2 conform teoremei 5.

Exemple :

1) Sa se deteremine sirul (Fn)nЄN astfel incat

1° Fn+2 = Fn+1 + Fn n Є N ;

2° F0=1,F1=1 (sirul lui Fibonacci).

Solutie. Ecuatia caracteristica asociata sirului este r2 = r + 1 si are radacinile

, Sirul are termenul general de forma

, conditiile initiale impunand

, rezulta importanta formula a lui Binet :

2) Sa se determine sirul (Ln)n≥0 , definit prin :

1° Ln+2 =Ln+1 + Ln, n

° L0= 2, L1 = 1 (sirul lui Lucas). Procedand ca la exemplul 1 se obtine

.

.

2.4. Numere Fibonacci generalizate

O generalizare a numerelor lui Fibonacci definită prin 1 = G1 = G2 = …= Gc-1 si prin relația de recurență:

Gn = Gn-1 + Gn-c

Acestea sunt sume ale elementelor de pe diagonale succesive din triunghiul lui Pascal.Aceste numere satisfac identitatile :

(Bicknell-Johnson si Spears 1996). Pentru cazul special c=3,

Horadam (1965) a definit numerele generalizate Fibonacci {wn}ca wn = wn(a,b;p,q), unde a,b,p și q sunt intregi,w0 = a,w1 = b si wn = pwn-1 – qwn-2 pentru n ≥ 2.Ele satisfac identitățile:

unde:

(Dujella 1996). Rezultatul final de mai sus este datorat lui Morgado (1987) și este numit identitatea lui Morgado.

2.5. Numere prime Fibonacci

Fiecare Fn care este prim are ca indice un numar prim,cu exceptia lui F4 = 3. Dar reciproca nu este adevarata (adica nu orice indice prim p este al unui Fp prim).

Primele numere prime Fibonacci Fn sunt 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, … care se obtin pentru n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911, 130021, 148091, 201107, 397379, …( Dubner si Keller 1999), unde numerele lui Fibonacci cu indicele >35999(Caldwell) sunt de fapt probabil prime(exceptie face indicele 81839, pentru care s-a dovedit sa fie prim; Broadhurst 2001, Caldwell).

Cel mai mare probabil prim cunoscut Fibonacci este F590041.

Nu este cunoscut daca exista o infinitate de numere Fibonacci.

2.6. Primele 100 de numere Fibonacci descompuse în factori primi

Oricare număr Fibonacci mai mare decât 1,cu excepția lui F6 = 8 si F12 = 144, are cel puțin un factor prim care nu este factor pentru nici un alt număr Fibonacci anterior.

Primele 100 de numere Fibonacci
0 : 0
1 : 1
2 : 1
3 : 2
4 : 3
5 : 5
6 : 8 = 23
7 : 13
8 : 21 = 3 x 7
9 : 34 = 2 x 17
10 : 55 = 5 x 11
11 : 89
12 : 144 = 24 x 32
13 : 233
14 : 377 = 13 x 29
15 : 610 = 2 x 5 x 61
16 : 987 = 3 x 7 x 47
17 : 1597
18 : 2584 = 23 x 17 x 19
19 : 4181 = 37 x 113
20 : 6765 = 3 x 5 x 11 x 41
21 : 10946 = 2 x 13 x 421
22 : 17711 = 89 x 199
23 : 28657
24 : 46368 = 25 x 32 x 7 x 23
25 : 75025 = 52 x 3001
26 : 121393 = 233 x 521
27 : 196418 = 2 x 17 x 53 x 109
28 : 317811 = 3 x 13 x 29 x 281
29 : 514229
30 : 832040 = 23 x 5 x 11 x 31 x 61
31 : 1346269 = 557 x 2417
32 : 2178309 = 3 x 7 x 47 x 2207
33 : 3524578 = 2 x 89 x 19801
34 : 5702887 = 1597 x 3571
35 : 9227465 = 5 x 13 x 141961
36 : 14930352 = 24 x 33 x 17 x 19 x 107
37 : 24157817 = 73 x 149 x 2221
38 : 39088169 = 37 x 113 x 9349
39 : 63245986 = 2 x 233 x 135721
40 : 102334155 = 3 x 5 x 7 x 11 x 41 x 2161
41 : 165580141 = 2789 x 59369
42 : 267914296 = 23 x 13 x 29 x 211 x 421
43 : 433494437
44 : 701408733 = 3 x 43 x 89 x 199 x 307
45 : 1134903170 = 2 x 5 x 17 x 61 x 109441
46 : 1836311903 = 139 x 461 x 28657
47 : 2971215073
48 : 4807526976 = 26 x 32 x 7 x 23 x 47 x 1103
49 : 7778742049 = 13 x 97 x 6168709
50 : 12586269025 = 52 x 11 x 101 x 151 x 3001
51 : 20365011074 = 2 x 1597 x 6376021
52 : 32951280099 = 3 x 233 x 521 x 90481
53 : 53316291173 = 953 x 55945741
54 : 86267571272 = 23 x 17 x 19 x 53 x 109 x 5779
55 : 139583862445 = 5 x 89 x 661 x 474541
56 : 225851433717 = 3 x 72 x 13 x 29 x 281 x 14503
57 : 365435296162 = 2 x 37 x 113 x 797 x 54833
58 : 591286729879 = 59 x 19489 x 514229
59 : 956722026041 = 353 x 2710260697
60 : 1548008755920 = 24 x 32 x 5 x 11 x 31 x 41 x 61 x 2521
61 : [anonimizat] = 4513 x 555003497
62 : 4052739537881 = 557 x 2417 x 3010349
63 : 6557470319842 = 2 x 13 x 17 x 421 x 35239681
64 : 10610209857723 = 3 x 7 x 47 x 1087 x 2207 x 4481
65 : 17167680177565 = 5 x 233 x 14736206161
66 : 27777890035288 = 23 x 89 x 199 x 9901 x 19801
67 : 44945570212853 = 269 x 116849 x 1429913
68 : 72723460248141 = 3 x 67 x 1597 x 3571 x 63443
69 : 117669030460994 = 2 x 137 x 829 x 18077 x 28657
70 : 190392490709135 = 5 x 11 x 13 x 29 x 71 x 911 x 141961
71 : 308061521170129 = 6673 x 46165371073
72 : 498454011879264 = 25 x 33 x 7 x 17 x 19 x 23 x 107 x 103681
73 : 806515533049393 = 9375829 x 86020717
74 : 1304969544928657 = 73 x 149 x 2221 x 54018521
75 : 2111485077978050 = 2 x 52 x 61 x 3001 x 230686501
76 : 3416454622906707 = 3 x 37 x 113 x 9349 x 29134601
77 : 5527939700884757 = 13 x 89 x 988681 x 4832521
78 : 8944394323791464 = 23 x 79 x 233 x 521 x 859 x 135721
79 : 14472334024676221 = 157 x 92180471494753
80 : 23416728348467685 = 3 x 5 x 7 x 11 x 41 x 47 x 1601 x 2161 x 3041
81 : 37889062373143906 = 2 x 17 x 53 x 109 x 2269 x 4373 x 19441
82 : 61305790721611591 = 2789 x 59369 x 370248451
83 : 99194853094755497
84 : 160500643816367088 = 24 x 32 x 13 x 29 x 83 x 211 x 281 x 421 x 1427
85 : 259695496911122585 = 5 x 1597 x 9521 x 3415914041
86 : 420196140727489673 = 6709 x 144481 x 433494437
87 : 679891637638612258 = 2 x 173 x 514229 x 3821263937
88 : 1100087778366101931 = 3 x 7 x 43 x 89 x 199 x 263 x 307 x 881 x 967
89 : 1779979416004714189 = 1069 x 1665088321800481
90 : 2880067194370816120 = 23 x 5 x 11 x 17 x 19 x 31 x 61 x 181 x 541 x 109441
91 : 4660046610375530309 = 132 x 233 x 741469 x 159607993
92 : 7540113804746346429 = 3 x 139 x 461 x 4969 x 28657 x 275449
93 : 12200160415121876738 = 2 x 557 x 2417 x 4531100550901
94 : 19740274219868223167 = 2971215073 x 6643838879
95 : 31940434634990099905 = 5 x 37 x 113 x 761 x 29641 x 67735001
96 : 51680708854858323072 = 27 x 32 x 7 x 23 x 47 x 769 x 1103 x 2207 x 3167
97 : 83621143489848422977 = 193 x 389 x 3084989 x 361040209
98 : 135301852344706746049 = 13 x 29 x 97 x 6168709 x 599786069
99 : 218922995834555169026 = 2 x 17 x 89 x 197 x 19801 x 18546805133
100 : 354224848179261915075 = 3 x 52 x 11 x 41 x 101 x 151 x 401 x 3001 x 570601

2.7. Numere tribonacci, matricea Fibonacci , șirul Fibonacci aleator,

coeficientul Fibonacci

Fie șirul definit făcând pentru k ≤ 0 , , și ceilalți termeni conform relației de recurență :

pentru k > 2. Primii câțiva termeni din șirurile acestea sunt :

Limita se obține rezolvând:

Sau echivalent cu:

și alegând rădăcina reala > 1.Pentru n par,sunt exact două rădăcini reale,una mai mare decât 1 și una mai mică decât 1,iar pentu n impar există exact o rădăcină ,care este întotdeauna ≥ 1.

Dacă n = 2,ecuația (2) devine:

cu soluțiile:

Raportul este deci:

Care este chiar raportul de aur,așa cum ne așteptam.

Soluțiile analitice pentru n = 1,2,…sunt date de:

Numere Tribonacci

Numerele tribonacci sunt o generalizare a numerelor lui Fibonacci definite de:

T1= 1,T2 = 1,T3 = 2 și relația de recurență:

Tn = Tn-1 +Tn-2 + Tn-3 (1)

pentru n ≥ 4.Ele reprezintă cazul n =3 pentru numerele lui Fibonacii în n pași.Primii

cațiva termeni pentru n = 0,1,2,…sunt 0,1,1,2,4,7,13,24,44,81,149,…

Primii cațiva termeni primi tribonacci sunt 2,7,13,149,…care au indicii 3,5,6,10,…

O expresie exactă pentru al n-lea număr tribonacci poate fi dată explicit prin formula:

unde (α,β,γ) sunt rădăcinile polinomului:

Intr-o formă mai concisă putem scrie:

Unde rn este a n-a radacină a polinomului:

Matricea Fibonacci

Matricea Fibonacci Q este astfel definita

unde Fn este numar Fibonacci.Atunci

Matricile Q ne conduc imediat la un important număr de identități Fibonacci,inclusiv

care duce la

ne conduce la

și

ne conduce la

Șirul Fibonacci aleator

Să considerăm recurența de tip Fibonacci

unde ao = 0,a1 = 1, și fiecare semn este ales independent și aleator,cu probabilitatea de 1/2. În mod surprinzător, Viswanath (2000) a arătat că :

cu probabilitatea unu.Această constantă este cateodată cunoscută drept constanta lui Viswanath.

Coeficientul Fibonacci

Coeficientul lui Fibonacci este definit prin

unde și Fn este un numar Fibonacci.Acest coeficient satsface

pentru k > 0, unde Ln este un număr Lucas.

Triunghiul coeficienților lui Fibonacci este:

Capitolul III. Numerele lui Lucas

3.1.Prezentare.Proprietăți

Numerele lui Lucas sunt companionii numerelor lui Fibonacci și satisfac următoarea relație de recurență:

Unde L1 = 1 si L2 = 3. Primele câteva sunt 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, …

Singurele pătrate dintre numerele Lucas sunt 1 și 4, fapt dovedit de John H. E. Cohn (Alfred 1964). Singurele numere triunghiulare Lucas sunt 1 si 3, și 5778 (Ming 1991). Singurul cub dintre numerele Lucas este 1.

Primele câteva numere Lucas prime sunt 3, 7, 11, 29, 47, 199, 521, 2207, 3571, … corespunzând indicilor n = 2, 4, 5, 7, 8, 11, 13, 16, 17, 19, 31, 37, 41, 47, 53, 61, 71, 79, 113, 313, 353, … (Dubner si Keller 1999). Cel mai mare numar Lucas probabil prim este L574219, care are 120.005 de cifre (Lifchitz si Lifchitz).

Analog formulei Binet pentru numere Fibonacci, pe care am demonstrat-o de fapt atunci când am vorbit despre formula Binet pentru numere Fibonacci, avem:

Printre identitățile satisfăcute de numerele lui Lucas sunt și urmatoarele:

Numerele lui Lucas satisfac urmatoarea recurentă :

unde este un coeficient Fibonacci .

descompunerea în fracții

unde

și formula de sumare

unde

Fie p un număr prim > 3 și k un numar întreg pozitiv.Atunci se termină in 3. Analoage ale identitatilor lui Cesàro pentru numere Fibonacci sunt:

unde este un coeficient binomial.

Definind

obținem

3.2. Identități cu numere Fibonacci și numere Lucas

Numeroase relații între numerele Fibonacci și Lucas pot fi găsite.Vom da în acest subcapitol destul de multe,o parte dintre ele fiind deja demonstrate în capitolele anterioare.

(84)

(85)

(86)

(87)

(88)

(89)

(90)

(91)

(92)

(93)

(94)

(95)

(96)

Numere complexe

Phi si –phi sunt radacinile ecuatiei x2 = x + 1.

Capitolul IV. Aplicații

4.1. Utilizări ale șirului Fibonacci

4.1.1. Algoritmul de căutare Fibonacci

1. Formularea problemei de căutare

În prelucrarea informațiilor cu ajutorul calculatorului un loc aparte îl ocupă

așa numitul proces de căutare. Prin căutare se întelege operatia de localizare a unei date specifice intr-o secventă cunoscută de date de același tip. Căutarea presupune două operatii distincte : memorarea datelor și regăsirea acestora.

Memorarea datelor impune alegerea unei structuri de date. Structura de tablou este potrivită pentru memorarea datelor în problema de căutare statică. Presupunem că fiecare dată, element al tabloului, este o colectie de informații, eventual de tipuri diferite, îin cadrul căreia există o porțiune, pe care o vom numi cheie, prin intermediul căreia se identifică unic întreaga dată. Ca urmare, structura de date utilizată într-o problemă de căutare reală este aceea de tablou de articole. Vom nota cu a[i] cheia corespunzătoare articolului R[i] ( cheia este un câmp al articolului). Memorarea datelor în procesul de căutare poate fi potrivită ca problema in care se dă un tablou vid si o secvență arbitrară de date si folosind un algoritm de memorare particular se introduc în tablou datele din secvență.

Procesul de regăsire consideră dat tabloul deja completat, parțial sau total; el constă din căutarea în tablou a acelui articol a cărui cheie a[i] se potriveste cu o cheie data x, la care ne vom referi ca la cheia de căutare. Algoritmii de căutare, datorită celor două operații pe care le implică, sunt adesea referiți ca algoritmi de memorare si regăsire. In cele ce urmează ne vom concentra atentia asupra procesului de regasire a informației din tabloul dat.

Localizarea unui articol în cadrul tabloului, prin intermediul cheii sale, asigură accesul la informatia din cadrul articolului (cel mai adesea extragerea informațiilor din câmpurile sale). Reamintim că tabloul este o structură de date statică; de aceea, operații ca adăugarea unor noi informații sau ștergerea ocazională de informații regăsite mai bine prin utilizarea unei structuri de date dinamice (listă, stivă).

In prezentarea algoritmilor de căutare nu vom intra în detalii legate de prelucrarea informației la care acești algoritmi asigură accesul și vom presupune că nu se realizează modificări în zona de memorie a tabloului (adică colecția de date este statică, dată pentru totdeauna).

Considerăm următorea specificație a problemei de căutare:

Sunt date: un tablou A de chei distincte, a [1], a [2],…, a [n], care conține o listă de valori (eventual vidă) si o cheie x particulară, de același tip cu cheile din tablou. Se caută indiciile valori x în tablou. Întrucat căutarea poate fi cu sau fără succes după cum cheia x se află sau nu in tabloul dat, sunt posibile două răspunsuri: “da” urmat de poziția cheii particulare in cadrul tabloului sau “nu” când cheia x nu se află in tablou (valoarea 0 pentru indice).

Deoarece, ansamblu, procesul de căutare a datelor implică un mare consum de timp este nevoie de algoritmi de cautare eficienți. Operația de bază în algoritmii de căutare este aceea de comparare a cheii de căutare x cu cheile din tablou. Ca urmare, numărul de comparări necesare pentru o căutare particulară poate fi folosit ca o masură a eficienției (operație fundamentală).

Un număr realtiv mare de algoritmi de căutare se bazează pe utilizarea tablourilor ordonate liniar. Fie a [1], a [2],…, a[n] un tablou de n chei distincte. Un tablou ordonat liniar se obține prin sortarea tabloului ce corespunde secvenței inițiale arbitrare. Căutarea are sens numai dacă cheia de căutare x satisface conditia a [1]≤ x ≤ a[n]. Există un grup de metode de căutare în tablouri ordonate liniar, numite metode de căutare binara. Toate se bazeaza pe un același principiu: se selectează din tablou o cheie a[i], după o regulă fixată (în cadrul metodei alese) care va fi cea dintâi comparată cu cheia x. Sunt posibile trei situații:

x = a [i] caz în care cautarea ia sfârșit cu success;

x < a [i] caz în care domeniul căutării se restrânge la elementele a [1],…,a[i-1]

și căutarea se reia conform aceluiași principiu;

3. x > a [i] caz în care domeniul căutarii se restrânge la elementele

a [1+1],…, a[n] si căutarea se reia conform aceluiasi principiu.

Algoritmul se termină când cheia dorită a fost localizată sau când domeniul căutarii nu mai poate fi restrâns.

Metodele de căutare din acest grup se diferențiaza după modul de alegere a cheii

a [i] pentru prima comparare cu cheia x si în raport cu cunoașterea sau necunoașterea probabilităților de acces a cheilor din tablou. Vom presupune în continuare că frecvențele de acces ale cheilor sunt necunoscute și vom considera că sunt echiprobabile. Întrucât structura de arbore binar joacă un rol fundamental în analiza acestui grup de tehnici de căutare, ele mai sunt cunoscute sub numele de metode de căutare pe arbori sau metode de căutare binară. Un algoritm optimal în clasa metodelor de căutare binară este cel cunoscut sub numele de căutare binară standard: prima cheie comparată cu cheia de căutare x este cheia din mijlocul tabloului.

În clasa metodelor de căutare binară există o metodă particulară cunoscută sub numele de căutare Fibonacci întrucât utilizează numerele Fibonacci:

Fk = Fk-1 + Fk-2 , F0 = 0, F1 = 1, k>1.

Căutarea Fibonacci poate fi folosită pe tablouri în care numărul cheilor n este de forma n = Fk-1, cu Fk un număr Fibonacci cu k>1.

2.Algoritmul pentru căutarea Fibonacci :

{n = Fk-1; Fk = Fk+1 + Fk-2}

var

cont: Boolean; loc: integer;

begin

if a [1] ≤ x ≤ a [n]

then begin

i: = Fk-1; p: = Fk-2 ; q: = Fk-3;

{pe tot parcursul algoritmului p si q sunt numere Fibonacci consecutive}

cont: = true;

while cont do

begin

if x = a [i]

then begin cont: = false; loc: = i end

else if x < a [i]

then if q = 0

then begin cont: = false; loc: = 0 end

else begin i: = i-q; t: = p; p: = q; q: = q-t end

else if p = 1

then begin cont: = false; loc: = 0 end

else begin i: = i + q; p: = p -1; q: = q – p end

end;

write loc

else write “căutarea nu are sens”

end;

O structură de date care este potrivită pentru procesele de căutare descris este arborele de căutare binary. Arborii de căutare binary reprezintă una dintre tehnicile cele mai flexibile si mai bine întelese pentru organizarea colecțiilor mari de date.

Pentru un tablou a [1],…, a [n] vom construi arborele binar de căutare asociat ca un arbore binar etichetat în care fiecare nod i este etichetat printr-un element a [i] care aparține lui A, astfel ca:

Pentru fiecare nod j în subarborele stâng al lui i, a [j] < a [i];

Pentru fiecare nod j în subarborele drept al lui i, a [j] > a [i];

Pentru fiecare cheie x care este în tabloul A, există exact un nod i astfel ca

a [j] = x.

Rădăcina arborelui este acea cheie a tabloului care este comparată prima cu cheia de căutare x . La un tablou dat putem asocia mai mulți arbori binary, corespunzător la metode particulare de căutare binară ( algoritmul rădăcinii).

Figura 4 arată un arbore binar pentru un tablou cu n = 12 care constituie reprezentarea arbore a căutării Fibonacci.

Nivelele într-un arbore de căutare binar se numară de la 0 (nivelul rădăcinii), k fiind cel mai mare nivel sau ultimul nivel. În exemplul dat k = 4.

Complexitatea diferiților algoritmi de căutare poate fi studiată pe arborii binary corespunzători.

Adâncimea unui arbore este nivelul maxim, deci adâncimea maximă a nodurilor sale și reprezintă lungimea celei mai lungi ramuri de la rădăcină la un nod terminal. Un arbore binar se va numi balansat daca adâncimea subarborelui stâng al fiecărui nod nu diferă niciodată prin mai mult de + l – 1 de adâncimea subarborelui drept al aceluiași nod. Arborele binar corespunzător metodei binare standard este balansat; de asemenea cel pentru căutarea Fibonacci.

Când frecvențele de acces ale cheilor sunt cunoscute este mai avantajos să se folosească arbori binari nebalansați cu așa numita lungime de drum ponderată care este definită luând în calcul (frecvențele cheilor sunt referite ca ponderi ale nodurilor).

Distingem între arbori balansați pentru chei distribuite uniform (algoritmul de căutare binară și folosirea arborilor Fibonacci) și arbori nebalansați pentru diferite distribuții neuniforme ale cheilor. Au fost proiectați algoritmi pentru construirea de arbori binary optimali sub presupuneri de diferite distribuții ale cheilor. Acești algoritmi prezintă un interes mai mult teoretic.

Metoda de căutare pe arbore binar are următoarea structură de bază:

Pentru a găsi dacă o cheie de căutare este în arbore o comparăm cu cheia din radacină și apar cazurile:

nu există rădacină (arborele binar este vid); cheia de căutare nu este în arbore și căutarea se termină fără success;

cheia de căutare coincide cu cheia din rădacină; căutarea se termină cu success;

cheia de căutare este mai mică decât cea din rădacină; căutarea continuă cu examinarea subarborelui stâng al rădăcinii în același mod;

cheia de căutare este mai mare decât cea din rădăcină: căutarea continuă cu examinarea subarborelui drept al rădăcinii în același mod.

Vom numi costul unui arbore de căutare binar numărul de comparații cerut de

o căutare particulară pe arbore. O definiție echivalentă a costului unui arbore poate fi dată adăugând întâi arborelui n + 1 noduri terminale fictive, într-o manieră arătată în figura 5 și apoi definind următoarele:

Dacă o cheie de căutare x este eticheta a [i] a unui nod i, atunci numărul de noduri vizitate când căutăm x este cu unu mai mare decât adâncimea nodului i.

Dacă x nu este în tabloul A și a [i] < x < a [i+1] atunci numărul de noduri vizitate pentru a-l căuta pe x este egal cu adâncimea nodului terminal fictiv i.

Din descrierea unui arbore de căutare binar vedem că adâncimea unui astfel de arbore și deci costul său este direct legată de modul in care:

este selectată rădăcina arborelui (sau cheia din tablou pentru prima comparație) și

este selectată o strategie “divide-et-impera” folosită în construcția arborelui.

Algoritmul de căutare Fibonacci selectează ca rădăcină a arborelui binar de

de căutare acel element al tabloului al carui indice este numarul Fibonacci ce precede imediat in sirul Fibonacci numarul Fk ce satisface relatia n= Fk – 1.

Strategia “divide-et-impera” folosita in constructia arborelui selecteaza radacinile subarborilor stang si drept in acelasi fel ca radacina arborelui respectand-se conditiile din definitia unui arbore binar de cautare.

Eficienta metodei de cautare Fibonacciana a fost studiata de Overhold (1973) care a aratat ca nu este optimala in termini de numar de comparari necesare. In mod specific timpul este cu 4% mai mare decat la cautarea binara standard.

4.1.2. Distribuția Fibonacci în sortarea externă prin interclasare

Sortare datelor este unul dintre cele mai commune procese in informatica si constituie o parte esentila a unui numar mare de programe de prelucrare a informatiilor.

Sortarea datelor consta in rearanjarea unei colectii de informatii structurata de obicei ca un tablou de articole astfel incat sa fie intr-o anumita ordine, crescatoare sau descrescratoare, in raport cu valorile unuia sau mai multuro dintre campurile fiecarui element al colectiei.

Consideram dat un tablou de articole ce urmeaza a fi sortat.

Prin cheie sau cheie de sortare referim o parte componenta a articolului, in raport cu acre se face sortarea. In principiu cheia de sortare constituie un identificator al articolului, adica pentru articole diferite valorile cheilor corespunzatoare sunt distincte. Pot exista mai multe chei de sortare : cheie-1, cheie-2, …, cheie-n, ele sunt considerate ierarhic in procesul de sortare in sensul ca pentru articole cu aceeasi valoare pentru cheie-1 se face aranjarea potrivit ordinii dorite pentru cheie-2 si asa mai departe. Sortarea cu chei multiple nu comporta dificultati majore in raport cu sortarea dupa o singura cheie, motiv pentru care ne vom restrange la sortarea dupa o singura cheie a tabloului de articole. Fiecare articol poate fi considerat ca avand structura generala

Prin intermediul cheii de sortare un articol poate fi consultat sau actualizat, partial sau total, in campurile inf-1 si inf-2, dar numai cheia de sortare intervine essential in procesul de sortare.

Întrucât informațiile inf-1 si inf-2 ce sunt asociate cheii de sortare nu intervin în procesul de sortare, vom studia procesul de sortare limitându-ne la valorile cheilor k [1], k[2], …, k[n].

Lista cheilor k [1], k [2], …, k [n] este sortată în ordine crescătoare (nedescrescătoare) dacă i < j implică k [i] ≤ k [j] și este în ordine descrescătoare (necrescătoare) dacă i < j implică k [i] ≥ k [j] pentru toate elementele listei.

Cea mai comună abordare pentru sortarea externă este o sortare internă urmată de o interclasare. Metodele de sortare externă cele mai utilizate se bazează pe interclasarea a doua fisiere numită și interclasare pe 2-căi. Deoarece interclasările trebuie facute in mod repetat, acești algoritmi sunt numiți algoritmi de sortare prin interclasare polifazată.

Definim o monotonie ca o secventă de chei in ordine nedescrescătoare; o monotonie reprizintă un subfișier ordonat.

Schema generala a sortarii externe are doua etape:

Crearea monotoniilor si distributia lor;

Interclasarea polifazata care interclaseza in mod monotoniile pana cand exista numai una.

Algoritmul de interclasare a doua fisiere reuneste intr-un nou fisier sortat

Continutul a doua fisiere sortate in acelasi f el ( crescator sau descrescator).

Fie f = < f1 , f2, …, fm > si g = < g1 , g2, …, gn > doua fisiere sortate crescator, adica:

i, j ((1≤ i < j ≤ m) => (fi< fj)), i, j ((1≤ i < j ≤ n) => (gi<gj)).

Algoritmul de interclasare a lor creeaza un nou fisier sortat h, unde h = < h1,

h2 , …, hm+n > reunind continutul fisierelor f si g, deci :

i, j ((1≤ i < j ≤ m+n)) => (hi<hj)) si

(f1 f2… fmg1 g2 … gn) permute (h1 h2…hm+n).

Presupunem ca numarul cheilor in lista supusa sortarii este atat de mare incat ele nu pot incapea toate in memoria interna la un moment dat astfel ca unele trebuie memorate pe un dispozitiv de memorie externa. Vom presupune ca benzile magnetice sunt folosite in acest scop. (Metodele prezentate pot fi folosite cu modificari minore cand se foloseste un alt support extern).

La inceput procesului de sortare externa avem la dispozitie un numar specificat de benzi magnetice pe care-l notam cu T. Orice metoda de sortare cu T benzi partitioneaza benzile in doua grupuri. Primul grup este folosit pentru distributia monotoniilor initiale (in ordine alternativa) si al doilea grup este intai folosit in prima faza de interclasare ; rolurile grupurile sunt apoi inversate in urmatoarele faze de interclasare.

Citirea cheilor este una din operatiile esentiale in sortarea externa. O problema importanta relativ la eficienta unui algoritm de sortare externa este distributia monotoniilor initiale pe benzi intr-un mod care sa minimizeze numarul de parcurgeri complete a cheilor.

O alta problema importanta este crearea monotoniilor intr-un mod care sa minimizeze numarul de parcurgerii complete a cheilor necesar pentru a face sortarea.

Intrucât scopul final al sortării externe este de a produce un singur fișier sortat este preferabil sa creăm monotonii inițiale care sunt cât mai lungi, ceea ce micsoreaza numarul fazelor de interclasare. Pe de alta parte, cresterea lungimii unei monotonii initiale face necesare opertaii suplimentare in timpul fazei de sortarea interna si intrucat pentru toti algoritmi de sortare interna cunoscuti, acest cost creste mai rapid decat liniar cu lungimea medie a monotoniei pana la care putem merge.

Fie n numarul total de chei de sortat si m numarul de chei care se pot pastra in memoria interna la un moment dat impreuna cu programele necesare pentru efectuarea sortarii. Lungimea unei monotonii create initial poate fi cel mult m.

Presupunem ca monotoniile cretae initial au aceesai lungime (de fapt ultima poate fi mai mica). Fie S numarul monotoniilor create initial si P numarul de cai folosite, numit si ordinul de interclasare.

Distributia monotoniilor pe benzile folosite in faza curenta intr-o interclasare cu P-cai influenteaza eficienta algoritmului deoarece fazele de copiere sunt faze pasive si un algoritm eficient le va evita.

Varianta pentru care in fiecare faza monoteniile sunt distribuite cat mai egal posibil pe benzile folosite in sortarea curenta constituie un exemplu de interclasare balasanta cu P-cai.

O varianta eficienta corespunde unei distributii foarte particulare a monotoniilor care foloseste numerele Fibonacci si proprietarile lor. Aceasta varianta este asa-numita sortare polifazata bazata pe distributii Fibonacci perfecte.

Se pare ca Knuth (1973) a imbunatatit primul teoria metodei de interclasare polifazata observand relatia sa cu asa-numitele distributii Fibonacci.

Distributiile Fibonacci sunt bazate pe numerele Fibonacci definite prin relatia de recurenta :

Fn = Fn-1 + Fn-2, n≥2, F0 = 0, F1=1. (1)

Primele 10 numere Fibonacci sunt :

F0 = 0, F1 =1, F2 = 1, F3 = 2, F4 = 3, F5 =5, (2)

F6 = 8, F7 = 13, F8 = 21, F9 = 34 , F10 = 55.

Fie T = 3, P = 2 si S =13. Pentru acesti parametri, trei variante de interclasare a monotoniilor initiale sunt date in tabelul1. In acest tabel, ‘1, 1, 1, 1, 1, 1, 1 ‘ desemneaza sapte monotonii initiale ; ‘2, 2, 2’ desemneaza trei monotonii de lungime relativa 2 ; etc.

Varianta 1 este un exemplu de interclasare balansata cu P-cai (P=2).

Varianta 2 este o modificare a interclasarii balansate cu 2-cai folosind 3 benzi.

Varianta 3 este un exemplu de sortare polifazata bazata pe distributii Fibonacci perfecte, intrucat, avem :

S = Fn= Fn-1 + Fn-1 = F7 = F6 + F5 = 13 = 8+5 (3)

Distributia initiala a monotoniilor pe T1 si T2 , in modul definit prin (3),

elimina complet faza de copiere si metoda cere exact (n-1) faze pentru a termina sortarea.

Distributia monotoniilor initiale definita prin (3) si (1) este numita distributia Fibonacci perfecta.

Daca numarul monotoniilor initiale nu se potriveste cu distributia Fibonacci perfceta, se pot adauga monotonii fivtive pentru a putea aplica distributia Fibonacci. Numerele Fibonacci date prin (1) pot fi legate in mod explicit de cantitea P = 2, folosind notatia urmatoare :

Fn(2) = Fn-1(2) + Fn-2(2), n≥2, F0(2) =0, F1(2) = 1 (4)

Tabelul 1

Aceasta notatie poate parea artificiala dar este convenabila pentru analiza sortarii polifazate generale cu T-benzi intrucat forma (4) poate fi generalizata intr-un mod direct pentru a defini numerele Fibonacci pentru orice p, adica

Fn(p) = Fn-1(p) + Fn-2(p) +…+ Fn-p(p), n≥p,

(5)

F0(p) = 0, F1(p) =0, …, Fp-2(p)= 0, Fp-1(p)= 1.

Sirul Fibonacci generalizat (5) este referit ca numere Fibonacci de ordinul p.

Spre exemplu, primele 11 numere Fibanacii de ordinul 4 (al IV-lea) sunt :

F0(4) = 0, F1(4) =0, F2(4)=0, F3(4)=1, F4(4)=1, F5(4)= 2,

(6)

F6(4) = 4, F7(4) =8, F8(4)=15, F9(4)=29, F10(4)=56, F11(4)= 108.

Șirul (5) este folosit pentru a produce distribuții Fibonacci perfecte într-o sortare externă când P>2. Un detaliu important al sortărilor bazate pe distribuții Fibonacci perfecte este presupunerea că P = T-1 pentru orice T dat. Aceasta inseamnă că în aceste sortării numai o bandă este facută liberă la sfârsitul fiecărei faze.

În general, dacă numărul de monotonii construite în prima fază a sortării externe cu trei nezi T0, T1, T2 este un număr Fibonacci, Fs, pentru un anume s, atunci distribuind monotoniile astfel incât Fs-1monotonii sunt pe o banda si Fs-2 pe cealalta, suntem asigurati ca vor fi intotdeauna monotonii pe doua benzi gata pentru interclasare fara a copia chei, pana cand cheile sunt sortate. Presupunand ca faza de construcite a monotoniilor a pus Fs-2 monotonii pe T1 si Fs-1 monotonii pe T2, etapa a 2-a din schema generala a sortarii externe pe trei benzi se realizeaza prin urmatorul algoritm, cunoscut sub numele de algoritmul de interclasare cu trei benzi folosind o distributie Fibonacci :

{Interclasare monotonii}

i1 : = 1 ; i2 : = 2 {indicii benzilor de intrare}

j : = 0 {indice pentru banda de iesire}

while exista mai mult decat o monotonie do

begin

Interclaseaza monotonii din Ti1 si Ti2 punand monotoniile rezulatte pe Tj,

pana cand Ti1 este vid.

Rebobineaza Ti1 si Tj .

i1 : = i1+1 ; i2 := i2+1 ; j : = j+1 ; (toate modulo 3).

end.

Numarul de parcurgeri ale cheilor in sortarea externa cu algoritmul de interclasare

cu 3 benzi folosind o distributie Fibonacci este aproximativ 1,04 log2r, r fiind numarul de monotonii create in prima faza a sortarii externe. Folosirea distributiei Fibonacci este de asemenea foarte folositoare daca mai multe benzi sunt disponobile ; ea poate fi generalizata pentru a proiecta algoritmi foarte rapizi.

4.2.Secțiunea de aur în geometrie

Numărul de aur

4.2.1. Constanta ≈ 1.618 este unul dintre cele mai celebre numere

din istoria culturală,socială și fizică a omenirii.El are proprietăți matematice de o eleganța extremă,cum ar fi următoarele:

( n numere 1 sub radical )

b) (n numere 1 în fracția continuă)

c)dacă (xn)n≥1 este șirul lui Fibonacci atunci putem arăta că

Xn = și

Luca Pacioli a denumit numarul de aur “proportia divina”,Johann Kepler l-a numit “sectiunea divina”,iar Leonardo da Vinci I-a spus “sectiunea de aur”.

Din punct de vedere geometric (fig. 1) numărul de aur este raportul în care trebuie împărțit un segment AB printr-un punct C a.î. AC > CB și “întregul (adică AB) să fie față de partea mai mare (adică AC) cum este partea mai mare (adică AC) față de partea mai mică (adică CB)”.Spunem că l-am împărțit pe AB în medie și extremă rație.

Trebuie să avem deci (notam AB = a,CB = B) adică .

Fig.1

Scriind obținem ecuația ,adică ,deci .

Ultima ecuație are soluțiile si .

Reținem soluția pozitivă și avem deci .

Dându-se segmentul AB , putem construi geometric punctul C ca mai sus (fig. 2).

Notăm AB = 2c și construim BD AB așa ca BD = c.În triunghiul dreptunghic ABD

avem .Luăm E (AD) așa ca DE = BD = c și apoi luăm C (AB) așa ca

AC = AE.Vom avea AE = AD – ED = ,deci .

Rezultă că .

Atunci, avem într-adevar că .

Fig.2

Numărul de aur, semnalat încă de școala lui Pitagora, a intervenit și intervine în pictură, sculptură, muzică, geometrie, creșterea biologică, chimie, dezintegrare radioactivă , demografie etc.

4.2.2. Împărțirea în medie și extremă rație este întâlnită destul de des în geometrie.

Latura L10 a decagonului regulat (fig. 3) înscrisă într-un cerc de rază R este egală,după

cum se știe,cu adica 2 R sin 18º .

Ptem calcula .

Așadar L10 =

Fig. 3

Cu alte cuvinte L10 este egal cu partea cea mai mare a razei cercului care a fost împărțită în medie și extremă rație.

În mod practic, pentru calculul lui L10, putem alege în loc de raportul a două numere vecine din șirul Fibonacci și să considerăm că L10 este aproximativ egal cu

sau chiar cu .

4.2.3. Să considerăm un pentagon regulat .Diagonalele lui formează un pentagon regulat stelat (fig. 4).

Unghiul AFD este egal cu 108º,iar unghiul ADF este efal cu 36º.Deci,conform teoremei sinusurilor,avem :

Deoarece este evident că , avem :

,și punctul C împarte segmentul

[AD] în medie și extremă rație.Însă,conform definiției împărțirii în medie și extremă rație

.

Observând că , obținem : .

Așadar, șirul de segmente [BC], [AB], [AC], [AD] este astfel încât fiecare segment este de ori mai mare decât precedentul.

Putem de asemenea arăta că .

4.2.3. Dreptungi cu secțiunea de aur

Un dreptunghi de aur este acel dreptunghi în care raportul lungimilor laturilor este egal cu ф și dacă împărțim acest dreptunghi într-un pătrat și un nou dreptunghi,acesta din urmă este tot un dreptunghi de aur. Euclid a folosit următoarea construcție pentru dreptunghiuri de aur.Desenăm pătratul ABCD, luăm E mijocul lui AC, a.î. AE = EC = x. Acum desenăm segmentul BE, care are lungimea:

Și construim EF cu această lungime.Acum completăm dreptunghiul CFGD, care este de aur având în vedere că

Dacă unim punctele succesive ce împart un dreptunghi de aur în pătrate obținem o spirală logaritmică.

Dreptunghiurile cu secțiune de aur par “proporționale” și sunt plăcute ca aspect.S-a constatat că este avantajos să utilizăm obiecte care au aceasta formă .De aceea, multor obiecte, dreptunghice, din viața noastră de toate zilele ( cărți, cutii de chibrituri, geamantane,etc. ) li se dau adeseori această formă.

Datorită aspectului frumos al dreptunghiului cu secțiune de aur și a altor figuri în care există împărțirea în medie și extremă rație, diferiți filozofi idealiști din antichitate și evul mediu construiau un principiu estetic și chiar filozofic din aceasta.Prin impărțirea în medie și extremă rație, cum și prin alte rapoarte numerice,se încerca să se explice fenomenele naturii și vieții sociale, iar cu numărul și cu fracțiile lui reduse se efectuau diferitele “operații” mistice.Se înțelege că asemenea teorii nu au nimic în comun cu știința.

O demonstrație fără cuvinte pentru suma pătratelor numerelor Fibonacci

F1 = F2 = 1 ; Fn+2 = Fn+1 + Fn => F1² + F2² +…+Fn² = Fn Fn+1

Demonstrație dată de Alfred Brousseau

(După cartea "Proofs without Words" de Roger B. Nelsen,

Math. Ass. of America )

4.3. Numerele Fibonacci în natura

Secretul numărului de aur

Cunoscut în antichitate de vechii înțelepți, iar apoi în evul mediu de marii învățați filozofi, geometri, preoți, alchimiști sau ocultiști, numărul de aur a ascuns întotdeauna mari mistere. Astăzi cercetări complexe au ajuns la concluzia că întreaga natură și chiar întreg universul este structurat respectând fidel proporția perfectă și exactă a numărului de aur. Marile construcții antice precum piramidele sau templele și catedralele respectă de asemenea proporția fidelă a acestui număr de aur. El reprezintă armonia și perfecțiunea în creație.

Proporția tainică a acestui număr reprezentată fie în triunghiul de aur (isoscel) al lui Pitagora, în elipsa de aur din tradiția hindusă sau în spirala de aur care prin șirul lui Fibonacci demonstrează creșterea naturală a plantelor păstrând această proporție.
În natură spirala generată de apă (vârtejurile), mișcarea curenților de aer în spirală, cochilia melcilor, dispunerea petalelor de tranafir sau a frunzelor și semințelor din regnul vegetal păstrează această proporție perfectă arătând că în întreaga creație se manifestă armonia și perfecțiunea divină reprezentată prin această proporție. Aceasta demonstrează existența unei sfere de conștiință a armoniei și frumuseții existente în întregul univers și care îl ghidează.

Probabil că mulți dintre noi nu ne-am făcut vreodată timp să examinăm cu atenție o floare și numărul de petale al acesteia.Dacă am face însă acest lucru, am observa în primul rând că numărul de petale ale unei flori este adesea un numar Fibonacci.Flori cu o petală…
 

și cu două nu sunt prea comune. Cu trei petale sunt mai întalnite.

Cu 5 petale sunt sute de specii,și sălbatice,și cultivate.

Nu foarte întâlnite sunt florile cu 8 petale dar există destule specii bine cunoscute.
 

Cu 13, 21 și 34 de petale avem destule flori.

Proporția divină în viața noastră

Putem spune că viața a fost proiectată cu ajutorul “riglei de aur”, pe care o putem ușor construi astfel :

Apoi repetăm același procedeu :

Combinăm segmentele să creem o riglă pentru măsurători,”rigla de aur”:

Iată câteva exemple:

Corpul uman

Sectiunea de aur în arta

Egiptenii din antichitate au fost primii care au folosit matematica în artă. Este sigur faptul că ei au descris proprietăți magice ale numărului de aur (proporția divina) și l-au folosit în construcția piramidelor.
 

Piramidele,Platoul Gizeh

Dac facem o secțiune în Marea Piramidă ca în figură,obținem un triunghi dreptunghic,așa numitul triunghi egiptean.

Pitagora (560-480 BC), geometrul grec,a fost în special interesat de raportul de aur și a demonstrat că stă la baza proporțiilor înfățișării umane.El a arătat că fiecare parte a corpului uman este în proportie de aur cu toate celelalte parti.
 

Pitagora la Scoala din Atena,de Rafael

Descoperirile lui Pitagora asupra proporțiilor figurii umane au avut un mare efect asupra artei în Grecia.Fiecare parte a marilor lor construcții,până la cel mai mic detaliu de decor,a fost construită ținând cont de acest raport.

Acropolele,Atena

Pantenonul a fost poate cel mai bun exemplu de contribuție a matematicii în artă.
 

Pantenonul, Acropolele, Atena

Vechiul templu se încadrează aproape perfect într-un dreptunghi de aur.

Subdiviziuni ale dreptunghiului încadrează perfect caracteristicile arhitecturale ale structurii.

Leonardo da Vinci (1451-1519) afișat pentru mult timp un interes arzător pentru matematica în artă si natură.

Ca și Pitagora,el a facut un studiu amănunțit al figurii umane și a arătat cum toate părțile sale sunt legate între ele de raportul de aur.

Lucrarea neterminată a lui Leonardo,Sfântul Gerome,îl înfățișează pe acesta cu un leu așezat la picioarele sale.

Un dreptunghi de aur încadrează atât de bine figura centarală încât adesea se spune că artiștii în mod intenționat pictau conformându-se acestor proporții.Cunoscând dragostea lui Leonardo pentru geometrie este foarte posibil să fi fost așa.

Dreptunghiurile de aur din Mona Lisa lui Da Vinci abundă.

Artiștii Renașterii,precum Michelangelo,

(1475-1564) și Rafael (1483-1530) iși

construiau operele pe baza secțiunii de aur.

David,Michelangelo

BIBLIOGRAFIE

[1] M. N. Vorobiev – Numerele lui Fibonacci, Editura tehnică, București,

1953

[2] Dan și Rodica Brânzei – Șiruri recurente în liceu, Editura Gil, Zalău, 1995

[3] Marcel Țena – Cinci teme de aritmetica superioară,Biblioteca

Societății de Științe Matematice,București,1991

[4] Laurențiu Panaitopol

și Alexandru Gica – O introducere în aritmetică și teoria numerelor,

editura Universității,București, 2001

[5] W. Sierpinski – Elementary Theory of Numbers, Warszawa, 1987

[6] Gazeta Matematică – O problemă de geometrie elementară în care apare

numărul de aur, de Ion Chițescu, articol din nr. 9/1995

[7] Gazeta Matematică – Suma pătratelor numerelor Fibonacci, de Alfred

Brousseau, articol din nr.10-11/1997

[8] Eric W. Weisstein – Fibonacci Numbers , MathWorld

http://mathworld.wolfram.com/FibonacciNumber.html

[9] Eric W. Weisstein – Lucas Sequence ,MathWorld

http://mathworld.wolfram.com/LucasSequence.html

[10] www.mcs.surrey.ac.uk

[11] www.evolutionoftruth.com