Resolução da relação de recorrência <em>T</em>(<em>n</em>) = 3<em>T</em>(<em>n</em>-2) + 9, <em>T</em>(1) = <em>T</em>(2) = 1

Mais uma vez publico aqui a tradução de uma resposta a uma questão no MSE. Desta vez trata-se da resolução da relação de recorrência

pedida por Nir nesta questão. Apliquei a ideia fundamental indicada num comentário de Ross Millikan. Inicialmente enganei-me na resolução, fui alertado para o erro por user6312 e refi-la.

Os primeiros termos são:

Generalizando, tem-se

Dado que

obtemos

Vamos aplicar rudimentos da teoria das recorrências  (ou equações com diferenças, ver por ex. An introduction to difference equations de Saber Elaydi.) Esta relação de recorrência é não homogénea,  pelo que teremos de determinar uma solução particular da recorrência e resolver a recorrência homogénea, que é linear e tem coeficientes constantes . Assim, a solução explícita é da forma

em que é a raíz da equação característica associada à equação homogénea e é uma solução particular (neste caso, constante) de . De , deverá ser , isto é, . Assim .

Da condição inicial , obtemos , donde . Por conseguinte a solução de é

Logo a solução da recorrência dada é

Bibliografia (em português)

ANDRÉ, Carlos e FERREIRA, Fernando, Matemática Finita, Universidade Aberta, nº 203, Lisboa, 2000.