We now want to discuss the nature of the generating growth function AG(X). We are interested in this function as an actual complex analytic function, not just a formal power series, and therefore we will write in this chapter the variable as z, not X. In the examples opening this book, A(z) was usually a rational function. Assuming that this is the case, we write A(z) = P(z)/Q(z), for some polynomials P(z) = ∑pnzn and Q(z) = ∑qnzn, rewrite this as A(z)Q(z) = P(z), and then rewrite this equation as the infinite set of equations ∑a(k)qn-k = pn (where we take pn = 0 for n bigger than the degree of P, and similarly for Q). We see that rationality of A(z) is equivalent to the existence of linear recurrence relations for the numbers a(n). We will refer to a group with a rational generating growth function as a rational group.

Theorem 15.1Let G be a rational group (relative to some set of generators). Then the coefficients of the growth-generating function can be taken as integers, and the growth of G is either polynomial or exponential.

Proof Using the above notation, consider the recursion formulas for a(n) as a system of linear equations for pn and qn. Since the a(n)s are integers, the system has a rational solution, and multiplying by a common denominator leads to an integral solution.