Relație de recurență

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În matematică, se spune că un șir  (a_n)_{n \in \mathbb N} este definit printr-o relație de recurență dacă fiecare termen al acestuia poate fi scris ca o funcție de termenii anteriori:

 a_n = f (n, a_{n-1}, a_{n-2}, \cdots, a_{n-k}).

Un exemplu de relație de recurență este:

x_{n+1} = r x_n (1 - x_n). \,

Relația de recurență liniară[modificare | modificare sursă]

Un caz particular îl constituie șirurile ce pot fi definite printr-o recurență liniară finită, care este de forma:

 a_n = \lambda_1 a_{n-1} + \lambda_2 a_{n-2} + \cdots + \lambda_k a_{n-k}.

 (1)

Acesteia îi corespunde ecuația caracteristică:

 x^k - \lambda_{1} x^{k-1} - \lambda_{2} x^{k-2} - \cdots - \lambda_k=0 .

 (2)

Teorema 1. Dacă  t \in \mathbb R este o soluție a ecuației caracteristice  (2) , atunci șirul  (a_n)_{n \in \mathbb N} , \, a_n = a_0 \cdot t^n verifică relația de recurență  (1).

Teorema 2. Dacă șirurile  (a^{(1)}_n)_{n \in \mathbb N}, (a^{(2)}_n)_{n \in \mathbb N}, \cdots ,  (a^{(k)}_n)_{n \in \mathbb N}  îndeplinesc condiția de recurență și sunt liniar independente, atunci orice soluție  (a)_{n \in \mathbb N} se exprimă ca o combinație liniară a șirurilor  (a^{(1)})_{n \in \mathbb N}, (a^{(2)})_{n \in \mathbb N}, \cdots ,  (a^{(k)})_{n \in \mathbb N}  adică există  p_1, p_2, \cdots, p_k \in \mathbb R astfel încât:

 a_n = p_1 a_n^{(1)} + p_2 a_n^{(2)} +  \cdots + p_k a_n^{(k)}, \; \forall n \in \mathbb N.

 (3)

Teorema 3. Există k șiruri liniar independente ce verifică relația de recurență.

  • Dacă ecuația caracteristică are soluții reale distincte t_1, t_2, \cdots , t_k,  șirurile sunt:

 u_n^{(1)}= a_0 \cdot t_1^n, \; u_n^{(2)} = a_0 \cdot t_2^n, \; \cdots , u_n^{(k)} = a_0 \cdot t_k^n \;

 (4)
  • Dacă ecuația caracteristică are soluții reale multiple:  t_1 cu ordinul de multiplicitate  l_1,  t_2 cu ordinul de multiplicitate  l_2, \cdots ,   t_m cu ordinul de multiplicitate  l_m, unde  l_1 + l_2 + \cdots + l_m = k, șirurile sunt:
 u_n^{(1,1)} = u_0^{(1,1)} \cdot t_1^n, \; u_n^{(1,2)} = u_0^{(1,2)} \cdot n \cdot t_1^n, \; \cdots , u_n^{(1,l_1)} = u_0^{(1,l_1)} \cdot n^{l_1 -1} \cdot t_1^n (5)
 u_n^{(2,1)} = u_0^{(2,1)} \cdot t_2^n, \; u_n^{(2,2)} = u_0^{(2,2)} \cdot n \cdot t_2^n, \; \cdots , u_n^{(2,l_2)} = u_0^{(2,l_2)} \cdot n^{l_2 -1} \cdot t_2^n
\cdots \ \cdots \ \cdots \cdots \cdots \ \cdots \ \cdots
 u_n^{(m,1)} = u_0^{(m,1)} \cdot t_m^n, \; u_n^{(m,2)} = u_0^{(m,2)} \cdot n \cdot t_m^n, \; \cdots , u_n^{(m,l_m)} = u_0^{(m,l_m)} \cdot n^{l_m -1} \cdot t_m^n


Una dintre cele mai simple relații de recurență liniară definește „Șirul lui Fibonacci”, în care fiecare termen este egal cu suma celor doi termeni precedenți:

F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2} \mbox{ pentru }i \ge 2\mbox{.} \,