How to derive the closed form of this recurrence? 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.
 A: 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.$$
A: 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$. 
A: 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}
$$
