Reccurence relation

Question

Closed form of $\ nT_n = 3(n-1)T_{n-1} + 1, n \ge 1$

I've tried calculating some terms, and looking it up on wolframalpha, it sais the generating function is $\frac{exp(x)}{1-3x}$. Where do i start?

Answer 1

First make a substitution $B_n = nT_n$ so this recursion becomes $B_n = 3B_{n-1} +1$.

Next add $\frac{1}{2}$ to both sides to get $B_n + \frac{1}{2} = 3B_{n-1} +\frac{3}{2}$.

Now let $A_n = B_n + \frac{1}{2}$ this becomes $A_n = 3A_{n-1}$ which you can easily tell has closed form $A_n = \frac{3^n}{2}$.

Translating it all back we get $T_n = \frac{3^n - 1}{2n}$.