# Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$.

I understand how to get the generating function:

$$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x + \sum_{k\geq2}(2a_{k-1} + 3a_{k-2})x^k = 8x + 2x\sum_{k\geq2}a_{k-1}x^{k-1} + 3x^2\sum_{k\geq2}a_{k-2}x^{k-2} = 8x + 2x\sum_{k\geq1}a_kx^k + 3x^2\sum_{k\geq0}a_kx^k = 8x + 2xG(x) + 3x^2G(x) = \frac{-8}{3x^2+2x-1}$$

However, I am stuck from here. I need to find the value of $a_k$ and from what I've researched I need to use partial fractions, but I'm not sure how to implement that.

• Whenever doing partial fractions, the first step is always to factor the denominator (which can be done by inspection here--do you see the roots?). – Semiclassical Dec 14 '14 at 21:00
• @Semiclassical Yes, $x = \frac{1}{3}$ and $x = -1$. – Connor Berg Dec 14 '14 at 21:21

Since ultimately you would like the denominators of the partial fractions to have the form $1-ax$, I’d start by multiplying top and bottom by $-1$ to get

$$\frac8{1-2x-3x^2}\;.$$

Now use your roots to factor the denominator, then set up the partial fraction decomposition:

$$\frac8{1-2x-3x^2}=\frac8{(1-3x)(1+x)}=\frac{A}{1-3x}+\frac{B}{1+x}\;.$$

Now just follow the usual procedure: recombine over the least common denominator to get

$$\frac8{(1-3x)(1+x)}=\frac{A(1+x)+B(1-3x)}{(1-3x)(1+x)}\;,$$

and conclude that since the equal fractions have the same denominator, they must have equal numerators:

$$A(1+x)+B(1-3x)=8\;.$$

Multiply out the lefthand side to get a constant term and an $x$ term, and equate coefficients with the righthand side, which has $8$ as constant term and $0x$ as $x$ term. That gives you two equations in $A$ and $B$, which you can solve. When you’ve done that, make use of the fact that

$$\frac1{1-3x}=\sum_{n\ge 0}(3x)^n\quad\text{and}\quad\frac1{1+x}=\frac1{1-(-x)}=\sum_{n\ge 0}(-x)^n\;.$$

Combine the sums into a single sum of the form $\sum_{n\ge 0}a_nx^n$ and read off the coefficient of $x^n$.