Șirul $$(x_n)$$ verifică $$x_{n+1} = 4x_n + 3$$, cu $$x_1 = 1$$. Termenul lui general este:

$$x_n = 2 \cdot 4^{\,n-1} - 1$$

Cum calculez puterile unei matrice cu recurențe?

Lecția pe scurt · clasa a XI-a · Puterile unei matrice prin șiruri recurente

Presupui că $A^{n}$ păstrează forma matricei de pornire, cu elemente notate prin șiruri, apoi înmulțești cu $A$ și citești legăturile dintre pasul $n$ și pasul $n + 1$ . Ies una sau două recurențe simple, care se rezolvă cu formula progresiei. Pentru $A = (2011)$ apar $a_{n + 1} = 2 a_{n}$ și $b_{n + 1} = 2 b_{n} + 1$ , deci $a_{n} = 2^{n}$ și $b_{n} = 2^{n} - 1$ .

A treia metodă nu cere nici să ghicești formula, nici o descompunere norocoasă. Ideea: nu cauți direct matricea $A^{n}$ , ci urmărești cum se schimbă fiecare element de la un pas la altul. Scrii $A^{n} = (a_{n} c_{n} b_{n} d_{n})$ , unde cele patru simboluri sunt șiruri, calculezi produsul $A \cdot A^{n}$ și identifici elementele cu cele ale lui $A^{n + 1}$ . Obții patru relații de recurență, iar valorile de pornire se citesc din $A$ însăși, pentru că $A^{1} = A$ — aceasta este greșeala cea mai frecventă și cea mai ușor de evitat. Rezolvi apoi în ordinea în care șirurile devin cunoscute, începând cu cele care nu depind de celelalte.

Apar doar patru tipare, toate știute din clasa a IX-a. Geometric, $x_{n + 1} = q x_{n}$ , cu $x_{n} = x_{1} q^{n - 1}$ . Cu adaos variabil, $x_{n + 1} = x_{n} + t_{n}$ , rezolvat prin adunarea relațiilor, când termenii intermediari se reduc. Afin, $x_{n + 1} = q x_{n} + c$ cu $q \neq = 1$ , rezolvat prin punctul fix $ℓ = \frac{c}{1 - q}$ : șirul $x_{n} - ℓ$ devine geometric de rație $q$ . Și sistemul cuplat, decuplat prin sumă și diferență, care dau două șiruri geometrice independente.

Metoda funcționează și acolo unde binomul nu se aplică, adică la matricele cu diagonala neconstantă. Uneori recurența este răspunsul, ca la matricea lui Fibonacci. Verifică de fiecare dată pe $n = 1$ și $n = 2$ .

De reținut

Scrii $A^{n}$ cu elemente-șiruri, apoi identifici din $A^{n + 1} = A^{n} \cdot A$
$x_{n + 1} = q x_{n} \Rightarrow x_{n} = x_{1} q^{n - 1}$
$x_{n + 1} = q x_{n} + c$ : treci la $y_{n} = x_{n} - ℓ$ , cu $ℓ = \frac{c}{1 - q}$

Greșeala tipică

Se scriu recurențele corect, dar valorile de pornire se iau de la $n = 0$ când formula a fost dedusă pentru $n = 1$ . Rezultatul iese decalat cu un pas, iar verificarea pe $A^{2}$ îl arată imediat.

Exerciții din această mini-lecție

Se consideră $A = (5011)$ și se notează $A^{n} = (a_{n} c_{n} b_{n} d_{n})$ . Știind că $c_{n} = 0$ și $d_{n} = 1$ pentru orice $n$ , șirul $(b_{n})$ verifică recurența:
- a) $b_{n + 1} = 5 b_{n}$
- b) $b_{n + 1} = b_{n} + 5^{n}$
- c) $b_{n + 1} = 5 b_{n} + 1$
- d) $b_{n + 1} = b_{n} + 1$
Vezi răspunsul

Răspuns corect: c) $b_{n + 1} = 5 b_{n} + 1$

