ASYMPTOTIC ANALYSIS OF A CLASS OF

FUNCTIONAL EQUATIONS AND APPLICATIONS

Peter J. Grabner†, Helmut Prodinger and Robert F. Tichy†

Abstract. Flajolet and Richmond have invented a method to solve a large class of divide–and–conquer recursions. The essential part of it is the asymptotic analysis of a certain generating function for z → ∞ by means of the Mellin transform. In this paper this type of analysis is performed for a reasonably large class of generating functions fulfilling a functional equation with polynomial coefficients. As an application, the average life time of a party of N people is computed, where each person advances one step or dies with equal probabilites, and an additional “killer” can kill at any level up to d survivors, according to his probability distribution.

1. Introduction

In [3] Flajolet and Richmond presented an ingenious method to deal with a class of recursions where a typical example looks like

(1.1)  f_{n+d} = 1 + ∑_{k=0}^{n} 2^{−n}\binom{n}{k}(f_{k} + f_{n−k}).

Here, d ≥ 0 is a fixed integer. For d = 0 and d = 1 such recursions (and their solutions!) occur frequently as divide–and–conquer recursions in the Analysis of Algorithms. (See [6] as a general reference on the subject.) However, the new approach allows it for the first time to deal with the cases d = 2, 3, …; it consists of several stages. First, the recursion is translated into the language of exponential generating functions. Then, a related function (sometimes called the Poisson transform) is considered. Then, from its coefficients, an ordinary generating function G(z) is built up. The analytic behaviour of the latter for z → ∞ is then to be analyzed by Mellin transform methods. (This is the heart of the method.) Then, by a substitution, the asymptotic behaviour as z → 1 of the ordinary generating function of the desired numbers f_{n} is found. As the last step, this local information is translated to the asymptotic behaviour of the coefficients by transfer theorems.

The relevant function G(z) fulfills a functional equation

(1.2)  G(z)(1 + z)^{d} = 2z^{d}G (\frac{z}{2}) + P_{0}(z),

where the polynomial P_{0}(z) depends on the starting values.

Typeset by AMS-TEX

†These authors are supported by the Austrian Science Foundation Project P8274-PHY All authors are supported by the Austrian–Hungarian Science Cooperation Program, project 10U3

We devote this paper to the general study of recursions as in (1.2), with general polynomials as factors and “\frac{1}{2}” replaced by an arbitrary parameter 0 < λ < 1.

This is not only interesting by itself, but can be applied in the last section to a stochastic process which is a generalization of one presented in [10]. Although formulated in terms of “recreational mathematics” the recursions describe either average ‘trie’ parameters or the behaviour of an ‘approximate counter’. In order to keep this paper short, we refrain from describing those algorithms and data structures and refer for all computer science algorithms to [6] and [7]. For the Mellin transform, which has proven to be very useful especially in number theory and in theoretical computer science, we refer to [1, chapter 13], [6], [8] and to the survey [4]. We note here that the classical applications of the Mellin transform occur in prime number theory and, more recently, in the analysis of digital problems (cf.

[9] and for a detailed survey see [2]).

Let us recall the fundamental properties of Mellin transform;

(1.3)  f^{∗}(s) = ∫_{0}^{∞} f(x)x^{s−1}dx.

If f(x) is a piece-wise continuous function with

f(x) = O(x^{α}) for x → 0 and f(x) = O(x^{β}) for x → ∞

and α > β then the Mellin transform exists as a holomorphic function in the vertical strip −α < ℜs < −β (“fundamental strip”). Our basic tool is Mellin’s inversion formula

(1.4)  f(x) = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞}f^{∗}(s)x^{−s} ds

for any −α < c < −β. This formula yields a correspondence between the singularities of f^{∗}(s) and the asymptotics of f(x) (cf. [8, chapter 1.5]). This technique is especially useful in the asymptotic analysis of harmonic sums h(x) := ∑_{k} λ_{k}f(a_{k}x) since

(1.5)  h^{∗}(s) = f^{∗}(s) ∑_{k} \frac{λ_{k}}{a_{k}^{s}} .

Thus the Mellin transform of a harmonic sum is the product of a generalized Dirichlet series and the transform of the base function.

In Section 2 we introduce a class of functional equations with polynomial coefficients generalizing (1.2) and perform the asymptotic analysis by the Mellin transform approach. Two cases have to be distinguished: in the first one the main term does not contain an oscillating part (Section 2) and in the second one there are oscillations in the main term (Section 3). Section 4 is devoted to a direct extension of [3]. In the final section this method is applied to analyze a special evolution process where N persons are climbing up an infinite staircase such at each step either a person goes to the next step or the person dies. We compute the average of the maximum lifetime.

ASYMPTOTIC ANALYSIS … 3

2. A Class of Functional Equations

We consider the functional equation

(2.1)  G(z)P_{1}(z) = G(λz)P_{2}(z) + P_{0}(z),

