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ă, 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} , \, x_n = t^n verifică relația de recurență  (1).

Teorema 2. Dacă șirurile  (a^{(1)})_{n \in \mathbb N}, (a^{(2)})_{n \in \mathbb N}, \cdots ,  (a_{(k)})^{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 u_n^{(1)} + p_2 u_n^{(2)} +  \cdots + p_k u_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)}= t_1^n, \; u_n^{(2)} = t_2^n, \; \cdots , u_n^{(k)} = 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)} = t_1^n, \; u_n^{(1,2)} = n \cdot t_1^n, \; \cdots , u_n^{(1,l_1)} =n^{l_1 -1} \cdot t_1^n (5)
 u_n^{(2,1)} = t_2^n, \; u_n^{(2,2)} = n \cdot t_2^n, \; \cdots , u_n^{(2,l_1)} =n^{l_1 -1} \cdot t_2^n
\cdots \cdots \cdots\cdots \cdots \cdots\cdots \cdots \cdots
 u_n^{(m,1)} = t_m^n, \; u_n^{(m,2)} = n \cdot t_m^n, \; \cdots , u_n^{(m,l_1)} =n^{l_1 -1} \cdot t_m^n


Una dintre cele mai simple relațiii 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{.} \,