Relație de recurență

În matematică, se spune că un șir ${\displaystyle (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:

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

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

${\displaystyle 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:

${\displaystyle a_{n}=\lambda _{1}a_{n-1}+\lambda _{2}a_{n-2}+\cdots +\lambda _{k}a_{n-k}.}$

${\displaystyle (1)}$

Acesteia îi corespunde ecuația caracteristică:

${\displaystyle x^{k}-\lambda _{1}x^{k-1}-\lambda _{2}x^{k-2}-\cdots -\lambda _{k}=0.}$

${\displaystyle (2)}$

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

Teorema 2. Dacă șirurile ${\displaystyle (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 ${\displaystyle (a)_{n\in \mathbb {N} }}$ se exprimă ca o combinație liniară a șirurilor ${\displaystyle (a^{(1)})_{n\in \mathbb {N} },(a^{(2)})_{n\in \mathbb {N} },\cdots ,(a^{(k)})_{n\in \mathbb {N} }}$ adică există ${\displaystyle p_{1},p_{2},\cdots ,p_{k}\in \mathbb {R} }$ astfel încât:

${\displaystyle a_{n}=p_{1}a_{n}^{(1)}+p_{2}a_{n}^{(2)}+\cdots +p_{k}a_{n}^{(k)},\;\forall n\in \mathbb {N} .}$

${\displaystyle (3)}$

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

• Dacă ecuația caracteristică are soluții reale distincte ${\displaystyle t_{1},t_{2},\cdots ,t_{k},}$ șirurile sunt:

${\displaystyle 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}\;}$

${\displaystyle (4)}$

• Dacă ecuația caracteristică are soluții reale multiple: ${\displaystyle t_{1}}$ cu ordinul de multiplicitate ${\displaystyle l_{1},}$ ${\displaystyle t_{2}}$ cu ordinul de multiplicitate ${\displaystyle l_{2},\cdots ,}$ ${\displaystyle t_{m}}$ cu ordinul de multiplicitate ${\displaystyle l_{m},}$ unde ${\displaystyle l_{1}+l_{2}+\cdots +l_{m}=k,}$ șirurile sunt:

	${\displaystyle 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}}$	${\displaystyle (5)}$
	${\displaystyle 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}}$
	${\displaystyle \cdots \ \cdots \ \cdots \cdots \cdots \ \cdots \ \cdots }$
	${\displaystyle 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:

${\displaystyle F_{0}=0,F_{1}=1,F_{i}=F_{i-1}+F_{i-2}{\mbox{ pentru }}i\geq 2{\mbox{.}}\,}$