Analytic Combinatorics to asymptotically estimate the number of objects of size at most n?

Question

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics.

I am quiet curious as how to asymptotically estimate the number of objects of size at most n.

Suppose for example that I specified a combinatorial class $A$. I also computed its generating function $A(z)=\sum\limits_n a_n z^n$. Therefore, studying the singularities of $A(z)$ yields an asymptotic estimate of the coefficient $a_n$, that represents the number of objects of size n.

How can I asymptotically estimate the number of objects of size at most $n$ ($\sum\limits_{k=0}^{n} a_n$)? Ideally, I would seek a combinatorial interpretation that would let me re-use the generating function $A(z)$, but I am drying up! Any thoughts?

Answer 1

If $A(z)$ is the generating function of the class $A$, then $$[z^n] {A(z) \over 1-z} $$ is the number of objects in the class $A$ at most $n$. (Recall $1/(1-z) = 1 + z + z^2 + \cdots$ and think about how multiplication of formal power series works.) You can then use the techniques of Flajolet and Sedgewick's book to get the asymptotics.

Answer 2

Indeed, it does the trick!

B(z) = $A(z) \times \sum\limits_n z^n = \sum\limits_{n} \sum\limits_{k = 0}^n a_k z^n$