0
$\begingroup$

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.

Thank you in advance.

$\endgroup$
  • $\begingroup$ 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?). $\endgroup$ – Semiclassical Dec 14 '14 at 21:00
  • $\begingroup$ @Semiclassical Yes, $x = \frac{1}{3}$ and $x = -1$. $\endgroup$ – Connor Berg Dec 14 '14 at 21:21
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.