# Closed form solution for the recurrence

I am given the following recurrence and need to find a closed form solution for the recurrence. I have no idea on how to get started though and i need some help on leading me to solve this.

$A_0=20, A_1=60$ and for $n > 1, A_n= 2A_{n-1}+3A_{n-2}+4^n+6$

I have done this so far but i don't understand what i should do next.

$A_2 = 2(60) + 3(20) +4^2 +6 = 202$

$A_3 = 2(202) + 3(60) +4^3 +6 = 654$

$A_4 = 2(654) + 3(202) +4^4 +6 = 2176$

$A_5 = 2(2176) + 3(654) +4^5 +6 = 7344$

I don't really see a pattern between these where $A_n = ...?$

Solved it: $A_n = 1.55(-1)^n + 16.75(3^n) + 3.2(4^n) - 1.5$! Thanks guys

Generally, recurrences of this form are solved in two stages:

1. First solve $A_n = 2A_{n-1} + 3A_{n-2}$. You will get a solution of the form $A_n = c_1 x_1^n + c_2 x_2^n$, where $x_1$ and $x_2$ are found from the recurrence and $c_1,c_2$ are found from the initial conditions after stage 2.
2. Find a particular solution to $A_n = 2A_{n-1} + 3A_{n-2} + 4^n + 6$. Generally, a good idea is to try solutions similar to the non-homogenous part $4^n + 6$. I'd guess something like $A_n = c_34^n + c_4$, plug into the recurrence and find the values of $c_3,c_4$.

Then, the full solution is of the form $A_n = c_1x_1^n + c_2x_2^n + c_34^n + c_4$.

Can you take it from there?

• Hey Thanks so much i got the answer thanks to both of your guys answers. I just marked yours since you were "first" Commented Nov 6, 2015 at 2:35

Outline: There are many ways to solve this kind of problem. The solution we sketch below may be quite different from the one you were taught.

We break the problem into three parts: (i) finding the general solution of the homogeneous equation $A_n-2A_{n-1}-3A_{n-2}=0$; (ii) finding a particular solution of the given equation; and then (iii) finding the general solution of the given equation, and applying the initial conditions.

(i) For the general solution of the homogeneous equation, I suggest using the characteristic equation method. The characteristic equation is $x^2-2x-3=0$, which has roots $-1$ and $3$, so the general solution of the homogeneous equation is $P(-1)^n +Q3^n$ where $P$ and $Q$ are arbitrary constants.

(ii) We look for a particular solution of the shape $a4^n+b$.

Plugging in we get $a4^n+b-2a4^{n-1}-2b-3a4^{n-2}-3b=4^n+6$. Now we can find $a$ and $b$.

(iii) Finally, the general solution is $P(-1)^n+Q3^n+a4^n+b$ where $a$ and $b$ are known. Now choose $P$ and $Q$ so the initial conditions are satisfied.

Yet another technique: Use generating functions. Define $g(z) = \sum_{n \ge 0} A_n z^n$, shift indices to get:

\begin{align} A_{n + 2} = 2 A_{n + 1} + 3 A_n + 16 \cdot 4^n + 6 \end{align}

Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:

\begin{align} \sum_{n \ge 0} A_{n + 2} z^n &= 2 \sum_{n \ge 0} A_{n + 1} z^n + 3 \sum_{n \ge 0} A_n z^n + 16 \sum_{n \ge 0} 4^n z^n + 6 \sum_{n \ge 0} z^n \\ \frac{g(z) -A_0 - A_1 z}{z^2} &= 2 \frac{g(z) - A_0}{z} + 3 g(z) + \frac{16}{1 - 4 z} + \frac{6}{1 - z} \end{align}

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

\begin{align} g(z) &= \frac{20 - 80 z + 2 z^2 + 40 z^3} {1 - 7 z + 11 z^2 + 7 z^3 - 12 z^4} \\ &= \frac{16}{5 (1 - 4 z)} + \frac{67}{4 (1 - 3 z)} - \frac{3}{2 (1 - z)} + \frac{31}{20 (1 + z)} \end{align}

Everything in sight is a geometric series:

\begin{align} A_n &= \frac{16}{5} \cdot 4^n + \frac{67}{4} \cdot 3^n - \frac{3}{2} + \frac{31}{20} \cdot (-1)^n \end{align}