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

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|improve this question
Oh crap, I don't how how to apply latex to my post :/ – khernik Apr 24 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 at 14:06
Thank you, edited. – khernik Apr 24 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 at 15:19

1 Answer

up vote 1 down vote

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

Your Answer

 
discard

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.