# Solve the recurrence relation $a_n = 4a_{n-1} - 3a_{n-2} + 2^n$

Solve the recurrence relation

$$a_n = 4a_{n-1} - 3a_{n-2} + 2^n$$

With initial conditions:

$$a_1 = 1$$

$$a_2 = 11$$

I have done similar recurrence relation problems to this, but none that were a non-homogeneous recurrence relation such as this one.

So far I have:

$$r^n = 4^{n-1} - 3^{n-2}$$

Divide both sides by $$\frac{1}{r^{n-2}}$$ Giving me this as my Auxiliary Equation:

$$r^n - 4r + 3 = 0$$

I then solved for the $$r$$ values and got $$r = -4$$ and $$r = 1$$ I am stumped from here as to where the non-homogeneous piece comes into play, any help is appreciated.

• You need to find a single solution to the non-homogeneous equation. Since it contains $2^n$ part, try $c2^n$ and see if you can solve for $c$. Sidenote: double-check your solution to Auxiliary Equation.
– A.S.
Oct 11 '15 at 22:19
• This question was asked and answered today. Oct 11 '15 at 22:26
• Sep 28 '17 at 12:54

Hint: $$a_n = 4a_{n-1} - 3a_{n-2} + 2^n \tag{P}$$ $$a_{n+1} = 4a_n - 3a_{n - 1} + 2^{n+1} \tag{Q}$$

Now subtract equations as $Q - 2P$.

Start by finding the general solution to the homogeneous recurrence relationship:

$$a_n = 4a_{n-1} - 3a_{n-2}$$

This has auxiliary equation $\lambda^2=4 \lambda-3$

$\lambda^2-4\lambda+3=0$

$\lambda_1=1, \lambda_2=3$

$$a_n = A(1)^n +B(3)^n$$

You want a particular solution to the non-homogeneous relationship.

Try $a_n=k(2)^n$

Then $a_{n-1}=\frac 12 k(2)^n$, $a_{n-2}=\frac 14 k(2)^n$

So $k(2)^n = 4\left (\frac 12 k(2)^n \right)-3 \left(\frac 14 k(2)^n \right)+(2)^n$

$k = 2k - \frac 34 k +1$

$k=-4$

Add this to the general solution to the homogeneous relationship to find the general solution to the non-homogeneous relationship.

$$a_n = A +B(3)^n-4(2)^n$$

Use the known values $a_1=1$ and $a_2=11$

$1=A+3B-8$

$11=A+9B-16$

gives $10=6B-8$

$6B=18$

$B=3$

$1=A+9-8$

$A=0$

$$a_n =3(3)^n-4 (2)^n$$

A general technique is to use generating functions. Define $$A(z) = \sum_{n \ge 0} a_n z^n$$, write your recurrence as: $$a_{n + 2} = 4 a_{n + 1} - 3 a_n + 4 \cdot 2^n$$ Multiply by $$z^n$$, sum over $$n \ge 0$$ and recognize some sums:

\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= 4 \sum_{n \ge 0} a_{n + 1} z^n - 3 \sum_{n \ge 0} a_n z^n + 4 \sum_{n \ge 0} 2^n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 4 \frac{A(z) - a_0}{z} - 3 A(z) + 4 \frac{1}{1 - 2 z} \\ \frac{A(z) - 1 - 11 z}{z^2} &= 4 \frac{A(z) - 1}{z} - 3 A(z) + 4 \frac{1}{1 - 2 z} \end{align*}

Solve for $$A(z)$$, as partial fractions:

$$A(z) = \frac{7}{1 - 3 z} - \frac{4}{1 - 2 z} - \frac{2}{1 - z}$$

This is just geometric series. We want:

$$a_n = [z^n] A(z) = 7 \cdot 3^n - 4 \cdot 2^n - 2$$