Assume that a rational generating function \(\displaystyle f(z) \over g(z) \), with

1. \(f(z)\) and \(g(z)\) relatively prime and
2. \(g(0)\ne0\),
3. has a unique pole \(\displaystyle 1 \over \beta\) of smallest modulus (that is, \(\displaystyle g({1 \over \alpha})=0\) and \(\alpha\ne\beta\) implies that \(\displaystyle |{1 \over \alpha}|>|{1 \over \beta}|\), or \(|\alpha|<|\beta|\)).

Then, if the multiplicity of \(\displaystyle 1 \over \beta\) is \(\nu\), we have a powerful theorem for precise approximation

\[ \begin{aligned} \color{red}{[z^n]{f(z)\over g(z)}\sim C\beta^{n}n^{\nu-1}}\quad\hbox{where}\quad \color{red}{C=\nu{(-\beta)^\nu f(1/\beta)\over g^{(\nu)}(1/\beta)}} \qquad &\text{!} \\ \end{aligned} \]

Example:

\[ \begin{aligned} a_n &= 5_{n-1} - 6a_{n-2} &\text{for } n \ge 2 \text{ with } a_0=0 \text{ and } a_1=1 \\ a_n &= 5_{n-1} - 6a_{n-2} + \delta_{n1} &\text{make recurrence work for all } n \\ A(z) &= 5z A(z) - 6z^2 A(z) + z & \text{multiply by }z^n \text{ and sum on }n \\ A(z) &= \frac{z}{1 - 5z + 6z^2} \\ &= \frac{z}{(z-{1 \over 2})(z-{1 \over 3})} \\ \end{aligned} \]

The root closest to zero in the denominator is \(\displaystyle \frac{1}{3}\), which is therefore the "smallest modulus" with a multiplicity of \(1\) (ie as a root \(\displaystyle \frac{1}{3}\) appears only once).

\[ \begin{aligned} {1 \over \beta} &= {1 \over 3} \\ v &= 1 \\ g'(z) &= -5 + 12z \\ g'({1 \over 3}) &= -5 + {12 \over 3} = -1 \\ C &= \frac{(-3)^1 f({1 \over 3})}{-1} \\ &= \frac{(-3) \cdot {1 \over 3}}{-1} = 1 \\ [z^n]A(z) &\equiv [z^n]\frac{z}{1 - 5z + 6z^2} \equiv a_n \thicksim 3^n \\ \end{aligned} \]

Source: Analysis of Algorithm