3
$\begingroup$

This is a follow up question to Paradox of the closed form Fibonacci generating function

Suppose we have a generating function $F(x)$ for some infinite series $F_n$

$$F(x) = F_0x^0 + F_1x^1 + F_2x^2 + ... + F_nx^n + ...$$

Now I know that further algebra manipulation around $F(x)$ depends on it being a finite number. In other words, $F(x)$ must be convergent for some domain.

Does such a domain always exist? Could it be that $F_n$ grows very fast (being some higher order infinite?) so that $F(x)$ never converges? I asked because I seldom see people discuss convergence of $F(x)$ before using it in deductions.

$\endgroup$
7
  • 5
    $\begingroup$ Take $F_n=n!$ . Of course, the series always converges at $x=0$ $\endgroup$
    – lulu
    Commented Jun 14 at 15:38
  • $\begingroup$ @lulu OK. Totally forgot the trivial answer $0$. But that trivial answer would render $F(x)$ useless, right? I think we need a non-trivial answer to meaningfully apply generating functions. $\endgroup$
    – Lingxi
    Commented Jun 14 at 15:47
  • 2
    $\begingroup$ Not sure what point you are making. "meaningful" is subjective. Even formal power series can be informative. But, sure. it's better if there is some positive radius of convergence, and best if there is a sensible analytic continuation outside the interval of convergence (as is the case for the Fibonacci series). $\endgroup$
    – lulu
    Commented Jun 14 at 15:50
  • 3
    $\begingroup$ In the context of formal power series you can certainly perform many manipulations without regard for if the series converges in the regular sense over some domain. Such computations can actually be useful. Here is an answer that offers some discussion on this. $\endgroup$ Commented Jun 14 at 16:32
  • 3
    $\begingroup$ See Wilf's comprehensive book generatingfunctionology. In only one of the chapters does he consider where the generating function converges. The rest of the time he deals with "formal power series". They are not useless. $\endgroup$
    – GEdgar
    Commented Jun 14 at 21:20

1 Answer 1

12
$\begingroup$

Now I know that further algebra manipulation around $F(x)$ depends on it being a finite number.

Actually it does not! There is a perfectly well-behaved theory of formal power series in which the coefficients can be completely arbitrary and can still be manipulated algebraically (for example added, multiplied, divided, even composed) under very mild hypotheses. Sometimes formal power series can have zero radius of convergence when interpreted as "actual" power series, for example the generating function

$$F(x) = \sum_{n \ge 0} n! x^n$$

of the factorials, which converges only for $x = 0$. The problem here is that $n!$ grows faster than any exponential. Nonetheless this is a perfectly sensible generating function and one can do interesting things with it, such as take its formal logarithm

$$\log F(x) = x + \frac{3}{2} x^2 + \frac{13}{3} x^3 + \frac{71}{4} x^4 + \dots.$$

The coefficients of the logarithm turn out to count something interesting: the coefficient of $x^n$ is $\frac{a_n}{n}$ where $a_n$ is the number of subgroups of index $n$ in the free group $F_2$. This is explained here.

For a reference you can consult Chapter 2 of Wilf's generatingfunctionology (legally freely available at the link).


On the other hand, for more complicated arguments sometimes it is necessary to use "actual" power series, for example if you want to use complex analysis. Then it is necessary to talk about convergence. But typically most generating functions $F(x) = \sum f_n x^n$ in practice have the property that $f_n$ grows at most exponentially, which corresponds to the radius of convergence being nonzero, and then we implicitly work within this radius of convergence. Frequently (but not always) $F(x)$ has some small number of poles and admits an analytic continuation and then we can leave the radius of convergence to do fancy arguments involving contour integrals and so forth. Wilf also discusses this briefly in Chapter 2.

$\endgroup$
4
  • $\begingroup$ A good source devoted to analytic combinatorics is Flajolet and Sedgewick's book on the subject. $\endgroup$ Commented Jun 15 at 1:35
  • $\begingroup$ It's really not easy to get around this. Looks like formal power series has its own manipulation rules despite that it shares the same form/structure with actual power series when written down. On the one hand, with milder hypotheses (do not require convergence), formal power series is more widely applicable than actual series. On the other, when conditions are met (like with convergence guarantee), we can promote and apply actual power series rules which potentially enables us to do more like value evaluation. Is my understanding correct? $\endgroup$
    – Lingxi
    Commented Jun 15 at 4:05
  • $\begingroup$ @Lingxi: I'm not quite sure I've parsed what you've said, but that sounds right. If you have more specific questions you can ask them or see if Wilf answers them. $\endgroup$ Commented Jun 15 at 6:43
  • $\begingroup$ @Lingxi Very good answer from Qiaochu Yuan (+1) ! Moreover, when you need to ensure convergence, it is to be noted that you are not limited to the standard generating function, but you can consider other types of generating functions. For example, when dealing with the sequence $a_n = n!$, whose usual generating function converges only at zero, you may use the exponential generating function instead, namely $F(x) := \sum_{n\ge0} a_n \frac{x^n}{n!}$. $\endgroup$
    – Abezhiko
    Commented Jun 16 at 5:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .