Recurrence Relations Closed Form So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$
$\begin{align}T(n) &= 3T(n-1)+5
    \\&= 3(3T(n-2)+5)+5
     \\&= 3(3(3T(n-3)+5)+5)+5\end{align}$
I'm just struggling to go from here. I understand that it's $3$ to the power of something but I'm lost on what I have to do after this. 
 A: Calculating the first few values: $0,5,20,65,200$ , dividing by $5$ this is $0,1,4,13,40$ , multiplying by $2$ we get $0,2,8,26,80$ adding $1$ we get $1,3,9,27,81$. Otherwise you can use generating functions:
Let $A=\sum\limits_{n=0}^\infty t(n)x^n$.
Then $A=3xA+5\sum\limits_{n=1}^\infty x^n$ (since $f(0)=0$).
Then $(1-3x)A=\frac{5}{1-x}-5$ so $A=\frac{5}{(1-3x)(1-x)}-\frac{5}{1-3x}=\frac{5}{2(x-1)}-\frac{15}{2(3x-1)}+\frac{5}{3x-1}=\frac{5}{2(x-1)}-\frac{5}{2(3x-1)}=\frac{1}{2}(\sum\limits_{n=0}^\infty 5\cdot 3^{n} -5)$
therefore $f(n)=\frac{5(3^{n}-1)}{2}$
A: There are two types of solutions here: the homogeneous and the particular.  Rewrite the equation as
$$T_n - 3 T_{n-1} = 5$$
The homogeneous solution is simply the solution assuming the RHS is zero.  Thus $T_n^{(H)} = A \cdot 3^n$.  The particular solution is a simple solution that satisfies the equation and boundary conditions.  In this case, $T_n^{(P)} = B$, a constant:
$$B - 3 B = 5 \implies B=-\frac{5}{2} $$
The solution is the sum of the homogeneous and particular solutions:
$$T_n = A \cdot 3^n - \frac{5}{2} $$
$$T(0)=0 \implies A=\frac{5}{2} $$  
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
"$\,$If$\,$" there is a solution which is $n$-independent it should be $\ds{\frac{5}{1 - 3} =-\,\frac{5}{2}}$. It means that
$\ds{\,{\rm T}\pars{n} - \pars{-\,\frac{5}{2}}}$ satisfies a homogeneous recurrence equation:
\begin{align}
\,{\rm T}\pars{n} + \frac{5}{2}=3\bracks{\,{\rm T}\pars{n - 1} + \frac{5}{2}}
\end{align}
Then,
\begin{align}
\,{\rm T}\pars{n} + \frac{5}{2}=3^{1}\bracks{\,{\rm T}\pars{n - 1} + \frac{5}{2}}
=3^{2}\bracks{\,{\rm T}\pars{n - 2} + \frac{5}{2}}=\cdots=
3^{n}\bracks{\overbrace{\,{\rm T}\pars{0}}^{\ds{=\ \dsc{0}}} + \frac{5}{2}}
=\frac{5}{2}\,3^{n}
\end{align}
which leads to:
$$
\color{#66f}{\large\,{\rm T}\pars{n}}
=\color{#66f}{\large\frac{5}{2}\pars{3^{n} - 1}}
$$
