Vizualizare sursă pentru „Relație de recurență”

În [[matematică]], se spune că un [[șir (matematică)|șir]] <math> (a_n)_{n \in \mathbb N} </math> este definit printr-o '''relație de recurență''' dacă fiecare termen al acestuia poate fi scris ca o [[funcție (matematică)|funcție]] de termenii anteriori:
::<math> a_n = f (n, a_{n-1}, a_{n-2}, \cdots, a_{n-k}). </math> <!-- de ce nu ", a_{n-k}, \cdots )" ? -->

Un exemplu de relație de recurență este:
::<math>x_{n+1} = r x_n (1 - x_n). \,</math>

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

{|
| width="100" |
| width="500" |
<math> a_n = \lambda_1 a_{n-1} + \lambda_2 a_{n-2} + \cdots + \lambda_k a_{n-k}. </math>
| <math> (1) </math>
|}

Acesteia îi corespunde ecuația caracteristică:

{|
| width="100" |
| width="500" |
<math> x^k - \lambda_{1} x^{k-1} - \lambda_{2} x^{k-2} - \cdots - \lambda_k=0 . </math>
| <math> (2) </math>
|}

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

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

{|
| width="100" |
| width="500" |
<math> a_n = p_1 a_n^{(1)} + p_2 a_n^{(2)} +  \cdots + p_k a_n^{(k)}, \; \forall n \in \mathbb N.  </math>
| <math> (3) </math>
|}

''Teorema 3''.
Există ''k'' șiruri liniar independente ce verifică relația de recurență.
* Dacă ecuația caracteristică are soluții reale distincte <math>t_1, t_2, \cdots , t_k,  </math> șirurile sunt:

{|
| width="100" |
| width="500" |
<math> 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 \;  </math>
| <math> (4) </math>
|}

* Dacă ecuația caracteristică are soluții reale multiple: <math> t_1 </math> cu ordinul de [[multiplicitate]] <math> l_1, </math> <math> t_2 </math> cu ordinul de multiplicitate <math> l_2, \cdots ,  </math> <math> t_m </math> cu ordinul de multiplicitate <math> l_m, </math> unde <math> l_1 + l_2 + \cdots + l_m = k, </math> șirurile sunt:

{|
| width="100" rowspan="4" |
| width="500" | <math> 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</math>
| rowspan="4" | <math>(5)</math>
|-
| <math> 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</math>
|-
| <math>\cdots \ \cdots \ \cdots \cdots \cdots \ \cdots \ \cdots </math>
|-
| <math> 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</math>
|}
<!-- TODO: explicarea determinarii constantelor u_0^(...) in functie de conditiile initiale, a_0, a_1, ..., a_(k-1) -->

<!-- TODO: dar daca ecuatia caracteristica are solutii complexe... ( e.g., x_n = - x_{n-2} ) ? -->

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:
:<math>F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2} \mbox{ pentru }i \ge 2\mbox{.} \, </math>

{{Control de autoritate}}
[[Categorie:Matematică]]