Relație de recurență

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

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 ℝ$ 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_n^{(1)}{)}_{n\in \mathbb{N}},(a_n^{(2)}{)}_{n\in \mathbb{N}},\cdots ,(a_n^{(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 ℝ$ astfel încât:

$a_n=p_1{a}_n^{(1)}+p_2{a}_n^{(2)}+\cdots +p_k{a}_n^{(k)},\mathrm{\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}\text{ pentru }i\ge 2\text{.}$