where P_{0}(z) = a_{0} + a_{1}z + ⋯ + a_{d_{0}}z^{d_{0}}, P_{1}(z) = b_{0} + b_{1}z + ⋯ + b_{d_{1}}z^{d_{1}} and P_{2}(z) = c_{0} + c_{1}z + ⋯ + c_{d_{2}}z^{d_{2}} are polynomials of degrees d_{0}, d_{1}, d_{2} (d_{1} ≤ d_{2}, d_{0} ≥ 0), respectively, assume that P_{1} and P_{2} have no non-negative real roots, P_{1}(0) ≠ P_{2}(0) and 0 < λ < 1. Our main result gives an asymptotic expansion for the unique analytic solution of (2.1). Formally iterating the functional equation we get

G(z) = ∑_{n=0}^{∞} P_{0}(λ^{n}z)\frac{P_{2}(z) ⋯ P_{2}(λ^{n−1}z)}{P_{1}(z) ⋯ P_{1}(λ^{n}z)}.

Let now

Q_{1}(z) = ∏_{n=0}^{∞} \frac{1}{b_{0}} P_{1}(λ^{n}z) and Q_{2}(z) = ∏_{n=0}^{∞} \frac{1}{c_{0}} P_{2}(λ^{n}z).

Thus we can write

(2.2)  G(z) = \frac{Q_{2}(z)}{b_{0}Q_{1}(z)} ∑_{n=0}^{∞} P_{0}(λ^{n}z) (\frac{c_{0}}{b_{0}} )^{n} \frac{Q_{1}(λ^{n+1}z)}{Q_{2}(λ^{n}z)}.

Our next step is to establish an asymptotic expansion of G(z) for z → ∞. This will be done by a Mellin-transform technique. Let for the following

(2.3)  \frac{1}{b_{0}} P_{1}(z) = ∏_{k=1}^{r_{1}}(1 + α_{k}z)^{μ_{k}} and \frac{1}{c_{0}} P_{2}(z) = ∏_{k=1}^{r_{2}}(1 + β_{k}z)^{ν_{k}}

(μ_{k} and ν_{k} denoting the multiplicities of the roots) and take the Mellin-transforms of the logarithms of these equations

(log \frac{1}{b_{0}} P_{1})^{∗} (s) = \frac{π}{s sin πs} ∑_{k=1}^{r_{1}} μ_{k}α_{k}^{−s} and (log \frac{1}{c_{0}} P_{2})^{∗} (s) = \frac{π}{s sin πs} ∑_{k=1}^{r_{2}} ν_{k}β_{k}^{−s}

for −1 < ℜs < 0. Observing that log Q_{1} and log Q_{2} are harmonic sums yields

(2.4)

(log Q_{1})^{∗} (s) = \frac{1}{1 − λ^{−s}} \frac{π}{s sin πs} ∑_{k=1}^{r_{1}} μ_{k}α_{k}^{−s} and

(log Q_{2})^{∗} (s) = \frac{1}{1 − λ^{−s}} \frac{π}{s sin πs} ∑_{k=1}^{r_{2}} ν_{k}β_{k}^{−s}.

In order to establish an asymptotic expansion for Q_{1} and Q_{2} we apply Mellin’s inversion formula

(2.5)  log Q_{1}(z) = \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}(log Q_{1})^{∗} (s)z^{−s}ds

(and similarly for Q_{2}). Inserting (2.4) and shifting the line of integration to ℜs = \frac{1}{2} (cf. [8, chapter 1.5]) yields (2.6)

log Q_{1}(z) = ∑_{m∈ℤ} Res_{s=χ_{m}} \frac{1}{λ^{−s} − 1} \frac{π}{s sin πs} ∑_{k=1}^{r_{1}} μ_{k}α_{k}^{−s}z^{−s}+ \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}(log Q_{1})^{∗} (s)z^{−s}ds,

where χ_{m} = \frac{2mπi}{log \frac{1}{λ}} are the roots of 1 − λ^{−s} = 0. Note that for s = 0 we have a triple pole and in the other cases simple poles. Computing residues (and applying Vieta’s rule) we get

Res_{s=0} \frac{1}{1 − λ^{−s}} \frac{π}{s sin πs} ∑_{k=1}^{r_{1}} μ_{k}α_{k}^{−s}z^{−s} = −\frac{d_{1}}{2 log \frac{1}{λ}} log^{2} z − (\begin{matrix}log & \frac{b_{0}}{b_{d_{1}}} \\ log & \frac{1}{λ} \end{matrix} − \frac{d_{1}}{2} ) log z − B,

where

B = \frac{1}{2 log \frac{1}{λ}} ∑_{k=1}^{r_{1}} μ_{k} log^{2} α_{k} − \frac{1}{2} log \frac{b_{0}}{b_{d_{1}}} − \frac{log \frac{1}{λ}}{12} − \frac{π^{2}}{6 log \frac{1}{λ}} .

For the residues at χ_{m} ≠ 0 we obtain

Res_{s=χ_{m}} \frac{1}{1 − λ^{−s}} \frac{π}{s sin πs} ∑_{k=1}^{r_{1}} μ_{k}α_{k}^{−s}z^{−s} = \frac{π}{χ_{m}(log λ) sin πχ_{m}} ∑_{k=1}^{r_{1}} μ_{k}α_{k}^{−χ_{m}}z^{−χ_{m}}.

Thus we have