Calculăm produsul: $A \cdot A^{n} = (5 a_{n} + c_{n} c_{n} 5 b_{n} + d_{n} d_{n})$ . Identificând cu $A^{n + 1}$ , obținem $b_{n + 1} = 5 b_{n} + d_{n} = 5 b_{n} + 1$ — o recurență afină, nu una geometrică. Cu $b_{1} = 1$ și punctul fix $ℓ = - \frac{1}{4}$ rezultă $b_{n} = \frac{5 ^{n} - 1}{4}$ .
Șirul $(x_{n})$ verifică $x_{n + 1} = 4 x_{n} + 3$ , cu $x_{1} = 1$ . Termenul lui general este:
- a) $x_{n} = 4^{n - 1}$
- b) $x_{n} = 4^{n - 1} + 3 (n - 1)$
- c) $x_{n} = 4^{n} - 3$
- d) $x_{n} = 2 \cdot 4^{n - 1} - 1$
Vezi răspunsul

Răspuns corect: d) $x_{n} = 2 \cdot 4^{n - 1} - 1$

Recurența este afină, deci căutăm punctul fix: $ℓ = 4 ℓ + 3$ dă $ℓ = - 1$ . Scăzând, $x_{n + 1} + 1 = 4 (x_{n} + 1)$ , adică șirul $x_{n} + 1$ este geometric de rație $4$ , cu primul termen $2$ . Rezultă $x_{n} + 1 = 2 \cdot 4^{n - 1}$ . Control: $x_{2} = 4 \cdot 1 + 3 = 7$ , iar formula dă $8 - 1 = 7$ .
Se consideră $A = (4114)$ , pentru care $A^{n} = (a_{n} b_{n} b_{n} a_{n})$ . Șirul $s_{n} = a_{n} + b_{n}$ verifică:
- a) $s_{n} = 5^{n}$
- b) $s_{n} = 5 n$
- c) $s_{n} = 3^{n}$
- d) $s_{n} = 4^{n} + 1$
Vezi răspunsul

Răspuns corect: a) $s_{n} = 5^{n}$

Sistemul de recurențe este $a_{n + 1} = 4 a_{n} + b_{n}$ și $b_{n + 1} = a_{n} + 4 b_{n}$ . Adunându-le, $s_{n + 1} = 5 s_{n}$ : suma este un șir geometric de rație $5$ , iar $s_{1} = 4 + 1 = 5$ , deci $s_{n} = 5^{n}$ . (Diferența dă $p_{n + 1} = 3 p_{n}$ , cu $p_{1} = 3$ , deci $p_{n} = 3^{n}$ .)

Întrebări conexe

Cum leg elementele puterii următoare de cele ale puterii curente?

Faci produsul $A^{n} \cdot A$ cu elementele scrise ca șiruri și identifici pozițiile. Fiecare poziție din rezultat dă o egalitate între termenul de rang $n + 1$ și termenii de rang $n$ , adică exact recurențele căutate.

Ce șir obțin dacă un element rămâne constant la fiecare pas?

Un șir constant, deci acea poziție păstrează valoarea din matricea de pornire pentru orice exponent. Situația apare des la colțul de jos al matricelor triunghiulare, unde înmulțirea aduce doar zerouri peste valoarea existentă.

Ce legătură au puterile matricei lui Fibonacci cu șirul lui?

Pentru $A = (1110)$ , puterea $A^{n}$ are pe poziții exact termenii $F_{n + 1}$ , $F_{n}$ și $F_{n - 1}$ . Recurența citită din produs este chiar regula șirului, iar de aici ies identități greu de obținut altfel.

Ce fac dacă recurența are termenul liber zero?

Atunci șirul este direct geometric: din $x_{n + 1} = q x_{n}$ iese $x_{n} = x_{1} q^{n - 1}$ , fără nicio schimbare de variabilă. Este cazul cel mai comod și apare ori de câte ori matricea are zerouri așezate potrivit.

Cum verific formula obținută pentru puterile mici?

Pui $n = 1$ și $n = 2$ în expresiile găsite și le compari cu $A$ și cu $A^{2}$ calculate direct. Nepotrivirea la $n = 1$ arată de obicei că valorile de pornire ale șirurilor au fost luate greșit.

Pentru ce matrice se potrivește metoda recurențelor?

Pentru cele la care forma puterilor se păstrează, adică triunghiulare, diagonale sau cu multe zerouri fixe. Când puterile amestecă toate pozițiile, recurențele se leagă între ele și devine mai comodă ecuația Hamilton-Cayley.

Oamenii mai întreabă și: puterea unei matrice prin recurență · șiruri recurente pentru A la puterea n · cum găsesc formula puterii cu recurențe · recurență liniară la puterile matricelor