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.
Best Answer
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.