log Q_{1}(z) = \frac{d_{1}}{2 log \frac{1}{λ}} log^{2} z + (\begin{matrix}log & \frac{b_{0}}{b_{d_{1}}} \\ log & \frac{1}{λ} \end{matrix} − \frac{d_{1}}{2} ) log z + B + φ_{1} (\frac{log z}{log \frac{1}{λ}} ) + O (z^{− \frac{1}{2}} ) ,

where φ_{1}(u) is a continuous periodic function of period 1, whose Fourier expansion is given by

(2.7)  φ_{1}(u) = − ∑_{m∈ℤ\\{0\}} \frac{π}{χ_{m}(log λ) sin πχ_{m}} ∑_{k=1}^{r_{1}} μ_{k}α_{k}^{χ_{m}}e^{2πimu}.

Similar calculations yield the asymptotic expansion for Q_{2}:

log Q_{2}(z) = \frac{d_{2}}{2 log \frac{1}{λ}} log^{2} z + (\begin{matrix}log & \frac{c_{0}}{c_{d_{2}}} \\ log & \frac{1}{λ} \end{matrix} + \frac{d_{2}}{2} ) log z + C + φ_{2} (\frac{log z}{log \frac{1}{λ}} ) + O (z^{− \frac{1}{2}} ) ,

where

C = \frac{1}{2 log \frac{1}{λ}} ∑_{k=1}^{r_{2}} ν_{k} log^{2} β_{k} − \frac{1}{2} log \frac{c_{0}}{c_{d_{2}}} − \frac{log \frac{1}{λ}}{12} − \frac{π^{2}}{6 log \frac{1}{λ}}

and φ_{2}(u) is a continuous periodic function of period 1, whose Fourier expansion is given by

(2.8)  φ_{2}(u) = − ∑_{m∈\\{0\}} \frac{π}{χ_{m}(log λ) sin πχ_{m}} ∑_{k=1}^{r_{2}} ν_{k}β_{k}^{χ_{m}}e^{2πimu}.

Setting Φ(u) = exp(C − B + φ_{2}(u) − φ_{1}(u)), A = \frac{d_{2} − d_{1}}{2 log \frac{1}{λ}}, L = \begin{matrix}log & \frac{c_{0}b_{d_{1}}}{c_{d_{2}} b_{0}} \\ log & \frac{1}{λ} \end{matrix} and

observing the rate of growth of the transforms in (2.4), we derive

