Assume that a rational generating function \(\displaystyle f(z) \over g(z) \), with
- \(f(z)\) and \(g(z)\) relatively prime and
- \(g(0)\ne0\),
- 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
# posted by rot13(Unafba Pune) @ 8:27 PM