How can I solve this recurrence relation: $a_n = 3a_{n-1} + \frac{4^n}{4}$?

Question

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

Answer 1

Hint. A particular solution is $a_n^{(p)}=4^n$.

Answer 2

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

Answer 3

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.

Answer 4

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}

Answer 5

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$$