What is a generating function?

In the answer to this question this series comes up.

Its generating function is $$A(x) = \sum_{k\ge0} \frac{x^{4^k}}{1-x^{4^k}}$$

Which I took to mean the $x$th element of the series is given by $A(x)$

I guess that is not the case. I tried to read the definition of a generating function but it's all Greek to me. Is it simply that $A(x)$ sums to the next possible value in the series, but may not necessarily converge to a value?


In your example, it means $$ \sum_{k=0}^\infty \frac{x^{4^k}}{1-x^{4^k}} = \sum_{n=0}^\infty a_n x^n $$ where $(a_n)$ is the sequence of interest. The function $A(x)$ is the "generating function" for the sequence $(a_n)$.

Expanding, we get $$ A(x) = x+{x}^{2}+{x}^{3}+2\,{x}^{4}+{x}^{5}+{x}^{6}+{x}^{7}+2\,{x}^{8}+{x}^{ 9}+{x}^{10}+{x}^{11}+2{x}^{12}+{x}^{13}+{x}^{14}+{x}^{15}+3{x}^{16 }+{x}^{17}+{x}^{18}+{x}^{19}+2{x}^{20}+{x}^{21}+{x}^{22}+{x}^{23}+2 {x}^{24}+\dots $$ So, for example, $a_{20} = 2$ means that $2$ the coefficient of $x^{20}$. Summing the series is not involved.

| cite | improve this answer | |
  • $\begingroup$ Ok so in the linked question I wanted to input the value 21 into some function and get 2 out, because one less than the 4adic valuation of 64 is 2. Where do I put 21 in to get 2 out? You seem to be saying I generate a power series and the coefficient of $x^{21}$ in that power is 2. Is that correct? And that is useful for some abstract reason but not some simple algebraic one. Or does the series also in some sense sum to the desired value? $\endgroup$ – samerivertwice Jul 20 '17 at 0:46
  • $\begingroup$ I think this is my preferred answer which I'd like to accept but I think I need confirmation I've understood correctly first. $\endgroup$ – samerivertwice Feb 19 '18 at 8:08

Strictly speaking, $\sum_{k\geq 0}\frac{x^{4^k}}{1-x^{4^k}}$ is not a power series, but it can be easily converted into something of the form $\sum_{n\geq 0} a_n x^n$. When $a_n$ is related with the number of objects with weight $n$ in a combinatorial context, we say that the power series $\sum_{n\geq 0}a_n x^n$ is a generating function.

The interesting part of analytic combinatorics comes when we prove that under certain assumptions we can derive the asymptotic behaviour of $a_n$ directly from the behaviour of its generating function.

Generating functions are formal objects, but if some bound of the form $a_n\leq C\cdot M^n$ holds, then $\sum_{n\geq 0}a_n x^n$ is uniformly convergent over any compact set contained in the region $|x|\leq\frac{1}{M}$.

| cite | improve this answer | |
  • $\begingroup$ Correction: "over any compact set contained in the region $|x|\color{blue}{<} \frac{1}{M}$." $\endgroup$ – Trevor Gunn Jul 27 '17 at 14:26

The answer of the question depends on what kind of generating function is used to define the sequence $(a_n)$. It is not the same an ordinary generating function than an exponential generating function, by example.

An ordinary generating function have the usual form of a power series, that is

$$\sum_k a_k x^k$$

and a exponential generating function have a specific power series form

$$\sum_k a_n\frac{x^k}{k!}$$

A generating function can be an analytic function[*] such that it series expansion (ordinary or exponential) generates (hence it name) the sequence of coefficients $a_n$.

By example: the exponential generating function of the Bernoulli numbers is defined by

$$\frac{x}{1-e^x}=\sum_{k=0}^\infty B_k \frac{x^k}{k!}$$

where in this case the coefficients $B_k$ are the Bernoulli numbers.

Other example: the ordinary generating function of the Fibonacci numbers is

$$\frac{x}{1-x-x^2}=\sum_{k=0}^\infty F_k x^k,\quad |x|<1$$

where the coefficients $F_k$ are the numbers (the sequence of) Fibonacci.

For what is useful a generating function? By example: some generating functions can be used to define a recursion for it coefficients $a_n$, you can see it in the free book generatingfunctionology of Wilf in page 22 where it is introduced the procedure "$x D \log$" to define these recursions.

[*]: I dont knew, just Im seeing now in the wikipedia article about generating functions that a generating function can be just formal, so it doesnt necessarily need to be convergent. In this case if the series diverges it (obviously) doesnt represent an analytical function.

| cite | improve this answer | |
  • 1
    $\begingroup$ One memorable moment was when I first saw $1/.998999 = 1.001002003005008013021034055089...$ where Fibonacci numbers appeared from the decimal expansion of a reciprocal. $\endgroup$ – Somos Jul 19 '17 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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