\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 $-\alphac_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 $nc_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_1d_2$ cannot be treated
by the Mellin transform approach.)
\proclaim{Remark 1} Lemma~1 remains true in the case $d_10$)
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 $Md-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 $