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}=rx_{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 \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_{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 \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\geq 2{\mbox{.}}\,$