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)}$.
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}$.
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.
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}
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$$
