# Analytic Combinatorics for Computing Seeding Probabilities
## 3 Background
### Asymptotic Estimates
Differentiating the expression \(Q(z)=(z_{1}-z)Q_{1}(z)\) shows that \(Q^{\prime}(z_{1})=-Q_{1}(z_{1})\), and thus that \(\beta_{1}=-P(z_{1})/Q^{\prime}(z_{1})\), which concludes the proof. Theorem 2 says that the asymptotic growth of the coefficients of the series expansion of \(A(z)\) is dictated by the singularity with smallest _modulus_, also known as the \"dominant singularity\". An important observation is that the relative error in expression (4) is \(O(|z_{1}/z_{2}|^{k})\), i.e., it decreases exponentially fast as \(k\) increases. The hypotheses of Theorem 2 that there is only one dominant singularity and that it has multiplicity \(1\) are essential. Otherwise, expression (4) does not hold and other asymptotic regimes occur (25) (p. 498, Theorem 4). One can show that the conditions of Theorem 2 are satisfied for the weighted generating functions described in the next section. Importantly, one can also show that, in every case, the root with smallest _modulus_\(z_{1}\) is a real number greater than \(1\). This has the important consequence that we can search \(z_{1}\) in the space of real numbers greater than \(1\) using numerical methods such as Newton-Raphson or bisection. The proofs of these statements are outside the scope of this manuscript; the key observation is that, in all the cases, the body of the transfer graph is irreducible and aperiodic in the sense of Markov chains (14) (p. 341, Definitions V.5 and V.6). One can thus apply (14) (Theorem V.7 p. 434 and statement V.44 p. 358) to the body of the transfer graph, which by Theorem 1 is the sole contributor to the asymptotic growth of the coefficients. We refer the interested reader to (14) (pp. 336-58). Note that expression (7) in the proof of Theorem 2 gives the _exact_ value of the coefficients of the weighted generating function. Computing this expression requires finding all the singularities of the weighted generating function, and all the coefficients \(\beta_{1},\beta_{2,1},\ldots,\beta_{2,12},\ldots,\beta_{n,1},\ldots,\beta_{n, n}\). When all the singularities of the weighted generating function are simple poles, this expression is particularly simple. **Corollary 1**. : _With the hypotheses of Theorem 2, if \(z_{1},z_{2},\ldots,z_{n}\) (the roots of \(Q\)) all have multiplicity \(1\), then_  
\[\frac{1}{(1-z/a)^{n+1}}=\sum_{k=0}^{\infty}\binom{k+n}{n}\frac{z^{k}}{a^{k}}. \tag{5}\]0  
Corollary 1 can be used to find the exact value of the coefficients, but, in general, it is easier to use the weighted generating function to set up a linear recurrence to compute the coefficients (see, for instance, (13) (SS3.3)). **Theorem 3**. : _If the weighted generating function \(A(z)=\sum_{k\geq 0}a_{k}z^{k}\) can be written as the ratio of two polynomials \(P(z)/Q(z)\) with \(\deg(P)<\deg(Q)\), then the sequence \((a_{k})_{k\geq 0}\) satisfies a linear recurrence with constant coefficients._  
Proof. : Say that \(P(z)=p_{0}+p_{1}z+\ldots+p_{m}z^{m}\) and that \(Q(z)=q_{0}+q_{1}z+\ldots+q_{n}z^{n}\). To balance the coefficient of \(z^{0}\) on both sides of the equation \(P(z)=Q(z)\sum_{k\geq 0}a_{k}z^{k}\), we must have \(p_{0}=q_{0}a_{0}\), yielding \(a_{0}=p_{0}/q_{0}\). The coefficient of \(z^{1}\) must also be balanced, which implies \(p_{1}=q_{1}a_{0}+q_{0}a_{1}\), yielding \(a_{1}=(p_{1}-q_{1}a_{0})/q_{0}\). The process is repeated to find the next values of \(a_{k}\). For \(k<n\), the solution depends on the previous values and on the first \(k+1\) coefficients of \(P\) and \(Q\). For \(k\geq n\), we have \(a_{k}=-(q_{1}a_{k-1}+\ldots+q_{n}a_{k-n})/q_{0}\). This is a linear recurrence of order \(n=\deg(Q)\) with constant coefficients, whose initial conditions depend on the coefficients of \(P\).