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

Publicado em 8 de Julho de 2011 por Américo Tavares

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

T(n)=3T(n-2)+9,\qquad T(1)=T(2)=1

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:

\begin{aligned}T(1) &=T(2)=U(1)=1 \\T(3)&=T(4)=U(2)=12 \\T(5) &=T(6)=U(3)=45 \\&\cdots\end{aligned}

Generalizando, tem-se

T(2n-1)=T(2n)=U(n),\qquad n\ge 1.\qquad (1)

Dado que

T(2n-1)=3T(2n-3)+9=3T(2n-2)+9,

obtemos

U(1)=1,\qquad U(n)=3U(n-1)+9,\qquad n\ge 2.\qquad (2)

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

U(1)=1,\qquad U(n)=AX^{n}+C,\qquad (3)

em que X é a raíz da equação característica X-3=0 associada à equação homogénea U(n)-3U(n-1)=0 e C é uma solução particular (neste caso, constante) de U(n)=3U(n-1)+9. De (2), deverá ser C=3C+9, isto é, C=-9/2. Assim U(n)=3^{n}A-9/2.

Da condição inicial U(1)=1, obtemos 1=3A-9/2, donde A=11/6. Por conseguinte a solução de (2) é

U(n)=\dfrac{11}{6}3^{n}-\dfrac{9}{2},\qquad n\ge 1\qquad (4)

Logo a solução da recorrência dada T(n)=3T(n-2)+9 é

T(2n-1)=T(2n)=U(n)=\dfrac{11}{6}3^{n}-\dfrac{9}{2},\qquad n\ge 1.\qquad (5)

Bibliografia (em português)

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

10-10-2012: Correcção C=3C+9.

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Exercícios Matemáticos, Matemática, Matemática Discreta, Problemas, Recorrência com as etiquetas , , . ligação permanente.

4 respostas a Resolução da relação de recorrência T(n) = 3T(n-2) + 9, T(1) = T(2) = 1

  1. glenda diz:
    10 de Fevereiro de 2012 às 17:40

    Matemática discreta estou vendo no 5° Período de matemática mas estou achando muiiito ruim! alguém me ajude!!!

    Responder
  2. Isadora diz:
    10 de Outubro de 2012 às 02:53

    Gostaria de saber porque c = 3c -9 e não c = 3c + 9, fiquei na dúvida nessa parte, estou fazendo discreta sem ter feito calculo 3 e estou com dificuldade…
    Grata

    Responder
  3. Isnard Lopes diz:
    31 de Maio de 2015 às 14:20

    Na verdade, a equação característica deve ser x²-3=0…

    Responder

Deixe um comentário

Este site utiliza o Akismet para reduzir spam. Fica a saber como são processados os dados dos comentários.