How do we solve the exact recurrence for $T(1) = 1, T(n) = 3T(n - 1) + 2n + 2$ for $n > 1$? This looks like an exponential recurrence due to the 3 behind $T$, but I'm not sure how to formally solve for $T(n)$ without $T$ on the righthand side.


Hint $$T(n)+n=3(T(n-1)+(n-1))+5$$

So we just solve $a_1=2$, $a_{n}=3a_{n-1}+5$.

Hint $$a_n+\frac{5}{2}=3(a_{n-1}+\frac{5}{2})$$

Then $b_1=\frac{9}{2}$ and $b_n=3b_{n-1}$.
