Questão 2 (2 pts) - Resolva as seguintes relações de recorrência:
T(n)=5 T(n-1)-6 T(n-2)+2, T(0)=1, T(1)=2.

Passo 1

Vou deixar claro o que o enunciado dá e o que pede.
  • Relação de recorrência dada: T(n)=5\,T(n-1)-6\,T(n-2)+2, com condições iniciais T(0)=1,\qquad T(1)=2.
  • O que se pede: encontrar a fórmula fechada (expressão explícita) de T(n) para todo n natural.

Passo 2

Primeiro tratamos a parte homogênea da recorrência (ou seja, ignoramos o termo constante +2) para obter a solução geral da homogênea.
  • A recorrência homogênea correspondente é T_h(n)=5\,T_h(n-1)-6\,T_h(n-2).
  • Para resolver esse tipo de recorrência linear com coeficientes constantes, fazemos a substituição padrão T_h(n)=r^n. Isso gera a equação característica: r^2-5r+6=0.
  • Resolvendo essa equação quadrática: r^2-5r+6=(r-2)(r-3)=0, logo as raízes são r_1=2,\qquad r_2=3.
  • Como as raízes são distintas, a solução geral da homogênea é uma combinação linear das potências das raízes:
T_h(n)=A\cdot 2^n + B\cdot 3^n,
onde A e B são constantes a determinar pelas condições iniciais.
(Explicação rápida e intuitiva: cada raiz da equação característica dá uma solução da forma r^n; com duas raízes distintas, combinam-se linearmente.)

Passo 3

Agora procuramos uma solução particular T_p(n) da recorrência completa (incluindo o termo constante +2).
  • Observação: o termo não-homogêneo é uma constante ( +2). Pelo método dos coeficientes a determinar, tentamos uma solução particular constante: T_p(n)=C, onde C é uma constante desconhecida.
  • Substituindo T_p(n)=C na recorrência original:
C = 5C - 6C + 2.
  • Simplificando a equação: C = -C + 2, portanto 2C = 2 e C=1.
(Comentário didático: tentamos constante porque o lado não-homogêneo é constante. Isso funciona desde que 1 não seja raiz da equação característica. Se 1 fosse raiz, teríamos que multiplicar o palpite por n. Aqui as raízes foram 2 e 3, então 1 não é raiz e o palpite constante é válido.)

Passo 4

Montamos a solução geral da recorrência somando a solução homogênea com a particular:
T(n)=T_h(n)+T_p(n)=A\cdot 2^n + B\cdot 3^n + 1,
onde A e B ainda precisam ser determinados pelas condições iniciais.

Passo 5

Usamos as condições iniciais para encontrar [A) e B.
  • Para n=0, T(0)=A\cdot 2^0 + B\cdot 3^0 + 1 = A + B + 1. Como T(0)=1, obtemos a equação
A + B + 1 = 1 \quad\Rightarrow\quad A + B = 0.
  • Para n=1, T(1)=A\cdot 2^1 + B\cdot 3^1 + 1 = 2A + 3B + 1. Como T(1)=2, obtemos
2A + 3B + 1 = 2 \quad\Rightarrow\quad 2A + 3B = 1.
Agora resolvemos o sistema linear formado por
\begin{cases} A + B = 0,\\[4pt] 2A + 3B = 1. \end{cases}
  • Da primeira equação A = -B\]. Substituindo na segunda: \[2(-B) + 3B = 1 \quad\Rightarrow\quad -2B + 3B = 1 \quad\Rightarrow\quad B = 1.\] - Logo \(A = -B = -1.]

Passo 6

Encontramos os valores das constantes: A=-1 e B=1. Com isso a solução explícita está completamente determinada.

Resposta

T(n)=3^{n}-2^{n}+1

Exercícios relacionados