(2.9)  \frac{Q_{2}(z)}{Q_{1}(z)} = \{ \begin{matrix}z^{L}Φ (\frac{log z}{log \frac{1}{λ}} ) (1 + O(z^{− \frac{1}{2}} )) & if d_{1} = d_{2} \\ e^{A log^{2} z}z^{L+ \frac{d_{2}−d_{1}}{2}} Φ (\frac{log z}{log \frac{1}{λ}} ) (1 + O(z^{− \frac{1}{2}} )) & if d_{1} < d_{2} \end{matrix}

for z → ∞ inside an angular region | arg z| ≤ δ < δ_{0} = π − min_{k}(| arg α_{k}|, | arg β_{k}|). As above we obtain

(2.10)  \frac{Q_{1}(λz)}{Q_{2}(z)} = \{ \begin{matrix}\frac{b_{d_{1}}}{b_{0}λ^{d_{1}}} z^{−L−d_{1}} \frac{1}{Φ (\frac{log z}{log \frac{1}{λ}} )} (1 + O(z^{− \frac{1}{2}} )) & if d_{1} = d_{2} \\ e^{−A log^{2} z+O(log z)} & if d_{1} < d_{2} \end{matrix}

for | arg z| ≤ δ < δ_{0}.

Let us first consider the case d_{1} = d_{2} = d and a_{0} ≠ 0. Then we need |c_{0}| < |b_{0}| to ensure convergence in (2.2). Setting

(2.11)  H(z) = ∑_{n=0}^{∞} P_{0}(λ^{n}z) (\frac{c_{0}}{b_{0}} )^{n} \frac{Q_{1}(λ^{n+1}z)}{Q_{2}(λ^{n}z)},

and observing that this is a harmonic sum yields for its Mellin transform

(2.12)  H^{∗}(s) = \frac{b_{0}}{b_{0} − c_{0}λ^{−s}} (P_{0}(z)\frac{Q_{1}(λz)}{Q_{2}(z)})^{∗} (s).

Notice that this Mellin transform only exists, if −L + d_{0} − d < 0, since ‘the order at ∞’ has to be smaller than ‘the order at 0’. From our asymptotic expansion (2.10) we want to extract some information on the singularities of the transformed harmonic sum H^{∗}(s). The fundamental strip of this transform is

0 < ℜs < − max (−L + d_{0} − d, \begin{matrix}log & \frac{c_{0}}{b_{0}} \\ log & \frac{1}{λ} \end{matrix} ) .

Thus we have to distinguish two cases. First we consider the case occurring in our applications in Section 3, i.e.

(2.13)  b_{d}λ^{d_{0}} ≤ c_{d}λ^{d}.

This is the case where the singularities originate directly from the individual summands (in the other case the singularities are caused by the harmonic summation and a special example of this type was extensively studied by Flajolet and Richmond [3]). For b_{d}λ^{d_{0}} < c_{d}λ^{d}, by (2.10) we have

(2.14)  H(z) = \frac{b_{d}^{2}}{(b_{d} − c_{d}λ^{d−d_{0}})b_{0}λ^{d}} z^{−L−d+d_{0}} \frac{1}{Φ (\frac{log z}{log \frac{1}{λ}} )} (1 + O(z^{−ε})) ,

where ε is a suitable positive number. Combining (2.14) and (2.9) the fluctuation Φ cancels out in the asymptotics of G(z) and we obtain

(2.15)  G(z) = \frac{b_{d}^{2}a_{d_{0}}}{b_{0}^{2}(b_{d} − c_{d}λ^{d−d_{0}})λ^{d}} z^{d_{0}−d} (1 + O(z^{−ε})) .

For b_{d}λ^{d_{0}} = c_{d}λ^{d} the function H^{∗}(s) has double poles at −L−d+d_{0} +χ_{m}. Thus the asymptotic formula (2.14) has to be replaced by

(2.16)  H(z) = (\frac{log z}{log \frac{1}{λ}} \frac{1}{Φ (\frac{log z}{log \frac{1}{λ}} )} + Ψ (\frac{log z}{log \frac{1}{λ}} )) z^{−L−d+d_{0}} (1 + O(z^{−ε})) .

Combining (2.16) and (2.9) we derive

(2.17)  G(z) = (\frac{1}{b_{0}} \frac{log z}{log \frac{1}{λ}} + \frac{1}{b_{0}} Ψ (\frac{log z}{log \frac{1}{λ}} )) z^{d_{0}−d} (1 + O(z^{−ε})) ,

where Ψ is an unspecified periodic fluctuation.

Until now we have restricted ourselves to the case a_{0} ≠ 0. In general let ℓ be defined by P_{0}(z) = z^{ℓ}P̃_{0}(z) with a polynomial P̃_{0}(z) such that P̃_{0}(0) ≠ 0. Then the equation corresponding to (2.11) is

(2.18)  H(z) = z^{ℓ} ∑_{n=0}^{∞} P̃_{0}(λ^{n}z) (\frac{λ^{ℓ}c_{0}}{b_{0}} )^{n} \frac{Q_{1}(λ^{n+1}z)}{Q_{2}(λ^{n}z)}.

The sum in this expression is exactly of the type considered above and therefore we need the condition λ^{ℓ}|c_{0}| < |b_{0}| to ensure convergence. Thus we obtain the same asymptotic expansions also in the general case ℓ ≥ 0.

Summing up what we have proved until now yields

Theorem 1. Let G(z) be the unique analytic solution of a functional equation of type (2.1) and let ℓ be the smallest number such that a_{ℓ} ≠ 0. Furthermore assume the additional properties d_{1} = d_{2} = d, λ^{ℓ}|c_{0}| < |b_{0}| and b_{d}λ^{d_{0}} ≤ c_{d}λ^{d}. Then G(z) has an asymptotic expansion for z → ∞ (| arg z| ≤ δ < π −min_{k}(| arg α_{k}|, | arg β_{k}|) of the form

G(z) = \{ \begin{matrix}\frac{b_{d}^{2}a_{d_{0}}}{b_{0}^{2}(b_{d} − c_{d}λ^{d−d_{0}})λ^{d}} z^{d_{0}−d} (1 + O(z^{−ε})) & if b_{d}λ^{d_{0}} < c_{d}λ^{d} \\ (\frac{1}{b_{0}} \frac{log z}{log \frac{1}{λ}} + \frac{1}{b_{0}} Ψ (\frac{log z}{log \frac{1}{λ}} )) z^{d_{0}−d} (1 + O(z^{−ε})) & if b_{d}λ^{d_{0}} = c_{d}λ^{d}, \end{matrix}

where ε is a suitable positive number and Ψ denotes a continuous periodic function of period 1.

Remark 1. We note that in the case covered by Theorem 1 the periodic fluctuations do not occur in the main term.

3. Fluctuations in the Main Term

First we consider functional equations of type (2.1) with d_{1} = d_{2} = d satisfying the condition b_{d}λ^{d_{0}} > c_{d}λ^{d} converse to (2.13). In the previous section the convergence of the Fourier series for φ_{1} and φ_{2} was immediate. In the case treated now we establish a preparatory lemma generalizing Lemma 5 in [3], from which the convergence of the corresponding Fourier series can be deduced. In the following let v denote the maximal order of a zero of the entire function Q_{2}. Note that v is finite, but may be larger than max_{k} ν_{k}.

Lemma 1. Let F (z) = P_{0}(z)\frac{Q_{1}(λz)}{Q_{2}(z)}. Then the Mellin transform F^{∗}(s) admits the representation

\frac{π}{sin πs} (E_{0}(λ^{−s}) + (s − 1)E_{1}(λ^{−s}) + ⋯ + (s − 1) ⋯ (s − v + 1)E_{v−1}(λ^{−s})) ,

where the E_{i}’s are entire functions. Thus for σ > 0

(3.1)  |F^{∗}(σ + it)| = O (|t|^{v−1}e^{−π|t|}) as |t| → ∞.

Proof. Proceeding as in [3] let

J(s) = ∫_{H} F (z)(−z)^{s−1}dz,

where H denotes a Hankel contour that goes from +∞ − i0, circles around 0 clockwise and returns to +∞ + i0. Then a standard argument (cf. [11]) yields J(s) = 2i sin πsF^{∗}(s). Now we want to evaluate the loop integral by residues. For this purpose we have to know polynomial upper bounds for F (z), which follow from

(3.2)  |∏_{n=0}^{∞} (\frac{1 + αλ^{n}z}{1 + βλ^{n}z} )| ≤ K_{1}|z|^{K_{2}} for |1 + βλ^{n}z| ≥ ε,

where α, β and \frac{λ}{4} > ε > 0 are given numbers and K_{1} and K_{2} are positive constants depending on those numbers and on λ.

For proving this assertion let γ = max\{1, 2|α|, 2|β|\} and n_{0} = ⌊\frac{log 2γz}{log \frac{1}{λ}} ⌋+1. Thus

we have |λ^{n_{0}}zγ| ≤ \frac{1}{2}. We split the product (3.2) into two parts n < n_{0} and n ≥ n_{0}. The second product can be estimated by taking logarithms

| ∑_{n=n_{0}}^{∞} log (\frac{1 + αλ^{n}z}{1 + βλ^{n}z} )| =

| ∑_{n=n_{0}}^{∞} ((α − β)zλ^{n} − (α^{2} − β^{2})\frac{z^{2}}{2} λ^{2n} + (α^{3} − β^{3})\frac{z^{3}}{3} λ^{3n} ± ⋯)| ≤

≤ γ|z|λ^{n_{0}} \frac{1}{1 − λ} + γ^{2}|z|^{2}λ^{2n_{0}} \frac{1}{1 − λ^{2}} + ⋯ ≤ \frac{1}{1 − λ}.

For estimating the first part of the product in the region |1 + βλ^{n}z| ≥ ε for n = 0, …, n_{0} − 1 we note that the function f(w) = \frac{1+αw}{1+βw} is continuous on the compact subregion |1 + βw| ≥ ε of the Riemannian sphere, and hence attains its maximum M = M(ε, α, β, λ) ≥ 1. Thus we obtain

|∏_{n=0}^{∞} (\frac{1 + αλ^{n}z}{1 + βλ^{n}z} )| ≤ M^{n_{0}}e^{\frac{1}{1−λ}} ≤ K_{1}|z|^{K_{2}},

and (3.2) is proved.

Observing that \frac{Q_{1}}{Q_{2}} can be decomposed into finitely many factors of the type (3.2) we get get a polynomial upper bound for F (z) in the region |1 + β_{k}λ^{n}z| ≥ ε (k = 1, …, r_{2} and n = 0, 1, …). Notice that ε is chosen small enough that arbitrarily large circles centered at the origin are contained in this region. Again by a standard argument we derive

J(s) = 2πi ∑_{k=1}^{r_{2}} ∑_{n=0}^{∞} Res_{z=− \frac{λ^{−n}}{β_{k}}} F (z)(−z)^{s−1}

for ℜs < σ_{0} < 0. Next we calculate the residues and observe that the maximum order of the poles is v. Let us consider a pole −\frac{λ^{−n}}{β_{k}} of multiplicity b and set

X_{k,n}(z) = F (z)(1 + β_{k}λ^{n}z)^{b}.

First we have for w = z + \frac{λ^{−n}}{β_{k}} (3.3)

(−z)^{s−1} = λ^{−n(s−1)}β_{k}^{−s+1} (1 + \frac{(1 − s)}{1!}(β_{k}λ^{n}w) + \frac{(1 − s)(2 − s)}{2!}(β_{k}λ^{n}w)^{2} + ⋯) .

Expanding X_{k,n}(−\frac{λ^{−n}}{β_{k}} + w) around w = 0 we get

X_{k,n} (−\frac{λ^{−n}}{β_{k}} + w) =

P_{0}(z)Q_{1}(λz) ∏ (1 − \frac{β_{l}}{β_{k}} λ^{m−n})^{−1} ∏ (1 + \frac{w}{\frac{λ^{−m}}{β_{l}} − \frac{λ^{−n}}{β_{k}}} )^{−1} = ∑_{j=0}^{∞} Λ_{j}(k, n)w^{j},

where the products range over all (l, m) such that β_{l}λ^{m} ≠ β_{k}λ^{n}. We observe

(3.4)  Λ_{j}(k, n) = O (λ^{\frac{n(n+1)}{2} +jn}η_{k}^{−j})

with an absolute O-constant, where η_{k} is the minimal distance of \frac{1}{β_{k}} to the other roots of Q_{2}.

Multiplying (3.3) and the expansion of X_{k,n} yields for the coefficient of w^{b−1}

λ^{−n(s−1)}β_{k}^{−s+1} ∑_{j=0}^{b−1} Λ_{b−j−1}(k, n)\frac{(1 − s)(2 − s) ⋯ (j − s)}{j!}.

Each residue provides one term in the power series expansion of the E_{i}(λ^{−s}). Because of the upper bound (3.4) the power series expansion of E_{i} is hyperexponentially convergent and E_{i} is an entire function. □

Now we are able to treat functional equations of type (2.1) with equal degrees and fluctuations in the main term.

Theorem 2. Let G(z) be the unique analytic solution of a functional equation of type (2.1) and let ℓ be the smallest number such that a_{ℓ} ≠ 0. Furthermore assume the additional properties d_{1} = d_{2} = d, λ^{ℓ}|c_{0}| < |b_{0}| and b_{d}λ^{d_{0}} > c_{d}λ^{d}. Then G(z) has an asymptotic expansion for z → ∞ (| arg z| ≤ δ < π −min_{k}(| arg α_{k}|, | arg β_{k}|) of the form

G(z) = z^{M}Ψ_{1} (\frac{log z}{log \frac{1}{λ}} ) (1 + O(z^{−ε})) ,

where ε is a suitable positive number, M = \begin{matrix}log & \frac{b_{d}}{c_{d}} \\ log & \frac{1}{λ} \end{matrix} and Ψ_{1} some continuous periodic

fluctuation (the Fourier expansion of which is discussed in the proof).

Proof. We apply Mellin’s inversion formula to (2.12) and observe that the first singularities encountered when shifting the line of integration to the right originate from the factor \frac{b_{0}}{b_{0}−c_{0}λ^{−s}}. Notice that evaluations of the E_{i}’s of Lemma 1 at the poles are constants and that the Fourier expansion of the arising fluctuation is exponentially convergent because of the estimate (3.1). The fluctuation Ψ_{1} is obtained by multiplying with the periodic function \frac{1}{b_{0}} Φ as in (2.9). The proof is completed by multiplying with the first case in the asymptotic formula (2.9). □

Up to now we have only considered polynomials P_{1} and P_{2} of equal degree. What remains for a complete asymptotic analysis of functional equations of type (2.1) is the case d_{1} < d_{2}. (We note here that the converse case d_{1} > d_{2} cannot be treated by the Mellin transform approach.)

Remark 1. Lemma 1 remains true in the case d_{1} < d_{2}. The only problem is to find a polynomial upper bound for \frac{Q_{1}(λz)}{Q_{2}(z)}. This product can be split into products of type (3.2) and d_{2} − d_{1} additional linear factors in the denominator. For these additional factors we easily find the polynomial lower bound Kε^{(d_{2}−d_{1}) log z}.

By the same reasoning as above we obtain

Theorem 3. Let G(z) be the unique analytic solution of a functional equation of type (2.1) with d_{1} < d_{2}. Then G(z) has an asymptotic expansion for z → ∞ (| arg z| ≤ δ < π − min_{k}(| arg α_{k}|, | arg β_{k}|) of the form

G(z) = e^{A log^{2} z}z^{M+ \frac{d_{2}−d_{1}}{2}} Ψ_{2} (\frac{log z}{log \frac{1}{λ}} ) (1 + O(z^{−ε})) ,

where ε is a suitable positive number, A = \frac{d_{2} − d_{1}}{2 log \frac{1}{λ}}, M = \begin{matrix}log & \frac{b_{d}}{c_{d}} \\ log & \frac{1}{λ} \end{matrix} and Ψ_{2} some

continuous periodic fluctuation.

4. The Flajolet–Richmond Case

In [3] Flajolet and Richmond analyze a tree-partitioning process in which n elements split into d at the root of a tree (d is a design parameter), the rest going recursively into two subtrees with a binomial probability distribution. They prove an asymptotic formula for the expected number f_{n} of non-empty nodes in such a random tree, by studying the generating function G(z) = ∑_{n≥0} g_{n}z^{n} where f_{n} = ∑_{k=0}^{n} \binom{n}{k}g_{k}. G(z) satisfies the functional equation

(4.1)  G(z)(1 + z)^{d} = 2z^{d}G (\frac{z}{2}) + P_{0}(z),

where P_{0} is a polynomial of degree d. This is not a functional equation of type (2.1) since c_{0} = 0. Thus the above theorems cannot be applied. In the following we extend our general approach to the case c_{0} = 0, d_{1} = d_{2} = d which covers the special case (4.1) (in the case b_{0} = 0 there is no analytic solution, for d_{1} ≠ d_{2} the Mellin tansform approach cannot be applied).

Theorem 4. Let G(z) be the unique analytic solution of the functional equation

G(z)P_{1}(z) = G(λz)P_{2}(z) + P_{0}(z) (0 < λ < 1),

where P_{1}(z) = b_{0} + b_{1}z + ⋯ + b_{d}z^{d}, P_{2}(z) = c_{κ}z^{κ} + ⋯ + c_{d}z^{d} (with b_{0} ≠ 0, c_{κ} ≠ 0, κ > 0) are polynomials of equal degree d with no positive real roots and let P_{0}(z) = a_{0} + a_{1}z + ⋯ + a_{d_{0}}z^{d_{0}} ≢ 0. Then G(z) has an asymptotic expansion for z → ∞, (| arg z| ≤ δ < π − min_{k}(| arg α_{k}|, | arg β_{k}|) of the form

G(z) = \{ \begin{matrix}z^{M+d_{0}−d}Ψ_{3} (\frac{log z}{log \frac{1}{λ}} ) (1 + O(z^{−ε})) & if M < d − d_{0} \\ (\frac{a_{d}}{c_{d}} \frac{log z}{log \frac{1}{λ}} + Ψ_{4} (\frac{log z}{log \frac{1}{λ}} )) z^{d_{0}−d} (1 + O(z^{−ε})) & if M = d − d_{0} \\ \frac{a_{d_{0}}}{c_{d}} z^{d_{0}−d} (1 + O(z^{−ε})) & if M > d − d_{0}, \end{matrix}

where ε is a suitable positive number, M = \begin{matrix}log & \frac{b_{d}}{c_{d}} \\ log & \frac{1}{λ} \end{matrix} and Ψ_{3}, Ψ_{4} some continuous

periodic fluctuations.

Proof. Using the substitution t = \frac{1}{z} we can rewrite the explicit formula for G(z)

G(\frac{1}{t}) = t^{d−d_{0}} ∑_{n=0}^{∞} P̄_{0}(λ^{−n}t)λ^{n(d_{0}−d)} \frac{P̄_{2}(t) ⋯ P̄_{2}(λ^{−(n−1)}t)}{P̄_{1}(t) ⋯ P̄_{1}(λ^{−n}t)},

where P̄_{0}(z) = z^{d_{0}}P_{0}(\frac{1}{z}), P̄_{1}(z) = z^{d}P_{1}(\frac{1}{z}) and P̄_{2}(z) = z^{d}P_{2}(\frac{1}{z}) are polynomials with deg P̄_{1} = d > d − κ = deg P̄_{2}. Proceeding as in Section 2 we set

Q̄_{1}(t) = ∏_{n=0}^{∞} \frac{1}{b_{d}} P̄_{1}(λ^{n}t)

Q̄_{2}(t) = ∏_{n=0}^{∞} \frac{1}{c_{d}} P̄_{2}(λ^{n}t)

and obtain

(4.2)  G(\frac{1}{t}) = t^{d−d_{0}} \frac{Q̄_{1}(λt)}{c_{d}Q̄_{2}(λt)} ∑_{n=0}^{∞} P̄_{0}(λ^{−n}t)λ^{n(d_{0}−d)} \frac{Q̄_{2}(λ^{−(n−1)}t)}{Q̄_{1}(λ^{−n}t)}.

Let F (t) = P̄_{0}(t)\frac{Q̄_{2}(λt)}{Q̄_{1}(t)}. Notice that Lemma 1 can be applied to this function.

Furthermore we have for t → ∞ F (t) ≤ exp ( − η log^{2} t + O(log z)) with some constant η > 0 and F (0) = a_{d_{0}}. Thus the fundamental strip of F^{∗}(s) is 0 < ℜs < ∞. Denoting the sum in (4.2) by H(t) we obtain

(4.3)  H^{∗}(s) = F^{∗}(s)\frac{b_{d}}{b_{d} − c_{d}λ^{d_{0}−d+s}}

with the fundamental strip max(0, −M − d + d_{0}) < ℜs < ∞. This yields the desired asymptotic expansion for H(t), t → 0 which implies the expansion for G(z), z → ∞. □

Remark 2. The computer science problem originally considered by Flajolet and Richmond is covered by the first alternative of Theorem 4.

5. An Evolution Process with Killer

We consider the following stochastic process. N persons (starting at level 1) are climbing up an infinite staircase. At every step for each person there are two possibilities of equal probability: (i) go to the next step (ii) the person dies. After this at any level an outside killer kills j persons with given probability p_{j} (0 ≤ j ≤ d, d is fixed; p_{0} ≠ 0). (If there are only < j persons available, all of them are killed.) This situation is a generalization of [10] where the case d = 1 was discussed (emerging from some computer science problems).

We ask for the expectation C_{N} of the maximum lifetime. To this end, we introduce the probability generating functions F_{N}(z) where the coefficient of z^{k} is the probability that the maximum level of N persons is k. We have the recursion (N ≥ 1)

(5.1)  F_{N}(z) = z ∑_{k=1}^{N} 2^{−N} \binom{N}{k}[p_{0}F_{k}(z) + ⋯ + p_{k−d}F_{k−d}] + z2^{−N}.

(Observe that 2^{−N} \binom{N}{k} is the probability that k out of N people have made it to the next level. The variable z marks the level, and the effect of the killer is described by [p_{0}F_{k}(z) + ⋯ + p_{k−d}F_{k−d}].) The cumbersone special cases when there are less persons than the killer wants to kill can be avoided by setting F_{i}(z) = z for i ≤ 0.

Now the expectations C_{N} are obtained by differentiating the F_{N}(z) and then evaluating at z = 1. Doing this we obtain the recursion (N ≥ 1)

(5.2)  C_{N} = 1 + ∑_{j=0}^{d} p_{j} ∑_{k=1}^{N} 2^{−N} \binom{N}{k}C_{k−j},

and the starting values C_{i} = 1 for i ≤ 0.

Setting up the exponential generating function C(z) = ∑_{N≥0} C_{N}z^{N}/N! we find

(5.3)  C(z) = e^{z} − e^{z/2} + ∑_{j=0}^{d} p_{j}e^{z/2} ∑_{k≥0} C_{k−j} \frac{(z/2)^{k}}{k!} .

Now it is customary (in order to get an easier equation) to set D(z) = e^{−z}C(z) (the “Poisson transform”). For simplicity, we replace z by 2z, multiply the equation by e^{−z} and differentiate it d times, yielding

(5.4)  e^{z} ∑_{k=0} \binom{d}{k}2^{k}D^{(k)}(2z) = e^{z} + ∑_{j=0}^{d} p_{d−j}C^{(j)}(z).

Furthermore, we can express (by Leibniz’ rule) C^{(j)}(z) by e^{z} ∑_{i=0}^{j} \binom{j}{i}D^{(i)}(z), so that we obtain after another multiplication by e^{−z}

(5.5)  ∑_{j=0}^{d} \binom{d}{j}2^{j}D^{(j)}(2z) = 1 + ∑_{j=0}^{d} p_{d−j} ∑_{i=0}^{j} \binom{j}{i}D^{(i)}(z).

Now set D(z) = ∑_{N≥0} D_{N}z^{N}/N! and G(z) = ∑_{N≥0} D_{N}z^{N}. Comparing coefficients we find

(5.6)  ∑_{j=0}^{d} \binom{d}{j}2^{N+j}D_{N+j} = δ_{N,0} + ∑_{j=0}^{d} p_{d−j} ∑_{i=0}^{j} \binom{j}{i}D_{N+i}.

Finally, we multiply by (\frac{z}{2})^{N+d} and sum up for all N ≥ 0 to obtain

(5.7)  G(z)(1 + \frac{z}{2})^{d} = G(\frac{z}{2})P_{2}(z) + P_{0}(z)

with

(5.8)  P_{2}(z) = ∑_{j=0}^{d} p_{d−j} ∑_{i=0}^{j} \binom{j}{i}(\frac{z}{2})^{d−i} = ∑_{j=0}^{d} p_{j}(\frac{z}{2})^{j}(1 + \frac{z}{2})^{d−j}

and (5.9)

P_{0}(z) = (\frac{z}{2})^{d} + ∑_{j=0}^{d} \binom{d}{j}(\frac{z}{2})^{d−j} ∑_{i=0}^{j−1} D_{i}z^{i} − ∑_{j=0}^{d} p_{d−j} ∑_{i=0}^{j} \binom{j}{i}(\frac{z}{2})^{d−i} ∑_{h=0}^{i−1} D_{h}(\frac{z}{2})^{h}.

We want to apply Theorem 4 and find d_{0} = d, a_{d} = b_{d} = c_{d} = 2^{−d} and thus M = 0. Hence the second alternative of Theorem 4 gives

(5.10)  G(z) = log_{2} z + Ψ_{4} (log_{2} z) + O(z^{−ε}).

This leads to

(5.11)  \begin{aligned}F (z) & = ∑_{N≥0} C_{N}z^{N} = \frac{1}{1 − z} G(\frac{z}{1 − z} ) \\ & = \frac{1}{1 − z} log_{2} \frac{1}{1 − z} + \frac{1}{1 − z} Ψ_{4}( log_{2} \frac{1}{1 − z} ) + O((1 − z)^{−1+ε}), \end{aligned}

for z → 1. Now, since

[z^{N}]\frac{1}{1 − z} log \frac{1}{1 − z} = 1 + \frac{1}{2} + ⋯ + \frac{1}{N} = log N + γ + O(\frac{1}{N} ),

singularity analysis (cf. [5]) leads to Theorem 5.

Theorem 5. The average level C_{N} that a party of N people with an additional killer will reach is asymptotically given by

C_{N} = log_{2} N + φ( log_{2} N) + O(N^{−ε})

where φ(x) is a periodic function with period 1. Its Fourier coefficients could be given in principle by evaluating an appropriate Mellin integral at the points 2kπi/ log 2, k ∈ ℤ. φ(x) depends on the probability distribution (p_{0}, …, p_{d}) (with p_{d} ≠ 0) of the killer.

References

1. T.M.Apostol, Introduction to Analytic Number Theory, Springer, New York, 1984.

2. P.Flajolet, P. Grabner, P.Kirschenhofer, H.Prodinger and R.F.Tichy, Mellin Transforms and Asymptotics: Digital Sums, Theoretical Computer Science (to appear).

3. P.Flajolet and L.B.Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms 3 (1992), 305–320.

4. P. Flajolet, M. Régnier and R. Sedgewick, Some Uses of the Mellin Integral Transform in the Analysis of Algorithms, Combinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Springer, New York, 1985.

5. P.Flajolet and A.Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math. 3 (1990), 216–240.

6. P.Flajolet and J.Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A “Algorithms and Complexity”, North-Holland, 1990, pp. 431–524.

7. D.E.Knuth, The Art of Computer Science Vol.3, Addison-Wesley, Reading, MA, 1973.

8. H.M. Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992.

9. J.-L. Mauclaire and L. Murata, On q-Additive Functions, II, Proc. Japan Acad. 59 (1983), 441–444.

10. H.Prodinger, How to Advance on a Staircase by Coin Flippings,, Proceedings “Fibonacci Numbers and Applications 5” (1992) (to appear).

11. E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press,