<s>[INST] 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)}$.
 [/INST] 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}
</s>