Question

Resolva a recorrência abaixo:
T(1) = 1
T(n) = 3T(n-1) + 2, sendo n > 1

Answer 1

Primeiro passo:

Se f(n) é uma recorrência em n da forma $f(n)=k.f(n-1) +g(n)$ , sendo g(n) uma função em n devemos dividir a equação por $k^{n}$, logo:

$\frac{T(n)}{3^{n}}=\frac{3.T(n-1)}{3^{n}} + \frac{2}{3^{n}} \\\frac{T(n)}{3^{n}}=  \frac{T(n-1)}{3^{n-1}} + \frac{2}{3^{n}}$

lembrando que "2" será nossa função em n: g(n)=2

Segundo passo:

Utilizar uma recorrência auxiliar, ou seja chamaremos $\frac{T(n)}{3^{n}}$ de uma recorrência K(n), sendo assim :

$\frac{T(n-1)}{3^{n-1}} =K(n-1)\\ \frac{T(n)}{3^{n}}=K(n)$

Logo, teremos:

$K(n)=K(n-1)+\frac{2}{3^{n}} \\K(n-1)=K(n-2) + \frac{2}{3^{n-1}} \\...\\K(2)=K(1)+\frac{2}{3^{2}}$

Somando todas as equações, teremos:

$K(n)=K(1)+\frac{2}{3^{2}} +  \frac{2}{3^{2}} +... +\frac{2}{3^{n-1}} +\frac{2}{3^{n}} \\K(1)=\frac{T(1)}{3}= \frac{1}{3} \\K(n)=\frac{T(n)}{3^{n}}\\\frac{T(n)}{3^{n}} = \frac{1}{3} +\frac{2}{3^{2}} +  \frac{2}{3^{3}} +... +\frac{2}{3^{n-1}} +\frac{2}{3^{n}}$

Após o $\frac{1}{3}$ temos uma soma de PG com "n-1" termos de razão igual à $\frac{1}{3}$ ,  primeiro termo igual à $\frac{2}{3^{2}}$ e último termo igual à $\frac{2}{3^{n}}$, logo:

$\frac{T(n)}{3^{n}}= \frac{1}{3} + \frac{ \frac{2}{3^{2}}.[ (\frac{1}{3})^{n-1}-1]  }{ \frac{1}{3}-1 } \\\frac{T(n)}{3^{n}}= \frac{1}{3}-\frac{1}{3}.[( \frac{1}{3})^{n-1}-1] \\ \frac{T(n)}{3^{n}}= \frac{2}{3} -(\frac{1}{3})^{n}\\ T(n)=3^{n}.\frac{2}{3}-3^{n}. (\frac{1}{3})^{n}\\ T(n)=2.3^{n-1}-1$

Podemos testar T(2) para verificar a veracidade da resposta encontrada:

$T(2)=3.T(1)+2=3.1+2=5\\T(2)=2.3^{2-1}-1=2.3-1=5$

Logo, podemos ver que achamos a resposta correta.

Por favor, se a explicação lhe serviu, peço que indique como melhor resposta :). Abraços