# Calculating recursive sequence numbers using generating functions

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?

-
Oh crap, I don't how how to apply latex to my post :/ –  khernik Apr 24 '13 at 14:01
Replace your $$ and $$ 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 ## 1 Answer 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.

-
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