În matematică , se spune că un șir
(
a
n
)
n
∈
N
{\displaystyle (a_{n})_{n\in \mathbb {N} }}
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
,
⋯
,
a
n
−
k
)
.
{\displaystyle 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
)
.
{\displaystyle x_{n+1}=rx_{n}(1-x_{n}).\,}
Un caz particular îl constituie șirurile ce pot fi definite printr-o recurență liniară finită, care este de forma:
a
n
=
λ
1
a
n
−
1
+
λ
2
a
n
−
2
+
⋯
+
λ
k
a
n
−
k
.
{\displaystyle a_{n}=\lambda _{1}a_{n-1}+\lambda _{2}a_{n-2}+\cdots +\lambda _{k}a_{n-k}.}
(
1
)
{\displaystyle (1)}
Acesteia îi corespunde ecuația caracteristică:
x
k
−
λ
1
x
k
−
1
−
λ
2
x
k
−
2
−
⋯
−
λ
k
=
0.
{\displaystyle x^{k}-\lambda _{1}x^{k-1}-\lambda _{2}x^{k-2}-\cdots -\lambda _{k}=0.}
(
2
)
{\displaystyle (2)}
Teorema 1 .
Dacă
t
∈
R
{\displaystyle t\in \mathbb {R} }
(
2
)
{\displaystyle (2)}
(
a
n
)
n
∈
N
,
a
n
=
a
0
⋅
t
n
{\displaystyle (a_{n})_{n\in \mathbb {N} },\,a_{n}=a_{0}\cdot t^{n}}
(
1
)
.
{\displaystyle (1).}
Teorema 2 .
Dacă șirurile
(
a
n
(
1
)
)
n
∈
N
,
(
a
n
(
2
)
)
n
∈
N
,
⋯
,
(
a
n
(
k
)
)
n
∈
N
{\displaystyle (a_{n}^{(1)})_{n\in \mathbb {N} },(a_{n}^{(2)})_{n\in \mathbb {N} },\cdots ,(a_{n}^{(k)})_{n\in \mathbb {N} }}
liniar independente , atunci orice soluție
(
a
)
n
∈
N
{\displaystyle (a)_{n\in \mathbb {N} }}
(
a
(
1
)
)
n
∈
N
,
(
a
(
2
)
)
n
∈
N
,
⋯
,
(
a
(
k
)
)
n
∈
N
{\displaystyle (a^{(1)})_{n\in \mathbb {N} },(a^{(2)})_{n\in \mathbb {N} },\cdots ,(a^{(k)})_{n\in \mathbb {N} }}
p
1
,
p
2
,
⋯
,
p
k
∈
R
{\displaystyle p_{1},p_{2},\cdots ,p_{k}\in \mathbb {R} }
a
n
=
p
1
a
n
(
1
)
+
p
2
a
n
(
2
)
+
⋯
+
p
k
a
n
(
k
)
,
∀
n
∈
N
.
{\displaystyle a_{n}=p_{1}a_{n}^{(1)}+p_{2}a_{n}^{(2)}+\cdots +p_{k}a_{n}^{(k)},\;\forall n\in \mathbb {N} .}
(
3
)
{\displaystyle (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
,
⋯
,
t
k
,
{\displaystyle t_{1},t_{2},\cdots ,t_{k},}
u
n
(
1
)
=
a
0
⋅
t
1
n
,
u
n
(
2
)
=
a
0
⋅
t
2
n
,
⋯
,
u
n
(
k
)
=
a
0
⋅
t
k
n
{\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}\;}
(
4
)
{\displaystyle (4)}
Dacă ecuația caracteristică are soluții reale multiple:
t
1
{\displaystyle t_{1}}
multiplicitate
l
1
,
{\displaystyle l_{1},}
t
2
{\displaystyle t_{2}}
l
2
,
⋯
,
{\displaystyle l_{2},\cdots ,}
t
m
{\displaystyle t_{m}}
l
m
,
{\displaystyle l_{m},}
l
1
+
l
2
+
⋯
+
l
m
=
k
,
{\displaystyle l_{1}+l_{2}+\cdots +l_{m}=k,}
u
n
(
1
,
1
)
=
u
0
(
1
,
1
)
⋅
t
1
n
,
u
n
(
1
,
2
)
=
u
0
(
1
,
2
)
⋅
n
⋅
t
1
n
,
⋯
,
u
n
(
1
,
l
1
)
=
u
0
(
1
,
l
1
)
⋅
n
l
1
−
1
⋅
t
1
n
{\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}}
(
5
)
{\displaystyle (5)}
u
n
(
2
,
1
)
=
u
0
(
2
,
1
)
⋅
t
2
n
,
u
n
(
2
,
2
)
=
u
0
(
2
,
2
)
⋅
n
⋅
t
2
n
,
⋯
,
u
n
(
2
,
l
2
)
=
u
0
(
2
,
l
2
)
⋅
n
l
2
−
1
⋅
t
2
n
{\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 }
u
n
(
m
,
1
)
=
u
0
(
m
,
1
)
⋅
t
m
n
,
u
n
(
m
,
2
)
=
u
0
(
m
,
2
)
⋅
n
⋅
t
m
n
,
⋯
,
u
n
(
m
,
l
m
)
=
u
0
(
m
,
l
m
)
⋅
n
l
m
−
1
⋅
t
m
n
{\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}}
Ș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
pentru
i
≥
2
.
{\displaystyle F_{0}=0,F_{1}=1,F_{i}=F_{i-1}+F_{i-2}{\mbox{ pentru }}i\geq 2{\mbox{.}}\,}
