p=. !probleme-de-acoperire?P62.jpg!

* Putem observa uşor că <tex> $A[2n + 2] = 3A[2n] + 2B[2n - 2]$ </tex>, iar <tex> $B[2n] = A[2n] + B[2n – 2]$ </tex>. Aceste două recurenţe ar fi fost de ajuns pentru a rezolva problema în concurs. În cartea [3] rezolvarea continuă pentru a determina un număr explicit: <tex> $A[2n + 2] = 3 A[2n] + 2A[2n – 2] + 2B[2n – 4]$ </tex> (am înlocuit pe <tex> $B[2n – 2]$ </tex>). Mai departe obţinem <tex> $A[2n + 2] = 4 A[2n] – A[2n – 2]$ </tex>. Putem uşor afla că <tex> $A[2] = 3$ </tex> şi <tex> $A[4] = 11$ </tex>. Ecuaţia caracteristică a ecuaţiei liniare este $x^2^ – 4x + 1 = 0$, iar de aici obţinem că <tex> $A[2n] = 1/{2\sqrt{3}} * ((\sqrt{3} + 1) * (2 + \sqrt{3}){^n^} + (\sqrt{3} - 1) * (2 - \sqrt{3}){^n^})$ </tex>. (metoda rezolvării recurenţelor liniare este prezentată în manualul de clasa a 11-a de matematică). Un astfel de răspuns nu ne prea ajută pe noi ca programatori pentru că ar trebui să putem efectua operaţii cu numere reale cu o precizie destul de mare pentru a ajunge la rezultatul dorit. Totuşi, faptul că am găsit o recurenţa lineară ne ajută să determinăm mult mai repede numărul de posibilităţi folosindu-ne de următorul raţionament:

* Putem observa uşor că <tex> $A[2n + 2] = 3A[2n] + 2B[2n – 2]$ </tex>, iar <tex> $B[2n] = A[2n] + B[2n – 2]$ </tex>. Aceste două recurenţe ar fi fost de ajuns pentru a rezolva problema în concurs. În cartea [3] rezolvarea continuă pentru a determina un număr explicit: <tex> $A[2n + 2] = 3 A[2n] + 2A[2n – 2] + 2B[2n – 4]$ </tex> (am înlocuit pe <tex> $B[2n – 2]$ </tex>). Mai departe obţinem <tex> $A[2n + 2] = 4 A[2n] – A[2n – 2]$ </tex>. Putem uşor afla că <tex> $A[2] = 3$ </tex> şi <tex> $A[4] = 11$ </tex>. Ecuaţia caracteristică a ecuaţiei liniare este $x^2^ – 4x + 1 = 0$, iar de aici obţinem că <tex> $A[2n] = 1/{2\sqrt{3}} * ((\sqrt{3} + 1) * (2 + \sqrt{3}){^n^} + (\sqrt{3} - 1) * (2 - \sqrt{3}){^n^})$ </tex>. (metoda rezolvării recurenţelor liniare este prezentată în manualul de clasa a 11-a de matematică). Un astfel de răspuns nu ne prea ajută pe noi ca programatori pentru că ar trebui să putem efectua operaţii cu numere reale cu o precizie destul de mare pentru a ajunge la rezultatul dorit. Totuşi, faptul că am găsit o recurenţa lineară ne ajută să determinăm mult mai repede numărul de posibilităţi folosindu-ne de următorul raţionament:

* Dacă avem o recurenţa <tex> $X[n] = aX[n-1] + bX[n-2]$ </tex> atunci avem că: