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