How to obtain asymptotic form for sequence, given generating function

Question

Let $a_n$ be the number of ways to obtain the amount of $n$ cents, using a supply of 1-cent coins, 3 types of 2-cent coins, and 4-cent coins. Then, $a_n$ is the coefficient of $x^n$ in $$(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)^3(1+x^4+x^8+\cdots),$$ which equals $$G(x):=\sum_{n \ge 0} a_n x^n = \frac{1}{(1-x)(1-x^2)^3 (1-x^4)}.$$

The text I'm reading briefly mentions that $G(x)$ is analytic in $\mathbb{C}$, apart from poles at $\pm 1, \pm i$, and that the asymptotic form of $a_n$ can be obtained by standard analytic arguments. How exactly is the asymptotic form obtained using analytic arguments?

Answer 1

If the pole of smallest modulus has modulus $r$, then asymptotically $a_n=p(n)r^{-n}$ for some polynomial $p$. If the poles are all simple, the polynomial's a constant, and you just get $Cr^{-n}$ for some constant $C$. In the case in hand, the pole at $1$ has multiplicity 5, so the polynomial has degree 4. $a_n$ should be asymptotic to $Cn^4$ for some constant $C$.

The idea is that if the generating function is, as here, a rational function, then every factor $(1-cx)^k$ in the denominator leads to a summand $A/(1-cx)^k$ in the partial fraction decomposition of the rational function. If $k=1$ then expanding the summand (it's just a geometric series) gives a contribution $Ac^n$ to $a_n$. The dominant contribution comes from the largest $c$, which corresponds to the smallest pole $1/c$. When $k\gt1$ the binomial theorem lets you expand $(1-cx)^{-k}$ and the coefficient you get for $x^n$ is of the form $p(n)c^n$ for some polynomial $p(n)$ of degree $k-1$.