How to derive the closed form of this recurrence?

Question

For the recurrence, $T(n) = 3T(n-1)-2$, where $T(0)= 5$, I found the closed form to be $4\cdot 3^n +1$(with help of Wolfram Alpha). Now I am trying to figure it out for myself. So far, I have worked out: $T(n-1) = 3T(n-2)-2, T(n-2) = 3T(n-3)-2, T(n-3) = 3T(n-4)-2$ leading me to: $T(n)=81\cdot T(n-4)-54-18-6-2 $ etc. I have noticed the constants follow a Geometric Series whose sum is given by $1-3^n$. I am having trouble putting this together to end up with the final closed form.

Answer 1

There are many ways to solve such linear recurrences. We describe one of them.

Let the $n$-th term be $T_n$. We are told that $$T_n=3T_{n-1}-2.$$ It would be nice to get rid of the constant term $-2$. Let $T_n=U_n+d$, where we will choose $d$ soon. Then $$U_n+d=3(U_{n-1}+d)-2.$$ The constant term disappears if we choose $d=1$, and we obtain the recurrence $$U_n=3U_{n-1}.$$ Since $T_0=5$, it follows that $U_0=4$, and therefore $U_n=4\cdot 3^n$. It follows that $T_n=4\cdot 3^n+1$.

Remark: We analyze along your lines. We have $T_n=3T_{n-1}-2$. Thus $$T_n=3(3T_{n-2}-2)-2=3^2T_{n-2}-3.\cdot 2-2.$$ Substituting again, we get $$T_n=3^3T_{n-2}-3^2\cdot 2-3\cdot 2-2,$$ and then $$T_n=3^4T_{n-4}-3^3\cdot 2-3^2\cdot 2-3\cdot 2-2,$$ and so on. Ultimately, we end up with $$T_n=3^nT_0 -2(1+3+3^2+\cdots +3^{n-1}).$$ The sum of the geometric series $1+3+\cdot +3^{n-1}$ is $\frac{3^n-1}{3-1}$. Using the fact that $T_0=5$, we find that $$T_n=3^n \cdot 5-(3^n-1)=4\cdot3^n+1.$$

Answer 2

By making use of the generating function method the difference equation $T_{n} = 3 T_{n-1} - 2$, $T_{0} = 5$, can be seen as follows \begin{align} T(x) &= \sum_{n=0}^{\infty} T_{n} x^{n} = 3 \sum_{n=0}^{\infty} T_{n-1} x^{n} - 2 \sum_{n=0}^{\infty} x^{n} \\ T(x) &= 3 \left( T_{-1} + \sum_{n=1}^{\infty} T_{n-1} x^{n} \right) - \frac{2}{1-x} \\ &= 3 \left( T_{-1} + x T(x) \right) - \frac{2}{1-x} \end{align} which yields \begin{align} (1-3x) T(x) = 3 T_{-1} - \frac{2}{1-x}. \end{align} Since $T_{-1} = \frac{7}{3}$ then \begin{align} T(x) &= \frac{5 - 7x}{(1-x) (1-3x)} = \frac{1}{1-x} + \frac{4}{1-3x} \\ &= \sum_{n=0}^{\infty} \left( 4 \cdot 3^{n} + 1 \right) x^{n} \end{align} and provides $T_{n} = 4 \cdot 3^{n} + 1$.

Answer 3

Multiply the recursion by $3^{-n}$: $$ 3^{-n}T(n)=3^{-n+1}T(n-1)-2\cdot3^{-n} $$ Thus, $$ 3^{-n}T(n)=-2\cdot3^{-n}-2\cdot3^{-n+1}-\dots-2\cdot3^{-1}+T(0) $$ Multiply by $3^n$: $$ \begin{align} T(n) &=-2\cdot3^0-2\cdot3^1-\dots-2\cdot3^{n-1}+3^nT(0)\\[3pt] &=-2\frac{3^n-1}{3-1}+3^nT(0)\\[4pt] &=-3^n+1+3^nT(0)\\[4pt] &=4\cdot3^n+1 \end{align} $$