The given recurrence relation is:

$S(n) - 3S(n-1) - 4S(n-2) = 4^n$

This is a non-homogeneous linear recurrence relation because of the $4^n$ on the right-hand side. To solve it, we will:

Step 1: Solve the homogeneous part

Consider the homogeneous version of the recurrence relation (i.e., set the right-hand side to 0):

$S(n) - 3S(n-1) - 4S(n-2) = 0$

The characteristic equation for this is:

$r^2 - 3r - 4 = 0$

Solve for $r$ using the quadratic formula:

$r = \frac{-(-3) \pm \sqrt{(-3)^2 - 4(1)(-4)}}{2(1)}$ $r = \frac{3 \pm \sqrt{9 + 16}}{2} = \frac{3 \pm \sqrt{25}}{2} = \frac{3 \pm 5}{2}$

Thus, the roots are:

$r_1 = 4 \quad \text{and} \quad r_2 = -1$

The general solution to the homogeneous equation is:

$S_h(n) = C_1 4^n + C_2 (-1)^n$

Step 2: Find a particular solution

Now, we find a particular solution $S_p(n)$ to the non-homogeneous equation. Since the right-hand side is $4^n$, which is already a solution to the homogeneous equation, we need to multiply by $n$ to avoid duplication. So, we try a particular solution of the form:

$S_p(n) = A n 4^n$

Substitute this into the original recurrence relation:

$A n 4^n - 3A (n-1) 4^{n-1} - 4A (n-2) 4^{n-2} = 4^n$

Simplifying the powers of $4$:

$A n 4^n - 3A (n-1) 4^n - 4A (n-2) 4^n = 4^n$ $A n - 3A (n-1) - 4A (n-2) = 1$

Simplify further:

$A n - 3A n + 3A - 4A n + 8A = 1$ $(-6A n + 11A) = 1$

Thus, equating coefficients of $n$ and constants:

$-6A = 0 \quad \text{and} \quad 11A = 1$

From $11A = 1$, we get:

$A = \frac{1}{11}$

Thus, the particular solution is:

$S_p(n) = \frac{n}{11} 4^n$

Step 3: General solution

The general solution to the non-homogeneous recurrence relation is:

$S(n) = S_h(n) + S_p(n) = C_1 4^n + C_2 (-1)^n + \frac{n}{11} 4^n$

Conclusion:

The solution to the recurrence relation is:

$S(n) = \left(C_1 + \frac{n}{11}\right) 4^n + C_2 (-1)^n$

Where $C_1$ and $C_2$ are