<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] 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$$
</s>