Șirul lui Fibonacci

Șirul lui Fibonacci pornește de la $F_0=0$, $F_1=1$ și respectă regula $F_{n+2}=F_{n+1}+F_n$, pentru $n\ge 0$. Fiecare termen nou este suma celor doi precedenți. Primii termeni sunt $0;1;1;2;3;5;8;13;21;34;55;89;144;\dots$ Șirul nu este nici progresie aritmetică, nici geometrică: diferențele $1;0;1;1;2;3;\dots$ și rapoartele $1;2;\frac{3}{2};\frac{5}{3};\dots$ nu sunt constante. Raportul a doi termeni vecini se apropie de numărul de aur $\phi =\frac{1+\sqrt{5}}{2}\approx 1,618$, folosit în proporțiile construcțiilor.

Exemplu rezolvat. Aflăm $F_6$.

1. $F_2=1$, $F_3=2$.
2. $F_4=3$, $F_5=5$.
3. $F_6=F_5+F_4=5+3=8$.

Suma termenilor este $F_0+\cdots +F_n=F_{n+2}-1$. Demonstrația prin inducție are două etape. Pentru $n=0$, ambii membri sunt $0$. Presupunând egalitatea pentru $n$, adăugăm $F_{n+1}$ și obținem $F_{n+2}-1+F_{n+1}=F_{n+3}-1$, adică formula pentru indicele următor.

Suma pătratelor este $F_1^2+\cdots +F_n^2=F_n{F}_{n+1}$. Pentru $n=1$ avem $1=1\cdot 1$. Dacă egalitatea e adevărată pentru $n$, adăugând $F_{n+1}^2$ obținem $F_{n+1}(F_n+F_{n+1})=F_{n+1}{F}_{n+2}$. Geometric, pătratele cu laturile $F_1;F_2;\dots ;F_n$ acoperă un dreptunghi cu laturile $F_n$ și $F_{n+1}$; la $n=5$, aria este $5\cdot 8=40=1+1+4+9+25$.

Identitatea lui Cassini este $F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$, pentru $n\ge 1$. Notăm $c_n=F_{n-1}{F}_{n+1}-F_n^2$. Din recurență, $c_{n+1}=F_n(F_{n+1}+F_n)-F_{n+1}^2=F_n^2-F_{n+1}(F_{n+1}-F_n)=F_n^2-F_{n+1}{F}_{n-1}=-c_n$. Cum $c_1=F_0{F}_2-F_1^2=-1$, semnul alternează: $c_n=(-1{)}^n$.

Raporturile $r_n=F_{n+1}/F_n$, pentru $n\ge 1$, satisfac $r_{n+1}=1+1/r_n$, iar valorile lor $1;2;1,5;1,67;1,6;1,625;\dots$ converg. Limita $\ell >0$ verifică $\ell =1+1/\ell$, adică ${\ell }^2=\ell +1$, deci $\ell =\phi =\frac{1+\sqrt{5}}{2}$. Într-un dreptunghi de aur, raportul laturii mari la cea mică este $\phi$. Un astfel de dreptunghi cu laturile $\phi$ și $1$, din care se taie un pătrat de latură $1$, lasă un dreptunghi cu laturile $1$ și $\phi -1$, iar $\frac{1}{\phi -1}=\phi$, fiindcă $\phi (\phi -1)={\phi }^2-\phi =1$: dreptunghiul rămas este asemenea celui inițial. Pentru o latură mică de $5$ m, latura mare a unui dreptunghi de aur are $5\phi \approx 8,09$ m; un proiectant poate folosi aproximația dată de numerele Fibonacci vecine, $8/5=1,6$, adică o latură mare de $8$ m.

Exemplu rezolvat. Numărăm modurile de a urca o scară de $5$ trepte folosind pași de $1$ sau $2$ trepte.

1. Notăm cu $u_n$ numărul modurilor pentru o scară cu $n$ trepte, cu $u_0=1$ și $u_1=1$.
2. Ultimul pas vine de la treapta precedentă sau de la cea situată cu două mai jos, deci $u_n=u_{n-1}+u_{n-2}$.
3. Calculăm $u_2=2$, $u_3=3$, $u_4=5$ și $u_5=8$.
4. Există $u_5=8$ moduri, iar relația dintre șiruri este $u_n=F_{n+1}$.

Exemplu rezolvat. La începutul lunii $1$ există un cuplu de iepuri nou-născuți. Începând din a doua lună de viață, un cuplu aduce pe lume un cuplu nou la sfârșitul fiecărei luni, iar niciun iepure nu moare. Câte cupluri sunt la începutul lunii $12$?

1. Fie $c_n$ numărul cuplurilor de la începutul lunii $n$. Avem $c_1=1$ și $c_2=1$, deoarece primul cuplu nu a născut încă.
2. La începutul lunii $n+2$ există cele $c_{n+1}$ cupluri din luna precedentă și cuplurile nou-născute, câte unul pentru fiecare cuplu fertil în luna $n+1$, adică pentru cele $c_n$ cupluri existente încă de la începutul lunii $n$. Deci $c_{n+2}=c_{n+1}+c_n$.
3. Rezultă $c_n=F_n$ și $c_{12}=F_{12}=144$.

Exemplu rezolvat. Arătăm că $F_n$ este par dacă și numai dacă $n$ este multiplu de $3$.

1. Parități: $F_0=0$ par, $F_1=1$ impar, $F_2=1$ impar, $F_3=2$ par, $F_4=3$ impar.
2. Perechea de parități $(F_3;F_4)$ este (par; impar), ca $(F_0;F_1)$. Fiecare termen depinde numai de cei doi precedenți, deci paritățile se repetă din trei în trei: par, impar, impar.
3. Termenii pari sunt cei de indice $0;3;6;9;\dots$, de exemplu $F_6=8$ și $F_9=34$.

Greșeli frecvente

• Greșit: după termenii $5$ și $8$ urmează $10$.
  Corect: recurența cere suma lor, deci $5+8=13$.
• Greșit: pentru scara cu $5$ trepte răspunsul este $F_5=5$.
  Corect: condițiile inițiale dau $u_5=F_6=8$.
• Greșit: $F_{10}$ este al zecelea număr scris, deci $F_{10}=34$.
  Corect: șirul începe cu $F_0=0$; al zecelea număr scris este $F_9=34$, iar $F_{10}=55$.
• Greșit: raporturile $F_{n+1}/F_n$ sunt egale, deci șirul este progresie geometrică.
  Corect: ele sunt $1;2;\frac{3}{2};\frac{5}{3};\dots$, adică diferă și se apropie de $\phi$.

Înainte și după