Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a sequence created with the following recursive formula:

$a_{n+1} = 2 a_{n} + n$

I need to find a generating function for this one, so that I get the formula from which I can calculate the numbers. So according to a book "Generatingfunctionology" reccomended by one user here, I need to do the following steps:

1) Multiply the formula by $ x^{n} $, so I get:

$ x^{n}a_{n+1} = 2 x^{n}a_{n} + n x^{n} $

2) "Sum over all the values of n for which the relation is valid" - so basically I'm getting (let me omit some steps):

$ \sum_{n=0}^{ \infty } a_{n} x^{n} = \frac{1 - 2x + 2x^{2}}{(1-x)^{2}(1-2x)} $

My question is - does this pattern applies to all sequences given by a recursive formula?

And one more thing - this is the result of summing up infinitive sumber of single coefficients, or however you call this part right after the Epsilon sign. How am I supposed to get the sequence elements from this thing?

Or maybe I'm messing everything up?

share|cite|improve this question
Oh crap, I don't how how to apply latex to my post :/ – khernik Apr 24 '13 at 14:01
Replace your [tex] and [/tex] with $ for in-line tex, or $$ for tex on a new line. For instance $\sqrt{x}$ gives $\sqrt{x}$ and $$\sqrt{x}$$ gives $$\sqrt{x}$$ – Clive Newstead Apr 24 '13 at 14:06
Thank you, edited. – khernik Apr 24 '13 at 14:07
does this pattern applies to all sequences given by a recursive formula?... Unsurprisingly, no, but I seem to remember that the book you cite spends quite some time explaining which ones are OK. – Did Apr 24 '13 at 15:19

Once you have the generating function, usually the right strategy is to use partial fractions. In this case, you have $\frac{2x^2-2x+1}{(1-2x)(1-x)^2}=\frac{-1}{(1-x)^2}+\frac{2}{1-2x}$. These are now, hopefully, familiar generating functions. We have $\frac{1}{(1-x)^2}=\sum (n+1)x^n$ and $\frac{1}{1-2x}=\sum 2^nx^n$. Combining with the partial fraction representation, we get $a_n=-(n+1)+2\cdot 2^n$. Note that the coefficients $-1, 2$ are from the partial fractions.

In answer to your question of whether this will always work, unfortunately sometimes the generating function doesn't look like anything familiar. However this method does work for many types of recurrences.

share|cite|improve this answer
Thanks! Is there any list of these familiar generating functions? – khernik Apr 24 '13 at 14:23
Look e.g. at Wilf's "generatingfunctionology" (an old edition is free on the ǹet) – vonbrand Apr 24 '13 at 15:32
Also, a few basic ones are in the Wikipedia article, near the end of section 1.1. – vadim123 Apr 24 '13 at 17:38

Your Answer


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

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