2

I've been reading through other questions on this site and external resources for a few hours now but seem to be having a mental block, probably through some elementary misunderstanding of my course notes or most likely because my mathematical maturity is certainly prepubescent! I haven't a clue how I would show the following (I know it's ludicrously simple):

If there is a sequence $\{a_{k}\}=(-3)^{k}$, what is its generating function?

I'm not quite sure what is 100% going on behind a generating function. Any "for dummies" explanation would be greatly appreciated.

Thanks for your patience and interest.

Old mate
  • 694
  • 4
    Some additional resources: Wilf's generatingfunctionology is one of the best resources available, and it can be found on his site in pdf form for free. (I'm also a fan of Flajolet and Sedgwick's Analytic Combinatorics, and while it's decidedly more advanced it's also available for free in pdf form.) – Semiclassical Sep 07 '14 at 05:05
  • As to the generating function GF, it depends on which one you're interested in! The most obvious is the ordinary GF of ${a_k}$ with respect to $x$, defined as $\sum_{k=0}^\infty a_k x^k$. So if you can sum this series for your given $a_k$, you've got the GF. – Semiclassical Sep 07 '14 at 05:07
  • To give you an idea of how new this concept is to me (or how fried my brain is currently), I tried reading through the introductory chapter of generatingfunctionology but quickly became lost. – Old mate Sep 07 '14 at 05:08
  • It takes some getting comfortable with, to be sure. It helps if you've had some background with polynomial rings in abstract algebra, if only because it forces you to distinguish between polynomials as equations and as objects in and of themselves. – Semiclassical Sep 07 '14 at 05:11
  • If you're interested in the subject more generally, the curiously named text Generatingfunctionology is a good resource, and the second edition is available for free: http://www.math.upenn.edu/~wilf/ – Travis Willse Sep 07 '14 at 05:26

1 Answers1

2

For the gf:

$$G (x)=\frac{1}{1+3 x}$$

$$ \frac{1}{1-a x}=\sum _{k=0}^{\infty } a^k x^k $$

You can get that from any table of generating functions.

https://en.wikipedia.org/wiki/Generating_function

Or you can derive that one from the simplest one,

$$ \frac{1}{1- x}=\sum _{k=0}^{\infty } x^k $$

by substituting x = ax in it. So you see there are at least 3 ways, 1) sum the series, 2) Look it up in a table and 3) derive it from one we already know.

Try Applied Combinatorics by Tucker starting with chapter 6. Best way to learn anything at all is to see what it can be used for.

For your comments below:

$$s = 1 + ax + a^2x^2 + a^3x^3 +...+$$

$$axs = ax + a^2x^2 + a^3x^3 +...+$$

$$s - axs = 1$$

$$s(1-ax)=1$$

$$ s= \frac{1}{1-ax}$$

bobbym
  • 2,546
  • I am aware that this is the answer, however I'm interested in the in-between steps, and an understanding of them more than the answer itself. Thanks, though. – Old mate Sep 07 '14 at 05:13
  • 1
    You can do the sum as Semiclassical suggests or use a table. Some simple ones like that you should commit to memory. – bobbym Sep 07 '14 at 05:17
  • I'm interested in understanding how to do the sum. When I do this, I get $g(x)=1+ax+a^{2}x^{2}+...+a^{k}x^{k}$. Cool. Nothing foreign about that. I've seen in some texts that what generally happens next is both sides are multiplied by $x$, giving $xg(x)=x+a^{1}x^{2}+...+a^{k}+x^{k+1}$, and then you perform $g(x)-xg(x)$, before dividing through by $(1-x)$. But this just gets me back to $g(x)$, in the same form it was in at the start. Where I am getting lost, is that step. Thanks again for your patience. – Old mate Sep 07 '14 at 06:07
  • 1
    See the post, I have edited it. – bobbym Sep 07 '14 at 06:38
  • 1
    Thank you very much. What a duffer I am. – Old mate Sep 07 '14 at 06:42