Let the sequence an be given by the recurrence relation

$$a_n = −2a_{n−1} + 8a_{n−2}$$ $$a_0 = 1, a_1 = 5$$

(a) Calculate $a_2, a_3$ and $a_4$.

(b) Derive an exact expression for the generating function of the sequence

$$A(x) = \sum_{n=0}^∞ a_nx^n$$

as a ratio of two polynomials.

(c) Use a partial fraction expansion of $A(x)$ to derive an exact expression for $a_n$.

I think I have some understanding of what I need to do but I am not completely sure.

(a) $a_2 = -2a_1+8a_0 = (-2)*5 + 8 = -2$

$a_3 = -2a_2+8a_1 = (-2)*(-2) + 8*5 = 44$

$a_4 = -2a_3+8a_2 = (-2)*44+8*(-2) = -104$

(b) Rearranging the relation we get

$a_n + 2a_{n−1} - 8a_{n−2} = 0$

Let $A = 1+5x-2x^2+44x^3-104x^4...$

then $2xA=2x+10x^2-4x^3+88x^4...$

and $-8x^2A=-8x^2-40x^3+16x^4...$

Adding the 3 up we get:

$(1+2x-8x^2)A = 1+7x$

Since all the cubic and higher terms are canceled out.

Hence, $$A = \frac{1+7x}{1+2x-8x^2}$$

I dont know about (c), but does this look ok?

  • $\begingroup$ Judging from the first 100 terms (via Mathematica) the generating function you've obtained is correct. So now all you need to do is to find the closed-form expression. $\endgroup$ – Semiclassical Sep 13 '15 at 5:51
  • 1
    $\begingroup$ Hint: $$\frac{1+7x}{1+2x-8x^2}=\frac{u}{1-ax}+\frac{v}{1+bx}$$ $\endgroup$ – Did Sep 13 '15 at 6:08

The solution is correct.

Now write $A = c_1/(1-2x) + c_2/(1+4x)$ with some $c_1$ and $c_2$ to derive the closed form. Alternatively, from this decomposition you know that $a_n = c_12^n + c_2(-4)^n$, so you can find $c_1$ and $c_2$ from plugging some values of $n$ in.

| cite | improve this answer | |

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.