How do we solve the exact recurrence for $T(1) = 1, T(n) = 3T(n - 1) + 2n + 2$ for $n > 1$?

Question

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.

Answer 1

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}$.

Answer 2

Write $$ T(n)=A(n) 3^{n-1} $$ substituting $$ A(n+1) 3^n = 3 A(n) 3^{n-1}+ 2n + 2$$ Hence $$ A(n+1) = A(n) + \frac{2( n + 1)}{3^n}$$

Hence $$ A(n) = \sum_{k=1}^{n} \frac{k}{3^{k-1}} $$ Finally $$ T(n) = 3^{n-1} \sum_{k=1}^{n}\frac {k}{3^{k-1}}$$

There are some tricks to simplify the last summation.