How can I solve this recurrence relation: $a_n = 3a_{n-1} + \frac{4^n}{4}$? How can I solve the following recurrence relation?
$$a_n = 3a_{n-1} + \frac{4^n}{4}$$
I know that $a_n^{(h)} = 3a_{n-1}$ and that the characteristic equation is:
$$r-3 = 0$$ and thus:
$$a_n^{(h)} = \alpha_1(3)^n$$
I am struggling with the particular solution $a_n^{(p)}$.
 A: HINT : 
Dividing the both sides by $3^n$ gives
$$\frac{a_n}{3^n}=\frac{a_{n-1}}{3^{n-1}}+\frac{1}{4}\cdot\left(\frac 43\right)^n\iff b_n-b_{n-1}=\frac{1}{4}\cdot\left(\frac 43\right)^n$$
where $b_n=\frac{a_n}{3^n}$.
A: Consider the generating function for $a_{n}$. The process is the following.
\begin{align}
\sum_{n=0}^{\infty} a_{n+1} \, t^{n} &= 3 \, \sum_{n=0}^{\infty} a_{n} \, t^{n} +  \sum_{n=0}^{\infty} (4t)^{n} \\
\frac{1}{t} \, \sum_{n=1}^{\infty} a_{n} \, t^{n} &= 3 \, A(t) + \frac{1}{1-4t} \\
\frac{1}{t} \left( A(t) - a_{0} \right) &= 3 \, A(t) + \frac{1}{1-4t} 
\end{align}
where $A(t) = \sum_{n=0}^{\infty} a_{n} \, t^{n}$, which leads to
\begin{align}
A(t) &= \frac{a_{0}}{1-3t} + \frac{t}{(1-3t)(1-4t)} \\
&= \frac{a_{0}}{1-3t} + \left( \frac{1}{1-4t} - \frac{1}{1-3t}\right) \\
&= \frac{a_{0} - 1}{1-3t} + \frac{1}{1-4t} \\
&= \sum_{n=0}^{\infty} \left((a_{0} - 1) \, 3^{n} + 4^{n}\right) \, t^{n}
\end{align}
and finally
\begin{align}
a_{n} = 3^{n} \, (a_{0} - 1) + 4^{n}.
\end{align}
A: Hint. A particular solution is $a_n^{(p)}=4^n$.
A: You have 
$$a_{n} = 3~a_{n-1} + 4^{n-1} \tag{X}$$
and
$$a_{n+1} = 3~a_{n} + 4\cdot 4^{n-1} \tag{Y}$$
Compute $Y - 4X$ and you'll have a basic linear recurrence.
A: Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write your recurrence as:
$$
a_{n + 1} = 3 a_n + 4^n
$$
Multiply by $z^n$, add over $n \ge 0$ to get:
$$
\sum_{n \ge 0} a_{n + 1} z^n
  = 3 \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} 4^n z^n
$$
Recognize some sums:
$$
\frac{A(z) - a_0}{z}
  = 3 A(z) + \frac{1}{1 - 4 z}
$$
Solve for $A(z)$, write as partial fractions:
$\begin{align}
A(z) &= \frac{a_0 - (4 a_0 - 1) z}{1 - 7 z + 12 z^2} \\
     &= \frac{a_0 - 1}{1 - 3 z} + \frac{1}{1 - 4 z}
\end{align}$
This is just two geometric series:
$$a_n = (a_0 - 1) \cdot 3^n + 4^n$$
