Relações de recorrência lineares com coeficientes constantes

Uma relação de recorrência linear com coeficientes constantes é uma relação de recorrência da forma:

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_d{a}_{n-d}+c(n)$

em que o objetivo é expressar o termo geral a_n como uma função de n.

A relação é linear porque os termos da sequência aparecem de forma linear, ou seja, cada termo é uma combinação linear dos termos anteriores.

A ordem da relação é d.

A relação é homogênea quando c(n) = 0.

Esboço da solução

Cada solução é determinada unicamente pelos valores iniciais, $a_0,a_1,\dots ,a_{d-1}$. É fácil ver que as soluções da relação de recorrência linear homogênea com coefientes constantes

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_d{a}_{n-d}$

formam um espaço vetorial de dimensão d.

Portanto, se S_H representar as soluções da relação homogênea, e S_P for uma solução particular do caso geral, então S = S_H + S_P será uma solução geral.

Solução da relação homogênea

É fácil ver que a_n = λⁿ será uma solução da relação de recorrência

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_d{a}_{n-d}$

sempre que λ for uma raiz do polinômio

$p(t)=t^d-c_1{t}^{d-1}-c_2{t}^{d-2}-\dots -c_d$

Este polinômio é chamado de polinômio característico. Se uma raiz λ deste polinômio tem multiplicidade r maior que 1, então também são soluções, além de λⁿ, as sequências $n{\lambda }^n,n^2{\lambda }^n,\dots ,n^{r-1}{\lambda }^n$.

Ou seja, as raízes do polinômio caracteristico resolvem completamente o problema, ao fornecer uma base para a solução homogênea.