Tell me more ×
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.
up vote 0 down vote favorite
1

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
1  
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
1  
Although it can also be expressed in real terms, by introducing sines and cosines. – Gerry Myerson Nov 30 '12 at 1:54

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.