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ă:

\emph{}
\[ \left( \begin{array}{ccc}
a & b \\

1 & 0 \end{array} \right)\]
 
x

1 & 0 \end{array} \right)\]

\emph{}
\[ \left( \begin{array}{ccc}
X[n - 1] \\

X[n - 2] \end{array} \right)\]
</tex>

X[n - 2] \end{array} \right)\]  </tex>
 
<tex> = </tex>
 
<tex>
\emph{}
\[ \left( \begin{array}{ccc}
X[n] \\
X[n - 1] \end{array} \right)\]  </tex>
 
<tex> \Leftrightarrow </tex>
 
<tex>
\emph{}
\[ \left( \begin{array}{ccc}
a & b \\
1 & 0 \end{array} \right)\]^{(n-1)}
 
\emph{}
\[ \left( \begin{array}{ccc}
X[1] \\
X[0] \end{array} \right)\]
 
=
 
\emph{}
\[ \left( \begin{array}{ccc}
X[n] \\
X[n - 1] \end{array} \right)\]  </tex>

Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> $X[n]$ </tex> mult mai repede.