\magnification 1200
\input amstex
\documentstyle{amsppt}
\define\({\left(}
\define\){\right)}
\define\Res{\mathop{\roman{Res}}\limits}
\define\ph{\varphi}
\topmatter
\rightheadtext{Asymptotic Analysis $\ldots$}
\leftheadtext{Peter J. Grabner, Helmut Prodinger and Robert F. Tichy}
\title
Asymptotic Analysis of a Class of Functional Equations and Applications
\endtitle
\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\to\infty$ 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.
\endabstract
\author Peter J. Grabner\dag, Helmut Prodinger and Robert F. Tichy\dag\endauthor
\thanks\dag These authors are supported by the Austrian Science Foundation
Project P8274-PHY\hfill\break
All authors are supported by the Austrian--Hungarian Science Cooperation 
Program, project 10U3\endthanks
\endtopmatter
\document
\heading 1. Introduction\endheading

In \cite{3} Flajolet and Richmond presented an ingenious method to deal
with a class of recursions where a typical example looks like
$$
f_{n+d}=1+\sum_{k=0}^n2^{-n}\binom nk \big(f_k+f_{n-k}\big).\tag 1.1
$$
Here, $d\ge0$ is a fixed integer. For $d=0$ and $d=1$ such recursions
(and their solutions!) occur frequently as {\sl divide--and--conquer\/}
recursions in the {\sl Analysis of Algorithms\/}. (See \cite{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,\dots$; it consists of several stages. First, the
recursion is translated into the language of exponential generating functions.
Then, a related function (sometimes called the {\sl Poisson transform\/})
is considered. Then, from its coefficients, an {\sl ordinary generating
function\/} $G(z)$ is built up. The analytic behaviour of the latter for
$z\to\infty$ is then to be analyzed by {\sl Mellin transform\/} methods.
(This is the heart of the method.) Then, by a substitution, 
the asymptotic behaviour as $z\to1$ 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 {\sl transfer theorems}.

The relevant function $G(z)$ fulfills a functional equation
$$
G(z)(1+z)^d=2z^dG\left(\frac z2\right)+P_0(z),\tag1.2
$$
where the polynomial $P_0(z)$ depends on the starting values.

We devote this paper to the general study of recursions as in \thetag{1.2},
with general polynomials as factors and ``$\frac12$'' replaced by an
arbitrary parameter $0<\lambda<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 \cite{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 \cite{6} and
\cite{7}. For the Mellin transform,
which has proven to be very useful especially in number theory and in 
theoretical computer
science, we refer to \cite{1, chapter 13}, \cite{6}, \cite{8} and to the survey 
\cite{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. \cite{9} and for a detailed survey see \cite{2}).

Let us recall the fundamental properties of Mellin transform;
$$f^*(s)=\int_0^\infty f(x)x^{s-1}dx.\tag1.3$$
If $f(x)$ is a piece-wise continuous function with
$$f(x)=O(x^\alpha)\quad\text{for }x\to0\quad\text{and}
\quad f(x)=O(x^\beta)\quad\text{for }x\to\infty$$
and $\alpha>\beta$ then the Mellin transform exists as a holomorphic function in 
the vertical strip $-\alpha<\Re s<-\beta$
(``fundamental strip''). Our basic tool is Mellin's inversion formula
$$f(x)=\frac1{2\pi i}\int\limits_{c-i\infty}^{c+i\infty}f^*(s)x^{-s}\,ds
\tag1.4$$
for any $-\alpha<c<-\beta$. This formula yields a correspondence between 
the singularities of $f^*(s)$ and the asymptotics
of $f(x)$ (cf. \cite{8, chapter 1.5}). This technique is especially useful 
in the asymptotic analysis of {\sl harmonic sums}
$h(x):=\sum_k\lambda_kf(a_kx)$ since
$$h^*(s)=f^*(s)\sum_k\frac{\lambda_k}{a_k^s}.\tag1.5$$
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 \thetag{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 \cite{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.
\heading 2. A Class of Functional Equations\endheading
We consider the functional equation
$$G(z)P_1(z)=G(\lambda z)P_2(z)+P_0(z),\tag2.1$$
where $P_0(z)=a_0+a_1z+\cdots+a_{d_0}z^{d_0}$, 
$P_1(z)=b_0+b_1z+\cdots+b_{d_1}z^{d_1}$ and 
$P_2(z)=c_0+c_1z+\cdots+c_{d_2}z^{d_2}$
are polynomials of degrees $d_0,d_1,d_2$ ($d_1\leq d_2$, $d_0\geq0$), 
respectively, assume that $P_1$ and $P_2$ have no non-negative
real roots, $P_1(0)\not=P_2(0)$ and $0<\lambda<1$.
Our main result gives an asymptotic expansion for the unique analytic solution 
of \thetag{2.1}.
Formally iterating the functional equation we get
$$G(z)=\sum_{n=0}^\infty P_0(\lambda^nz)\frac{P_2(z)\cdots 
P_2(\lambda^{n-1}z)}{P_1(z)\cdots P_1(\lambda^nz)}.$$
Let now
$$Q_1(z)=\prod_{n=0}^\infty \frac 1{b_0}P_1(\lambda^nz)\quad\text{and}\quad
Q_2(z)=\prod_{n=0}^\infty \frac 1{c_0}P_2(\lambda^nz).$$
Thus we can write
$$G(z)=\frac{Q_2(z)}{b_0Q_1(z)}\sum_{n=0}^\infty P_0(\lambda^nz)\(\frac 
{c_0}{b_0}\)^n\frac{Q_1(\lambda^{n+1}z)}{Q_2(\lambda^nz)}.\tag2.2$$

Our next step is to establish an asymptotic expansion of $G(z)$ for 
$z\to\infty$. This will be done by a Mellin-transform technique.
Let for the following
$$\frac1{b_0}P_1(z)=\prod_{k=1}^{r_1}(1+\alpha_kz)^{\mu_k}\quad\text{and}
\quad\frac1{c_0}P_2(z)=\prod_{k=1}^{r_2}(1+\beta_kz)^{\nu_k}\tag2.3$$
($\mu_k$ and $\nu_k$ denoting the multiplicities of the roots) and 
take the Mellin-transforms of the logarithms of these equations
$$\(\log\frac1{b_0}P_1\)^*(s)=\frac\pi{s\sin\pi 
s}\sum_{k=1}^{r_1}\mu_k\alpha_k^{-s}\quad\text{and 
}\(\log\frac1{c_0}P_2\)^*(s)=\frac\pi{s\sin\pi s}\sum_{k=1}^{
r_2}\nu_k\beta_k^{-s}$$
for $-1<\Re s<0$. Observing that $\log Q_1$ and $\log Q_2$ are harmonic sums 
yields
$$\aligned&\(\log Q_1\)^*(s)=\frac1{1-\lambda^{-s}}\frac\pi{s\sin\pi 
s}\sum_{k=1}^{r_1}\mu_k\alpha_k^{-s}\quad\text{and }\cr
&\(\log Q_2\)^*(s)=\frac1{1-\lambda^{-s}}\frac\pi{s\sin\pi 
s}\sum_{k=1}^{r_2}\nu_k\beta_k^{-s}.\endaligned\tag2.4$$
In order to establish an asymptotic expansion for $Q_1$ and $Q_2$ we apply 
Mellin's inversion formula
$$\log Q_1(z)=\frac1{2\pi 
i}\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}\(\log 
Q_1\)^*(s)z^{-s}ds\tag2.5$$
(and similarly for $Q_2$). Inserting \thetag{2.4} and shifting the line of 
integration to $\Re s=\frac12$ (cf. \cite{8, chapter 1.5})
yields
$$\log Q_1(z)=\sum_{m\in\Bbb 
Z}\Res_{s=\chi_m}\frac1{\lambda^{-s}-1}\frac\pi{s\sin\pi 
s}\sum_{k=1}^{r_1}\mu_k\alpha_k^{-s}z^{-s}+
\frac1{2\pi i}\int\limits_{\frac12-i\infty}^{\frac12+i\infty}\(\log 
Q_1\)^*(s)z^{-s}ds,\tag2.6$$
where $\chi_m=\frac{2m\pi i}{\log\frac1\lambda}$ are the roots of 
$1-\lambda^{-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}\frac1{1-\lambda^{-s}}\frac\pi{s\sin\pi 
s}\sum_{k=1}^{r_1}\mu_k\alpha_k^{-s}z^{-s}=
-\frac{d_1}{2\log\frac1\lambda}\log^2z
-\(\frac{\log\frac{b_0}{b_{d_1}}}{\log\frac1\lambda}-\frac{d_1}2\)\log z-B,$$
where
$$B=\frac1{2\log\frac1\lambda}\sum_{k=1}^{r_1}\mu_k\log^2
\alpha_k-\frac12\log\frac{b_0}{b_{d_1}}-\frac{\log\frac1\lambda}{12}-
\frac{\pi^2}{6\log\frac1\lambda}.$$
For the residues at $\chi_m\not=0$ we obtain
$$\Res_{s=\chi_m}\frac1{1-\lambda^{-s}}\frac\pi{s\sin\pi 
s}\sum_{k=1}^{r_1}\mu_k\alpha_k^{-s}z^{-s}
=\frac\pi{\chi_m(\log\lambda)\sin\pi\chi_m}
\sum_{k=1}^{r_1}\mu_k\alpha_k^{-\chi_m}z^{-\chi_m}.$$
Thus we have
$$\log 
Q_1(z)=\frac{d_1}{2\log\frac1\lambda}\log^2z
+\(\frac{\log\frac{b_0}{b_{d_1}}}{\log\frac1\lambda}-\frac{d_1}2\)\log z+B+
\ph_1\(\frac{\log z}{\log\frac1\lambda}\)+O\(z^{-\frac12}\),$$
where $\ph_1(u)$ is a continuous periodic function of period $1$, whose Fourier 
expansion is given by
$$\ph_1(u)=-\sum_{m\in\Bbb 
Z\setminus\{0\}}\frac\pi{\chi_m(\log\lambda)\sin\pi\chi_m}\sum_{k=1}^{r_1}\mu_k
\alpha_k^{\chi_m}e^{2\pi imu}.\tag2.7$$
Similar calculations yield the asymptotic expansion for $Q_2$:
$$\log 
Q_2(z)=\frac{d_2}{2\log\frac1\lambda}\log^2z
+\(\frac{\log\frac{c_0}{c_{d_2}}}{\log\frac1\lambda}+\frac{d_2}2\)\log z+C+
\ph_2\(\frac{\log z}{\log\frac1\lambda}\)+O\(z^{-\frac12}\),$$
where
$$C=\frac1{2\log\frac1\lambda}\sum_{k=1}^
{r_2}\nu_k\log^2\beta_k-\frac12\log\frac{c_0}{c_{d_2}}-\frac{\log\frac1\lambda}{12}-
\frac{\pi^2}{6\log\frac1\lambda}$$
and $\ph_2(u)$ is a continuous periodic function of period $1$, whose Fourier 
expansion is given by
$$\ph_2(u)=-\sum_{m\in\Bbb 
\setminus\{0\}}\frac\pi{\chi_m(\log\lambda)\sin\pi\chi_m}\sum_{k=1}^{r_2}\nu_k
\beta_k^{\chi_m}e^{2\pi imu}.\tag2.8$$

Setting $\Phi(u)=\exp(C-B+\ph_2(u)-\ph_1(u))$, 
$A=\dfrac{d_2-d_1}{2\log\frac1\lambda}$, 
$L=\dfrac{\log\frac{c_0b_{d_1}}{c_{d_2}b_0}}{\log\frac1\lambda}$
and observing the rate of growth of the transforms in \thetag{2.4}, we derive
$$\frac{Q_2(z)}{Q_1(z)}=\cases z^L\Phi\(\dfrac{\log z}
{\log\frac1\lambda}\)\(1+O(z^{-\frac12})\)&\text{if $d_1=d_2$}\\
e^{A\log^2z}z^{L+\frac{d_2-d_1}2}\Phi\(\dfrac{\log z}
{\log\frac1\lambda}\)\(1+O(z^{-\frac12})\)&\text{if $d_1<d_2$}\endcases\tag2.9$$
for $z\to\infty$ inside an angular region $|\arg 
z|\leq\delta<\delta_0=\pi-\min_k(|\arg\alpha_k|,|\arg\beta_k|)$.
As above we obtain
$$\frac{Q_1(\lambda z)}{Q_2(z)}=\cases 
\dfrac{b_{d_1}}{b_0\lambda^{d_1}}z^{-L-d_1}\dfrac1{\Phi\(\frac{\log z}
{\log\frac1\lambda}\)}\(1+O(z^{-\frac12})\)&\text{if 
$d_1=d_2$}\\
e^{-A\log^2z+O(\log z)}&\text{if $d_1<d_2$}\endcases\tag2.10$$
for $|\arg z|\leq\delta<\delta_0$.

Let us first consider the case $d_1=d_2=d$ and $a_0\not=0$. Then we need 
$|c_0|<|b_0|$ to ensure convergence in \thetag{2.2}. Setting
$$H(z)=\sum_{n=0}^\infty P_0(\lambda^nz)\(\frac 
{c_0}{b_0}\)^n\frac{Q_1(\lambda^{n+1}z)}{Q_2(\lambda^nz)},\tag2.11$$
and observing that this is a harmonic sum yields for its Mellin transform
$$H^*(s)=\frac{b_0}{b_0-c_0\lambda^{-s}}\(P_0(z)\frac{Q_1(\lambda 
z)}{Q_2(z)}\)^*(s).\tag2.12$$
Notice that this Mellin transform only exists, if $-L+d_0-d<0$, since 
`the order at $\infty$' has to be smaller than `the order at
$0$'. From our asymptotic expansion \thetag{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<\Re s<-\max\(-L+d_0-d,\frac{\log\frac{c_0}{b_0}}{\log\frac1\lambda}\).$$
Thus we have to distinguish two cases. First we consider the case occurring in 
our applications in Section 3, i.e.
$$b_d\lambda^{d_0}\leq c_d\lambda^d.\tag2.13$$
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 \cite{3}).
For $b_d\lambda^{d_0}<c_d\lambda^d$, by \thetag{2.10} we have
$$H(z)=\frac{b_d^2}{(b_d-c_d\lambda^{d-d_0})b_0\lambda^d}z^{-L-d+d_0}\frac1{\Phi
\(\frac{\log z}{\log\frac1\lambda}\)}\(1+O(z^{-\varepsilon})\),\tag2.14$$
where $\varepsilon$ is a suitable positive number.
Combining \thetag{2.14} and \thetag{2.9} the fluctuation $\Phi$ cancels out in 
the asymptotics of $G(z)$ and we obtain
$$G(z)=\frac{b_d^2a_{d_0}}{b_0^2(b_d-c_d\lambda^{d-d_0})\lambda^d}
z^{d_0-d}\(1+O(z^{-\varepsilon})\).\tag2.15$$ 

For $b_d\lambda^{d_0}=c_d\lambda^d$ the function
 $H^*(s)$ has double poles at $-L-d+d_0+\chi_m$. Thus the asymptotic formula 
\thetag{2.14} has to
be replaced by
$$H(z)=\(\frac{\log z}{\log\frac1\lambda}\frac1{\Phi\(\frac{\log 
z}{\log\frac1\lambda}\)}+\Psi\(\frac{\log z}{\log\frac1\lambda}\)\)
z^{-L-d+d_0}\(1+O(z^{-\varepsilon})\).\tag2.16$$
Combining \thetag{2.16} and \thetag{2.9} we derive
$$G(z)=\(\frac1{b_0}\frac{\log z}{\log\frac1\lambda}+\frac1{b_0}\Psi\(\frac{\log 
z}{\log\frac1\lambda}\)\)z^{d_0-d}\(1+O(z^{-\varepsilon})\),\tag2.17$$
where $\Psi$ is an unspecified periodic fluctuation.

Until now we have restricted ourselves to the case $a_0\not=0$. 
In general let $\ell$ be defined by $P_0(z)=z^\ell\tilde P_0(z)$ with
a polynomial $\tilde P_0(z)$ such that $\tilde P_0(0)\not=0$. 
Then the equation corresponding to \thetag{2.11} is
$$H(z)=z^\ell\sum_{n=0}^\infty \tilde P_0(\lambda^nz)\(\frac {\lambda^\ell 
c_0}{b_0}\)^n\frac{Q_1(\lambda^{n+1}z)}{Q_2(\lambda^nz)}.\tag2.18$$
The sum in this expression is exactly of the type considered above and therefore 
we need the condition $\lambda^\ell|c_0|<|b_0|$ to
ensure convergence. Thus we obtain the same asymptotic expansions also in the 
general case $\ell\geq0$.

Summing up what we have proved  until now yields

\proclaim{Theorem 1} Let $G(z)$ be the unique analytic solution of a functional 
equation of type \thetag{2.1} and let $\ell$ be the
smallest number such that $a_\ell\not=0$. Furthermore assume 
the additional properties $d_1=d_2=d$, $\lambda^\ell|c_0|<|b_0|$ and
$b_d\lambda^{d_0}\leq c_d\lambda^d$.
Then $G(z)$ has an asymptotic expansion for $z\to\infty$ 
\ $(|\arg z|\leq\delta<\pi-\min_k(|\arg\alpha_k|,|\arg\beta_k|)$ of the form
$$G(z)=\cases \dfrac{b_d^2a_{d_0}}{b_0^2(b_d-c_d\lambda^{d-d_0})\lambda^d}
z^{d_0-d}\(1+O(z^{-\varepsilon})\)
&\text{{\rm if} $b_d\lambda^{d_0}<c_d\lambda^d$}\\
\(\dfrac1{b_0}\dfrac{\log z}{\log\frac1\lambda}+
\dfrac1{b_0}\Psi\(\dfrac{\log z}{\log\frac1\lambda}\)\)
z^{d_0-d}\(1+O(z^{-\varepsilon})\)&\text{{\rm if} $b_d\lambda^{d_0}
=c_d\lambda^d$,}\endcases$$
where $\varepsilon$ is a suitable positive number and $\Psi$ denotes a 
continuous periodic function of period $1$.
\endproclaim
\proclaim{Remark 1} We note that in the case covered by Theorem~1 the periodic 
fluctuations do not occur in the main term.
\endproclaim
\heading 3. Fluctuations in the Main Term\endheading
First we consider functional equations of type \thetag{2.1} with $d_1=d_2=d$ 
satisfying the condition $b_d\lambda^{d_0}>c_d\lambda^d$
converse to \thetag{2.13}. In the previous section the convergence of the 
Fourier series for $\ph_1$ and $\ph_2$ was immediate.
In the case treated now we establish a preparatory lemma generalizing 
Lemma~5 in \cite{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\nu_k$.
\proclaim{Lemma 1} Let $F(z)=P_0(z)\frac{Q_1(\lambda z)}{Q_2(z)}$. Then the 
Mellin transform $F^*(s)$ admits the representation
$$\frac\pi{\sin\pi 
s}\(E_0(\lambda^{-s})+(s-1)E_1(\lambda^{-s})+\cdots+(s-1)\cdots(s-v+1)E_{v-1}
(\lambda^{-s})\),$$
where the $E_i$'s are entire functions. Thus for $\sigma>0$
$$|F^*(\sigma+it)|=O\(|t|^{v-1}e^{-\pi|t|}\)\quad\text{as 
}|t|\to\infty.\tag3.1$$
\endproclaim
\demo{Proof} Proceeding as in \cite{3} let
$$J(s)=\int_\Cal H F(z)(-z)^{s-1}dz,$$
where $\Cal H$ denotes a Hankel contour that goes from $+\infty-i0$, circles 
around $0$ clockwise and returns to $+\infty+i0$.
Then a standard argument (cf. \cite{11}) yields $J(s)=2i\sin\pi 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
$$\left|\prod_{n=0}^\infty\(\frac{1+\alpha\lambda^nz}{1+\beta\lambda^nz}\)
\right|\leq K_1|z|^{K_2}\quad\text{for}\quad
|1+\beta\lambda^nz|\geq\varepsilon,\tag3.2$$
where $\alpha$, $\beta$ and $\frac\lambda4>\varepsilon>0$ are given numbers and 
$K_1$ and $K_2$ are positive constants depending on those numbers and
on $\lambda$.

For proving this assertion let $\gamma=\max\{1,2|\alpha|,2|\beta|\}$ and 
$n_0=\left\lfloor\frac{\log2\gamma z}{\log\frac1\lambda}\right\rfloor+1$.
Thus we have $|\lambda^{n_0}z\gamma|\leq\frac12$. We split the product 
\thetag{3.2} into two parts $n<n_0$ and $n\geq n_0$.
The second product can be estimated by taking logarithms
$$\align&\left|\sum_{n=n_0}^\infty 
\log\(\frac{1+\alpha\lambda^nz}{1+\beta\lambda^nz}\)\right|=\cr
&\left|\sum_{n=n_0}^\infty\((\alpha-\beta)z\lambda^n-
(\alpha^2-\beta^2)\frac {z^2}2\lambda^{2n}+(\alpha^3-\beta^3)\frac{z^3}3
\lambda^{3n}\pm\cdots\)\right|\leq\cr
&\le\gamma 
|z|\lambda^{n_0}\frac1{1-\lambda}+\gamma^2|z|^2\lambda^{2n_0}\frac1{1-\lambda^2}
+\cdots\leq\frac1{1-\lambda}.\endalign$$
For estimating the first part of the product in the region 
$|1+\beta\lambda^nz|\geq\varepsilon$ for 
$n=0,\ldots,n_0-1$ we note that the
function $f(w)=\frac{1+\alpha w}{1+\beta w}$  is continuous on the compact 
subregion $|1+\beta w|\geq\varepsilon$ of the Riemannian
sphere, and hence attains its maximum $M=M(\varepsilon, 
\alpha,\beta,\lambda)\geq1$. Thus we obtain
$$\left|\prod_{n=0}^\infty\(\frac{1+\alpha\lambda^nz}{1+\beta\lambda^nz}\)\right
|\leq M^{n_0}e^{\frac1{1-\lambda}}\leq K_1|z|^{K_2},$$
and \thetag{3.2} is proved.

Observing that $\frac{Q_1}{Q_2}$ can be decomposed into finitely many factors of 
the type \thetag{3.2} we get get a polynomial upper
bound for $F(z)$ in the region $|1+\beta_k\lambda^nz|\geq\varepsilon$ 
($k=1,\ldots,r_2$ and $n=0,1,\ldots$). Notice that $\varepsilon\ $
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\pi 
i\sum_{k=1}^{r_2}\sum_{n=0}^\infty\Res_{z=-\frac{\lambda^{-n}}{\beta_k}}F(z)(-z)
^{s-1}$$
for $\Re s<\sigma_0<0$. Next we calculate
the residues and observe that the maximum order of the poles is $v$. Let us 
consider a pole $-\frac{\lambda^{-n}}{\beta_k}$ of
multiplicity $b$ and set
$$X_{k,n}(z)=F(z)(1+\beta_k\lambda^nz)^b.$$
First  we have for $w=z+\frac{\lambda^{-n}}{\beta_k}$
$$(-z)^{s-1}=\lambda^{-n(s-1)}\beta_k^{-s+1}\(1+\frac{(1-s)}{1!}(\beta_k\lambda^
nw)+\frac{(1-s)(2-s)}{2!}(\beta_k\lambda^nw)^2+\cdots\).\tag3.3$$
Expanding $X_{k,n}(-\frac{\lambda^{-n}}{\beta_k}+w)$ around $w=0$ we get
$$\align &X_{k,n}\(-\frac{\lambda^{-n}}{\beta_k}+w\)=\cr
&P_0(z)Q_1(\lambda z)\prod\(1-\frac{\beta_l}{\beta_k}\lambda^{m-n}\)^{-1}
\prod\(1+\frac 
w{\frac{\lambda^{-m}}{\beta_l}-\frac{\lambda^{-n}}{\beta_k}}\)^{-1}=
\sum_{j=0}^\infty\Lambda_j(k,n)w^j,\endalign$$
where the products range over all $(l,m)$ such that 
$\beta_l\lambda^m\not=\beta_k\lambda^n$. We observe
$$\Lambda_j(k,n)=O\(\lambda^{\frac{n(n+1)}2+jn}\eta_k^{-j}\)\tag3.4$$
with an absolute $O$-constant, where $\eta_k$ is the minimal distance of 
$\frac1{\beta_k}$ to the other roots of $Q_2$.

Multiplying \thetag{3.3} and the expansion of $X_{k,n}$ yields for the 
coefficient of $w^{b-1}$
$$\lambda^{-n(s-1)}\beta_k^{-s+1}\sum_{j=0}^{b-1}\Lambda_{b-j-1}(k,n)\frac{(1-s)
(2-s)\cdots(j-s)}{j!}.$$
Each residue provides one term in the power series expansion of the 
$E_i(\lambda^{-s})$. Because of the upper bound
\thetag{3.4} the power series expansion of $E_i$ is hyperexponentially 
convergent and $E_i$ is an entire function.
\qed\enddemo
Now we are able to treat functional equations of type \thetag{2.1} with equal 
degrees and fluctuations in the main term.

\proclaim{Theorem 2} Let $G(z)$ be the unique analytic solution of a 
functional equation of type \thetag{2.1} and let $\ell$ be the
smallest number such that $a_\ell\not=0$. 
Furthermore assume the additional properties $d_1=d_2=d$, 
$\lambda^\ell|c_0|<|b_0|$ and
$b_d\lambda^{d_0}>c_d\lambda^d$.
Then $G(z)$ has an asymptotic expansion for $z\to\infty\ $ 
$(|\arg z|\leq\delta<\pi-\min_k(|\arg\alpha_k|,|\arg\beta_k|)$ of the form
$$G(z)=z^M\Psi_1\(\frac{\log z}{\log\frac1\lambda}\)
\(1+O(z^{-\varepsilon})\),$$
where $\varepsilon$ is a suitable positive number, 
$M=\dfrac{\log\frac{b_d}{c_d}}{\log\frac1\lambda}$ and $\Psi_1$ some continuous
periodic fluctuation (the Fourier expansion of which is discussed in the proof).
\endproclaim
\demo{Proof} We apply Mellin's inversion formula to \thetag{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\lambda^{-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 \thetag{3.1}. The fluctuation $\Psi_1$ is obtained by 
multiplying with the periodic function $\frac1{b_0}\Phi$
as in \thetag{2.9}. The proof is completed by multiplying with the first case in 
the asymptotic formula \thetag{2.9}.
\qed\enddemo
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 \thetag{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.)
\proclaim{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(\lambda z)}{Q_2(z)}$. This product can be split into products of type 
\thetag{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\varepsilon^{(d_2-d_1)\log z}$.
\endproclaim
By the same reasoning as above we obtain

\proclaim{Theorem 3} Let $G(z)$ be the unique analytic solution 
of a functional equation of type \thetag{2.1} with $d_1<d_2$.
Then $G(z)$ has an asymptotic expansion for $z\to\infty$ 
$(|\arg z|\leq\delta<\pi-\min_k(|\arg\alpha_k|,|\arg\beta_k|)$ of the form
$$G(z)=e^{A\log^2z}z^{M+\frac{d_2-d_1}2}
\Psi_2\(\frac{\log z}{\log\frac1\lambda}\)\(1+O(z^{-\varepsilon})\),$$
where $\varepsilon$ is a suitable positive number, 
$A=\dfrac{d_2-d_1}{2\log\frac1\lambda}$, 
$M=\dfrac{\log\frac{b_d}{c_d}}{\log\frac1\lambda}$
and $\Psi_2$ some continuous periodic fluctuation.
\endproclaim



\heading 4. The Flajolet--Richmond Case\endheading
In \cite{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)=\sum_{n\ge0}g_nz^n$ where $f_n=\sum_{k=0}^n\binom nkg_k$. $G(z)$ satisfies 
the functional equation
$$G(z)(1+z)^d=2z^dG\(\frac z2\)+P_0(z),\tag4.1$$
where $P_0$ is a polynomial of degree $d$. This is not a functional equation of 
type \thetag{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 \thetag{4.1} (in the case $b_0=0$ there is no 
analytic solution, for $d_1\not=d_2$ the Mellin tansform
approach cannot be applied).

\proclaim{Theorem 4} Let $G(z)$ be the unique analytic solution of the 
functional equation
$$G(z)P_1(z)=G(\lambda z)P_2(z)+P_0(z)\qquad(0<\lambda<1),$$
where $P_1(z)=b_0+b_1z+\cdots+b_dz^d$, $P_2(z)=c_\kappa z^\kappa+\cdots+c_dz^d$ 
(with $b_0\not=0$, $c_\kappa\not=0$, $\kappa>0$)
are polynomials of equal degree $d$ with no positive real roots and let
$P_0(z)=a_0+a_1z+\cdots+a_{d_0}z^{d_0}\not\equiv0$.
Then $G(z)$ has an asymptotic expansion for $z\to\infty$, 
$(|\arg z|\leq\delta<\pi-\min_k(|\arg\alpha_k|,|\arg\beta_k|)$ of the form
$$
G(z)=\cases z^{M+d_0-d}\Psi_3\(\frac{\log z}{\log\frac1\lambda}\)
\(1+O(z^{-\varepsilon})\)&\text{if $M<d-d_0$}\cr
\(\dfrac{a_d}{c_d}\dfrac{\log z}{\log\frac1\lambda}
+\Psi_4\(\frac{\log z}{\log\frac1\lambda}\)\)z^{d_0-d}\(1+O(z^{-\varepsilon})
\)&\text{if $M=d-d_0$}\cr
\frac{a_{d_0}}{c_d}z^{d_0-d}\(1+O(z^{-\varepsilon})\)&\text{if 
$M>d-d_0$,}\endcases$$
where $\varepsilon$ is a suitable positive number, 
$M=\dfrac{\log\frac{b_d}{c_d}}{\log\frac1\lambda}$ and $\Psi_3$, $\Psi_4$
some continuous periodic fluctuations.
\endproclaim
\demo{Proof} Using the substitution $t=\frac1z$ we can rewrite the
explicit formula for $G(z)$
$$G(\frac1t)=t^{d-d_0}\sum_{n=0}^\infty\bar 
P_0(\lambda^{-n}t)\lambda^{n(d_0-d)}\frac{\bar P_2(t)\cdots\bar 
P_2(\lambda^{-(n-1)}t)}
{\bar P_1(t)\cdots\bar P_1(\lambda^{-n}t)},$$
where $\bar P_0(z)=z^{d_0}P_0(\frac1z)$, $\bar P_1(z)=z^dP_1(\frac1z)$ and $\bar 
P_2(z)=z^dP_2(\frac1z)$ are polynomials with
$\deg\bar P_1=d>d-\kappa=\deg\bar P_2$. Proceeding as in Section~2 we set
$$\align &\bar Q_1(t)=\prod_{n=0}^\infty\frac1{b_d}\bar P_1(\lambda^n t)\cr
&\bar Q_2(t)=\prod_{n=0}^\infty\frac1{c_d}\bar P_2(\lambda^n t)\endalign$$
and obtain
$$G(\frac1t)=t^{d-d_0}\frac{\bar Q_1(\lambda t)}{c_d\bar Q_2(\lambda 
t)}\sum_{n=0}^\infty\bar P_0(\lambda^{-n}t)\lambda^{n(d_0-d)}
\frac{\bar Q_2(\lambda^{-(n-1)}t)}{\bar Q_1(\lambda^{-n}t)}.\tag4.2$$
Let $F(t)=\bar P_0(t)\frac{\bar Q_2(\lambda t)}{\bar Q_1(t)}$. 
Notice that Lemma~1 can be applied to this function. Furthermore we
have for $t\to\infty$ $F(t)\leq\exp\big(-\eta\log^2t+O(\log z)\big)$ 
with some constant $\eta>0$ and $F(0)=a_{d_0}$. Thus the fundamental
strip of $F^*(s)$ is $0<\Re s<\infty$. Denoting the sum in \thetag{4.2} by 
$H(t)$ we obtain
$$H^*(s)=F^*(s)\frac{b_d}{b_d-c_d\lambda^{d_0-d+s}}\tag4.3$$
with the fundamental strip $\max(0,-M-d+d_0)<\Re s<\infty$.
This yields the desired asymptotic expansion for $H(t)$, $t\to0$ which implies 
the expansion for $G(z)$, $z\to\infty$.
\qed\enddemo
\proclaim{Remark 2} The computer science problem originally considered by 
Flajolet and Richmond is covered by the first alternative
of Theorem~4.\endproclaim



\heading 5. An Evolution Process with Killer\endheading
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\leq j\leq d$, $d$ is fixed; $p_0\neq0$). (If there are only $<j$ persons
available, all of them are killed.) 
This situation is a generalization of \cite{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\ge1$)
$$
F_N(z)=z\sum_{k=1}^N2^{-N}\binom Nk
\Big[p_0F_k(z)+\dots+p_{k-d}F_{k-d}\Big]+z2^{-N}.\tag 5.1
$$
(Observe that $2^{-N}\binom Nk$ 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_0F_k(z)+\dots+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\le0$.

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\ge1$)
$$C_N=1+\sum_{j=0}^dp_j\sum_{k=1}^N2^{-N}{N\choose k}C_{k-j},\tag 5.2$$
and the starting values $C_i=1$ for $i\le0$.

Setting up the exponential generating function $C(z)=\sum_{N\ge0}
C_Nz^N/N!$ we find
$$
C(z)=e^z-e^{z/2}+\sum_{j=0}^dp_je^{z/2}\sum_{k\ge0}C_{k-j}\frac{(z/2)^k}{k!}.
\tag 5.3$$
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
$$
e^z\sum_{k=0}\binom dk2^kD^{(k)}(2z)=e^z+\sum_{j=0}^dp_{d-j}C^{(j)}(z).
\tag 5.4
$$
Furthermore, we can express (by Leibniz' rule) $C^{(j)}(z)$ by $e^z\sum_{i=0}^j
\binom jiD^{(i)}(z)$, so that we obtain after another
 multiplication  by $e^{-z}$
$$\sum_{j=0}^d\binom dj2^jD^{(j)}(2z)=1+\sum_{j=0}^dp_{d-j}
\sum_{i=0}^j\binom ji D^{(i)}(z).\tag 5.5$$
Now set $D(z)=\sum_{N\ge0}D_Nz^N/N!$ and $G(z)=\sum_{N\ge0}D_Nz^N$.
Comparing coefficients we find
$$
\sum_{j=0}^d\binom dj2^{N+j}D_{N+j}=\delta_{N,0}+\sum_{j=0}^dp_{d-j}
\sum_{i=0}^j\binom ji D_{N+i}.\tag 5.6
$$
Finally,  we multiply by $(\frac{z}{2})^{N+d}$ and sum up for all $N\ge0$
to obtain
$$
G(z)\Big(1+\frac z2\Big)^d=G\big(\frac z2\big)P_2(z)+P_0(z)\tag5.7
$$
with
$$
P_2(z)=\sum_{j=0}^dp_{d-j}\sum_{i=0}^j\binom ji \big(\frac z2\big)^{d-i}
=\sum_{j=0}^dp_j\big(\frac z2\big)^j\Big(1+\frac z2\Big)^{d-j}\tag 5.8
$$
and
$$
P_0(z)=\big(\frac z2\big)^d+\sum_{j=0}^d\binom dj \big(\frac z2\big)^{d-j}
\sum_{i=0}^{j-1}D_iz^i-
\sum_{j=0}^dp_{d-j}\sum_{i=0}^j\binom ji \big(\frac z2\big)^{d-i}
\sum_{h=0}^{i-1}D_h \big(\frac z2\big)^h.\tag5.9
$$

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
$$
G(z)=\log_2z+\Psi_4\left(\log_2z\right)+O(z^{-\varepsilon}).\tag 5.10
$$
This leads to
$$\aligned
F(z)&=\sum_{N\ge0}C_Nz^N=\frac{1}{1-z}G\Big(\frac{z}{1-z}\Big)\\
&=\frac{1}{1-z}\log_2\frac{1}{1-z}+\frac{1}{1-z}\Psi_4\Big(
\log_2\frac{1}{1-z}\Big)+O\big((1-z)^{-1+\varepsilon}\big),
\endaligned
\tag 5.11
$$
for $z\to1$. Now, since
$$
[z^N]\frac{1}{1-z}\log\frac{1}{1-z}=1+\frac12+\dots+\frac1N
=\log N+\gamma+O\big(\frac 1N\big),
$$
{\sl singularity analysis\/} (cf. \cite{5}) leads to Theorem 5.

\proclaim {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_2N+\varphi\big(\log_2N\big)+O\big(N^{-\varepsilon}\big)
$$
where $\varphi(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\pi i/\log2$, $k\in\Bbb Z$. $\varphi(x)$
depends on the probability distribution $(p_0,\dots,p_d)$ $\quad(
\text{with } p_d\ne0)$
of the killer.
\endproclaim

\Refs

\ref \no 1\by T.M.Apostol\book Introduction to Analytic Number Theory
\publ Springer\publaddr New York \yr 1984
\endref

\ref \no 2 \paper Mellin Transforms and Asymptotics: Digital Sums
 \by P.Flajolet, P. Grabner, 
P.Kirschenhofer, H.Prodinger and R.F.Tichy \jour Theoretical Computer Science
\toappear
\endref

\ref \no 3 \by  P.Flajolet and L.B.Richmond
\paper Generalized Digital Trees and Their Difference-Differential Equations
\jour Random Structures and Algorithms
\yr 1992 \pages 305--320        \vol 3      
\endref

\ref\no4 \by P. Flajolet, M. R\'egnier and R. Sedgewick\paper
Some Uses of the Mellin Integral Transform in the Analysis of Algorithms
\inbook Combinatorial Algorithms on Words\eds A. Apostolico and Z. Galil
\publ Springer \publaddr New York\yr1985\endref

\ref \no 5 \by P.Flajolet and A.Odlyzko \pages  216--240\paper
Singularity Analysis of Generating Functions\yr 1990 \vol  3
\jour SIAM J. Disc. Math. 
\endref

\ref \no 6 \by P.Flajolet and J.Vitter 
\paper Average-Case Analysis of     Algorithms and Data Structures \yr 
1990 \pages 431--524     \inbook Handbook of Theoretical     
Computer Science Vol. A ``Algorithms and     Complexity''
\publ North-Holland      \endref

\ref \no 7 
\by D.E.Knuth 
\book The Art of Computer Science Vol.3\publ
Addison-Wesley \yr 1973 \publaddr Reading, MA \endref

\ref \no 8 \by H.M. Mahmoud \book Evolution of Random Search Trees
\publ Wiley-Interscience Series in Discrete Mathematics and Optimization
\publaddr New York \yr 1992
\endref

\ref\no 9\by J.-L. Mauclaire and L. Murata\paper On $q$-Additive Functions, 
II\jour Proc. Japan Acad.
\vol 59\pages 441--444\yr 1983\endref

\ref \no 10 \by H.Prodinger\paper
How to Advance on a Staircase by Coin Flippings,\toappear
\jour Proceedings ``Fibonacci Numbers and Applications 5''  
\yr 1992
\endref

\ref\no 11\by E.T. Whittaker and G.N. Watson\book A Course in Modern
Analysis\publ Cambridge University Press\yr 1927\endref

\endRefs














\enddocument


