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}+\ldots +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},\ldots ,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}+\ldots +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}+\ldots +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}-\ldots -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},\ldots ,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.