Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having trouble midway with solving this recurrence relation using generating functions:

$a_{k+2} - a_{k + 1} + 2a_k = 4^x$, with initial conditions $a_0=2, a_1=1$.

I'm not sure if this is right, but my generating function is $\frac{5x^2 - 9x + 2}{(1-4x)(1-x+2x^2)}$

I want to extract the coefficient of $x^k$, so I used partial fractions to get $ \frac{-((17 x)/14-27/14)}{(2 x^2-x+1)} + \frac{1/14}{(1-4x))}$

The second term gives 4^k / 14, but I'm not sure how to proceed for the first term...

share|improve this question
You need to use partial fractions one more time on the first term. Note that $2x^2-x+1= 2(x-a)(x-b)$ for some $a$ and $b$, hence $\frac{1}{2x^2-x+1} = \frac{1}{2(a-b)}\Big(\frac{1}{x-a}- \frac{1}{x-b}\Big)$. Now using the geometric sum on each of the two terms on the right you should get the closed formula you seek. –  newguy Nov 29 '12 at 17:56
You mean with complex roots? You can't factor the denominator anymore otherwise... –  user1526710 Nov 29 '12 at 19:49
Yes I mean with complex roots. We get $ \frac{1}{2x^2-x+1} = \frac{1}{\sqrt{-7}} \Big( \frac{4}{4 x-1-\sqrt{-7}} - \frac{4}{4 x-1+\sqrt{-7}}\Big)$. Using the geometric series to rewrite each of the two terms on the right will give you the formula you seek. –  newguy Nov 29 '12 at 20:12
Although it can also be expressed in real terms, by introducing sines and cosines. –  Gerry Myerson Nov 30 '12 at 1:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.