Annales Academiæ Scientiarum Fennicæ Mathematica Volumen 21, 1996, 189–204

ON THE TAYLOR COEFFICIENTS OF THE COMPOSITION OF TWO ANALYTIC FUNCTIONS

Titus Hilberdink

Goldsmiths College, Department of Mathematical Sciences New Cross, London SE14 6NW, England; map01twh@scorpio.gold.ac.uk

Abstract. We give an asymptotic formula for the Taylor coefficients f_{n} of f(z) = l(h(z)) where l(z) is analytic in the unit disc whose Taylor coefficients l_{n} vary ‘smoothly’ and h(z) is analytic in a larger disc. We show that under mild conditions on h(z), f_{n} ∼ σl_{[σn]} as n → ∞ where σ = 1/h′(1). Applications to renewal theory are also discussed.

1. Introduction

Asymptotic enumeration usually involves estimating coefficients of a generating function f(z) which satisfies some functional equation. In many cases such a functional equation can be reduced to the form

f(z) = l(h(z)),

where the function l(z) is frequently known and its Taylor coefficients l_{n} are nonnegative and usually satisfy a certain regularity condition (see Bender [1], Meir and Moon [11]). In this paper we make the following regularity condition on l_{n} which occurs in many applications:

(†)  l_{n+[λ\sqrt{n}]} ∼ l_{n}  as n → ∞  for all λ ∈ R.

For instance, the cases l_{n} = 1 and l_{n} = 1/n from renewal theory and harmonic renewal theory respectively both satisfy (†) for which our result applies and we will discuss the details in Theorem 2.11 at the end of the paper. It will be shown later that for a large class of functions h(z) this is a natural choice to make and difficulties appear if the l_{n} are made any larger. We note that l(z) has a radius of convergence equal to 1 and z = 1 is a singularity (since e^{−ε\sqrt{n}} < l_{n} < e^{ε\sqrt{n}} follows from (†) and l_{n} ≥ 0). We also assume that h(1) = 1, and that h(z) has non-negative coefficients such that |h(z)| = h(|z|) only if z is real and nonnegative. This last condition is equivalent to h(z) ≠ z^{p}k(z^{r}) for any analytic function k(z) and any r ≥ 2, p ≥ 0 (see Remark 2.7(3)).

We note that many authors have considered the composite function l(h(z)) where the Taylor coefficients h_{n} are well-behaved, but we consider the case where the coefficients l_{n} are well-behaved. Indeed, our setting differs significantly from the one considered by Embrechts and Omey in [4], since their ‘l(z)’ is analytic in an open region containing the set {h(z) : |z| ≤ 1}. In particular, l(z) would then be analytic at z = 1.

1991 Mathematics Subject Classification: Primary 30B10; Secondary 40E10, 60K05.

From an analytical viewpoint we have two quite distinct cases:

(i) h(z) is analytic in a disc D(0, 1 + δ) for some δ > 0.

(ii) h(z) is analytic in the unit disc only. We shall first consider case (i).

Estimating the coefficients of f(z) can often be done by using the analytic continuation of f(z) to a region

\{|z| < 1 + η : | arg (z − 1)| > ϕ for some η > 0 and 0 < ϕ < \frac{1}{2}π\}.

For instance, such methods have been used in [7] and [12]. However, we will adopt a different approach in that we do not assume such an analytic extension, and in this respect the techniques we use seem to be more elementary.

Our main result is

Theorem 1.1. Let f(z) = l(h(z)) where the Taylor coefficients l_{n} of l(z) satisfy (†), and h(z) is analytic in |z| < 1 + δ where δ > 0, has non-negative coefficients such that |h(z)| = h(|z|) on [0, 1 + δ) only and h(1) = 1. Then the coefficients f_{n} of f(z) satisfy

f_{n} ∼ σl_{[σn]} as n → ∞ where σ = \frac{1}{h′(1)}.

We have readily the following corollary which is an extension of the theorem.

Corollary 1.2. Let f(z) = l(h(z)) with l(z) and h(z) as before, but with h(z) analytic in |z| < γ such that h(β) = 1 for some 0 < β < γ. Then

f_{n} ∼ σl_{[σn]}β^{−n} as n → ∞ where σ = \frac{1}{βh′(β)}.

The proof of the corollary follows immediately by putting F (z) = f(βz) and H(z) = h(βz) so that F (z) = l(H(z)) and the conditions for the theorem are satisfied.

After the proof of Theorem 1.1, we will extend the theorem to cover the more difficult case (ii) in Theorem 2.9.

I wish to thank the referee for many helpful suggestions.

On the Taylor coefficients of the composition of two analytic functions 191

2. Proof of the theorem

We begin with the following representation of l_{n}.

Lemma 2.1. Given a sequence (l_{n})_{n≥0} of positive reals such that l_{n+[λ\sqrt{n}]} ∼ l_{n} as n → ∞ for all real λ, then

l_{n} = s(e^{\sqrt{n}})

for some slowly-varying function s.

Proof. The result will follow once we can show that l_{n+1} ∼ l_{n} as n → ∞. For then l_{n+m} ∼ l_{n} as n → ∞ for all integers m, so by letting s(x) = l_{[(log x)^{2}]} we observe that

s(λx) ∼ s(x) as x → ∞ for all λ > 0,

i.e., s is slowly-varying.

To show that l_{n+1} ∼ l_{n}, consider η_{n}(λ) = [λ\sqrt{n}] + [−λ\sqrt{n + [λ\sqrt{n}]} ] for various λ > 0. By (†), we have l_{n+η_{n}(λ)} ∼ l_{n}. Taking λ = \sqrt{2} and λ = 2 in turn, one finds that η_{n}(\sqrt{2} ) = −2 and η_{n}(2) = −3 for all n except when |2n − m^{2}| or |4n − m^{2}| < some constant A.

If this happens, let k = n + [μ\sqrt{n}] for some 0 < μ < 1. Then 2k and 4k are bounded away from perfect squares and hence l_{k−2} ∼ l_{k−3} ∼ l_{k} from which it will be seen that l_{n−2} ∼ l_{n−3} as required.

Note that the converse holds trivially, so that we have an equivalence.

Slowly-varying functions have been studied in great detail (see Bingham et al. [3] or Feller [5]) and it is well known that they can be represented as follows:

If s(x) is slowly-varying, then

s(x) = c(x) exp\{∫ ^{x} \frac{ε(t)}{t} dt\}

where c(x) → c > 0 and ε(x) → 0 as x → ∞.

Using this, we easily obtain

Lemma 2.2. If l_{n+[λ\sqrt{n}]} ∼ l_{n} as n → ∞ for all real λ, then

l_{n} = c_{n} exp\{ ∑_{m=1}^{n} \frac{δ_{m}}{\sqrt{m}}\}

where c_{n} → c > 0 and δ_{n} → 0 as n → ∞.

Proof. Since l_{n} = s(e^{\sqrt{n}}), we have

l_{n} = c(e^{\sqrt{n}}) exp\{∫_{1}^{e^{\sqrt{n}}} \frac{ε(t)}{t} dt\} = c_{n} exp\{∫_{0}^{n} \frac{η(s)}{\sqrt{s}} ds\}

by putting t = e^{\sqrt{s}} , η(s) = \frac{1}{2}ε(e^{\sqrt{s}}) and c_{n} = c(e^{\sqrt{n}}). This gives us

l_{n} = c_{n} exp\{ ∑_{m=1}^{n} \frac{δ_{m}}{\sqrt{m}}\}

where

δ_{m} = ∫_{0}^{1} \frac{η(m + t − 1)}{\sqrt{1 + (t − 1)/m}} dt

which tends to 0, as desired.

This lemma gives us a corollary which will be useful in the proof of the theorem.

Corollary 2.3. For n and n + k → ∞,

l_{n+k} = l_{n} exp\{o(\frac{|k|}{\sqrt{n}}) + o(1)\}.

Proof. Without loss of generality take k > 0. We have

\frac{l_{n+k}}{l_{n}} = \frac{c_{n+k}}{c_{n}} exp\{ ∑_{m=0}^{k} \frac{δ_{m+n}}{\sqrt{m + n}}\}.

Now c_{n+k} ∼ c_{n} and |∑_{0}^{k} δ_{m+n}/\sqrt{m + n}| < δk/\sqrt{n} as required.

We are particularly interested in the case when a\sqrt{n} < |k| < A\sqrt{n} log n for some constants a and A in which case the o(1) term becomes superfluous.

We are now in a position to prove the theorem. Proof. We have by Cauchy’s integral formula,

f_{n} = \frac{1}{2πi} ∫_{γ} \frac{f(z)}{z^{n+1}} dz = \frac{1}{2πi} ∫_{γ} \frac{l(h(z))}{z^{n+1}} dz = ∑_{m=0}^{∞} l_{m} \frac{1}{2πi} ∫_{γ} \frac{h(z)^{m}}{z^{n+1}} dz

where γ is inside the unit disc. Thus

(1)  f_{n} = ∑_{m=0}^{∞} l_{m}J_{m,n}

where

J_{m,n} = \frac{1}{2πi} ∫_{γ} \frac{h(z)^{m}}{z^{n+1}} dz

is the coefficient of z^{n} in the expansion of h(z)^{m}. Suppose h_{m_{0}} is the first non-zero coefficient of h(z). Then J_{m,n} = 0 for m > n/m_{0} . (If m_{0} = 0, J_{m,n} > 0 always.) The proof basically involves estimating J_{m,n} for m ≥ 0. We will show that J_{m,n} is largest when m is close to σn. Recall that σ = 1/h′(1). In fact, (1/σ)J_{m,n} behaves like a normal distribution with mean σn and deviation σ\sqrt{2στn} where τ is some positive constant dependent on h(z). Note that h′(1) = ∑_{m_{0}}^{∞} nh_{n} > m_{0} ∑_{m_{0}}^{∞} h_{n} = m_{0} , so that σn lies in the non-zero range of J_{m,n}. The special case where h_{n} = 0 for all n > m_{0} so that h′(1) = m_{0} gives h(z) = h_{m_{0}}z^{m_{0}} which is not allowed.

We first find bounds for J_{m,n} when |m − σn| is ‘large’.

Lemma 2.4. (1) For 0 ≤ m ≤ \frac{1}{3}σn and m ≥ 3σn, we have

J_{m,n} ≤ e^{−ηn}, e^{−η′m} respectively for some η, η′ > 0.

(2) For \frac{1}{3}σn ≤ m ≤ σn − 2σ\sqrt{n} log n and σn + 2σ\sqrt{n} log n ≤ m ≤ 3σn, we have

J_{m,n} ≤ Ae^{−|m−σn|/σ\sqrt{n}} for some A.
Proof. (1) Consider first 0 ≤ m ≤ \frac{1}{3}σn. We have

0 ≤ J_{m,n} ≤ \frac{h(r)^{m}}{r^{n}}

for any 0 < r < 1 + δ since |h(z)| ≤ h(|z|). Take r = e^{ε} where ε > 0 is chosen such that

h(e^{ε}) ≤ e^{2ε/σ}.

This is possible because h(e^{t}) = 1 + (t/σ) + O(t^{2}) = exp((t/σ) + O(t^{2})) as t → 0. Then

J_{m,n} ≤ e^{(2εm/σ)−εn} ≤ e^{−εn/3}

as required. For m ≥ 3σn, take r = e^{−ε} where ε > 0 is chosen such that h(e^{−ε}) ≤ e^{−ε/2σ}. Then again J_{m,n} ≤ e^{−(εm/2σ)+εn} ≤ e^{−εm/6σ}.

(2) For the range \frac{1}{3}σn ≤ m ≤ σn − 2σ\sqrt{n} log n take r = e^{1/\sqrt{n}} in the above inequality. Then

J_{m,n} ≤ h(e^{1/\sqrt{n}})^{m}e^{−\sqrt{n}} = e^{((1/σ\sqrt{n})+O(1/n))m−\sqrt{n}} = e^{−(|m−σn|/σ\sqrt{n})+O(1)}.

If σn+2σ\sqrt{n} log n ≤ m ≤ 3σn take r = e^{−1/\sqrt{n}} and the result follows similarly.

Let S = \{m | \frac{1}{3}σn < m < 3σn and |m − σn| ≥ 2σ\sqrt{n} log n\}. Then from these bounds, we find that

∑_{|m−σn|≥2σ\sqrt{n} log n} l_{m}J_{m,n} = ∑_{0≤m≤σn/3, m≥3σn} l_{m}J_{m,n} + ∑_{S} l_{m}J_{m,n}

≤ e^{−ηn} ∑_{0≤m≤σn/3} l_{m} + ∑_{m≥3σn} l_{m}e^{−η′m}

+ A ∑_{S} l_{m}e^{−|m−[σn]|/σ\sqrt{n}}

≤ e^{−η′′n} + 2Al_{[σn]} ∑_{k≥2σ\sqrt{n} log n} e^{−k/σ\sqrt{n}+o(k/\sqrt{n})}

by putting k = m − [σn] and using Corollary 2.3 and the fact that l_{n} = e^{o(\sqrt{n})} . The last sum is bounded for all large n by

∫_{2σ\sqrt{n} log n}^{∞} e^{−t/2σ\sqrt{n}} dt = \frac{2σ}{\sqrt{n}}.

Hence

∑_{|m−σn|≥2σ\sqrt{n} log n} l_{m}J_{m,n} = O(\frac{l_{[σn]}}{\sqrt{n}} ).

Now it only remains to consider the range |m − σn| < 2σ\sqrt{n} log n. Here J_{m,n} behaves as follows:

Lemma 2.5. For |m − σn| < 2σ\sqrt{n} log n, we have

J_{m,n} = \frac{1}{2\sqrt{πστn}} exp \{−\frac{(m − σn)^{2}}{4σ^{3}τn} \} + O(\frac{(log n)^{2}}{n} )

where τ = \frac{1}{2}(h′(1) + h′′(1) − h′(1)^{2}) > 0 by Remark 2.6.

Proof. We have

J_{m,n} = \frac{1}{2πi} ∫_{γ} \frac{h(z)^{m}}{z^{n+1}} dz = \frac{1}{2π} ∫_{0}^{2π} e^{−niθ}h(e^{iθ})^{m} dθ.

Let δ_{n} = \sqrt{2 log n/στn} with τ as before. Then

|\frac{1}{2π} ∫_{δ_{n}}^{2π−δ_{n}} e^{−niθ}h(e^{iθ})^{m} dθ| ≤ sup_{δ_{n}≤θ≤2π−δ_{n}} |h(e^{iθ})|^{m} = |h(e^{±iδ_{n}})|^{m}

for all n sufficiently large, since |h(e^{iθ})| decreases near 0 and 2π where it is maximal. But

\begin{aligned}h(e^{iθ}) & = h(1 + iθ − \frac{1}{2}θ^{2} + O(θ^{3})) = 1 + h′(1)iθ − \frac{1}{2}(h′(1) + h′′(1))θ^{2} + O(θ^{3}) \\ & = exp(\frac{i}{σ} θ − τθ^{2} + O(θ^{3})) \end{aligned}

so that |h(e^{±iδ_{n}})|^{m} = exp(−mτδ_{n}^{2} + O(mδ_{n}^{3})) = O(n^{−2}). Hence

J_{m,n} = \frac{1}{2π} ∫_{−δ_{n}}^{δ_{n}} e^{−niθ}h(e^{iθ})^{m} dθ + O(\frac{1}{n^{2}} ).

In the range |θ| ≤ δ_{n}, we have

e^{−niθ}h(e^{iθ})^{m} = exp(−niθ + \frac{mi}{σ}θ − mτθ^{2} + O(mθ^{3}))

= exp\{\frac{m − σn}{σ}iθ − στnθ^{2} + O(\frac{(log n)^{2}}{\sqrt{n}} )\}

= exp\{\frac{m − σn}{σ}iθ − στnθ^{2}\}(1 + O(\frac{(log n)^{2}}{\sqrt{n}} ))

by using m = σn + O(\sqrt{n} log n). Thus

J_{m,n} = \frac{1}{2π} ∫_{−δ_{n}}^{δ_{n}} e^{(m−σniθ/σ)−στnθ^{2}} dθ + O(\frac{(log n)^{2}}{\sqrt{n}} ∫_{−δ_{n}}^{δ_{n}} e^{−στnθ^{2}} dθ) + O(\frac{1}{n^{2}} )

= \frac{1}{2π\sqrt{στn}} ∫_{−\sqrt{2 log n}}^{√\overline{2 log n}} e^{−ϕ^{2}+(m−σn)iϕ/σ\sqrt{στn}} dϕ + O(\frac{(log n)^{2}}{n} ∫_{−∞}^{∞} e^{−ϕ^{2}} dϕ)

= \frac{1}{2π\sqrt{στn}}e^{−(m−σn)^{2}/4σ^{3}τn} ∫_{−∞}^{∞} e^{−(ϕ−i(m−σn)/2σ\sqrt{στn})^{2}} dϕ

+ o(\frac{1}{n^{2}} ) + O(\frac{(log n)^{2}}{n} )

= \frac{1}{2\sqrt{πστn}} exp\{−\frac{(m − σn)^{2}}{4σ^{3}τn} \} + O(\frac{(log n)^{2}}{n} )

since

|∫_{|ϕ|≥\sqrt{2 log n}}| ≤ \frac{1}{\sqrt{2 log n}} ∫_{√\overline{2 log n}}^{∞} 2ϕe^{−ϕ^{2}} dϕ = o(\frac{1}{n^{2}} ).

Remark 2.6. Note that τ > 0. This is because ∑_{0}^{∞} h_{n} ∑_{0}^{∞} n^{2}h_{n} ≥ (∑_{0}^{∞} nh_{n})^{2} by Cauchy–Schwarz. Equality occurs only if h_{n} = 0 for all n except perhaps for one value of n but this case has already been ruled out.

To finalize the proof of the theorem, we must consider the sum ∑ l_{m}J_{m,n} over the range |m − σn| < 2σ\sqrt{n} log n.

First we have

∑_{|m−σn|<2σ\sqrt{n} log n} l_{m} \frac{(log n)^{2}}{n} = l_{[σn]} \frac{(log n)^{2}}{n} ∑_{|k|<2σ\sqrt{n} log n} e^{o(|k|\sqrt{n})}

= O(l_{[σn]} \frac{(log n)^{2}}{n} ∫_{0}^{2σ\sqrt{n} log n} e^{εt/\sqrt{n}} dt)

= O(l_{[σn]}n^{−(1/2)+ε′})

where ε and ε′ are arbitrarily small. Now choose an arbitrary A > 0. Then we have

\frac{1}{2\sqrt{πστn}} ∑_{|m−σn|<2σ\sqrt{n} log n} l_{m}e^{−(m−σn)^{2}/4σ^{3}τn} = ^{∑′} +^{∑′′},

where ^{∑′} is over the range |m − σn| ≤ A\sqrt{n} and ^{∑′′} is over A\sqrt{n} < |m − σn| ≤ 2σ\sqrt{n} log n. For ∑′′ we have

∑′′ = \frac{l_{[σn]}}{2\sqrt{πστn}} ∑_{A\sqrt{n}<|k|≤2σ\sqrt{n} log n} e^{−(k^{2}/4σ^{3}τn)+o(|k|/\sqrt{n})}

= O(\frac{l_{[σn]}}{\sqrt{n}} ∫_{A\sqrt{n}}^{2σ\sqrt{n} log n} e^{−(t^{2}4σ^{3}τn)+o(t/\sqrt{n})} dt)

= O(l_{[σn]} ∫_{A}^{∞} e^{−(y^{2}/4σ^{3}τ)+o(y)} dy) where t = y\sqrt{n}

< ε(A)l_{[σn]}

where ε(A) → 0 as A → ∞.

Lastly

∑′ ∼ l_{[σn]} ∑_{|m−σn|≤A\sqrt{n}} J_{m,n}  by virtue of (†)

= l_{[σn]} ∑_{m=0}^{∞} J_{m,n}(1 + δ_{n}(A))

where, as before, |δ_{n}(A)| ≤ δ(A) → 0 as A → ∞ by using the previous known bounds on J_{m,n}. But

∑_{m=0}^{∞} J_{m,n} = \frac{1}{2πi} ∫_{γ} \frac{1}{(1 − h(z))z^{n+1}} dz = σ + O(a^{−n})

for some a > 1, by choosing γ so that it contains the simple pole of 1/1 − h(z) at 1. So letting A → ∞, (1) gives

f_{n} ∼ σl_{[σn]}

as desired.

Remark 2.7. (1) The result is ‘best possible’ in the sense that if we increase the growth rate of l_{n} it becomes false. In particular, by the same methods one can prove that if l_{n} = r(e^{\sqrt{n}}) where r is a regularly-varying function with index ρ, then

f_{n} ∼ σl_{[σn]}e^{σ^{3}τρ^{2}/4} as n → ∞.

(Lemma 2.4 would have to be improved to J_{m,n} = O(e^{−(m−σn)^{2}/4σ^{3}τn}) for |m − σn| = O(n^{2/3}). This is done by taking r = e^{−(m−σn)/2σ^{2}τn} in the proof.)

Also, if the l_{n} are made larger than e^{A\sqrt{n}} (any A), then the arguments following Lemma 2.4 and Remark 2.6 fail and only with very precise knowledge of the behaviour of l_{[σn]+m}/l_{[σn]} as m varies, can we obtain a simple asymptotic formula for f_{n}.

(2) The proof of the theorem would in many cases be substantially easier if we did not allow the l_{n} to be quite so large. For example, if l_{n} was regularly-varying (which satisfies (†)), we only need Lemma 2.4 after which

∑_{|m−σn|≤2σ\sqrt{n} log n} l_{m}J_{m,n} ∼ l_{[σn]} ∑_{|m−σn|≤2σ\sqrt{n} log n} J_{m,n} ∼ l_{[σn]} ∑_{m=0}^{∞} J_{m,n} ∼ σl_{[σn]}

follows immediately. Also, with a little extra work, we can usually find an asymptotic expansion for f_{n} given that l_{n} has one.

(3) The original condition on h(z) was that |h(z)| = h(|z|) on [0, 1 + δ) only. As stated earlier this is equivalent to saying that h(z) is not of the form z^{p}k(z^{r}) for any analytic k(z) and p ≥ 0, r ≥ 2. On the other hand, if h(z) = z^{p}k(z^{r}), then consider gcd(p, r) > 1 and = 1. In the former case, the theorem fails since f_{n} = 0 if d |̸n. In fact, if gcd(p, r) = d ≥ 2 then h(z) = k_{1}(z^{d}) some k_{1} analytic which is equivalent to the case p = 0. If however gcd(p, r) = 1, the result is, surprisingly enough, still true. Lemma 2.4 will hold as before but a change occurs in Lemma 2.5. Here we have

J_{m,n} = \{ \begin{matrix}\frac{r}{2\sqrt{πστn}}e^{−(m−σn)^{2}/4σ^{3}τn} + O(\frac{(log n)^{2}}{n} ) & if pm ≡ n (mod r), \\ 0 & otherwise. \end{matrix}

A little elementary number theory will be needed in the later stages of the proof. Thus the result stands true for all h(z) not of the form k(z^{r}) as long as there is a β > 0 within its radius of convergence such that h(β) = 1. If h(z) = k(z^{r}) with r ≥ 2 maximal, β = 1, then f(z) = F (z^{r}) with F (z) = ∑_{0}^{∞} F_{n}z^{n} and the theorem applies to F (z), i.e., F_{n} ∼ rσl_{[rσn]} . The result now covers all possible forms of h(z).

In case (ii), where h(z) is analytic in the unit disc only, we cannot use the arguments of Lemma 2.4 (for the case m < σn) so other methods are needed to provide the bounds we want, viz.

J_{m,n} = O(e^{−λ|m−σn|/\sqrt{n}} ) for some λ > 0.

For the result f_{n} ∼ σl_{[σn]} to hold, we clearly need some bound on h_{n} (given that we still allow l_{n} to be large). For example, if h_{n} ≠ O(e^{−λ\sqrt{n}} ) for any λ > 0, we can always find an l_{n} = s(e^{\sqrt{n}}) such that l_{[σn_{k}]} = o(h_{n_{k}}) along some sequence n_{k} → ∞. Then since f_{n} ≥ l_{1}h_{n} the theorem cannot hold.

However, if h_{n} = O(e^{−λ\sqrt{n}} ) for some λ > 0, the theorem still holds. The trick is to use an approximation to h(z), namely h_{n}(z) = ∑_{r=0}^{n} h_{r}z^{r}, and to observe that J_{m,n} is still the coefficient of z^{n} in the expansion of h_{n}(z)^{m}. Thus we can use Cauchy’s inequality J_{m,n} ≤ h_{n}(r)^{m}r^{−n} with any r > 0. For r close to 1 this is useful, provided we know how h_{n}(r) varies. Whence the following lemma.

Lemma 2.8. Suppose h_{n}(z) = ∑_{r=0}^{n} h_{r}z^{r} with h_{n} = O(e^{−λ\sqrt{n}}) for some λ > 0. Then for 0 < ε_{n} ≤ μ/\sqrt{n} with μ < λ,

h_{n}(e^{ε_{n}}) = ∑_{k=0}^{K−1} \frac{ε_{n}^{k}S_{k}^{(n)}}{k!} + O(ε_{n}^{K})

for any K ≥ 1 where S_{k}^{(n)} = ∑_{r=0}^{n} h_{r}r^{k}.

Proof. We have

(∗) h_{n}(e^{ε_{n}}) = ∑_{r=0}^{n} h_{r}e^{rε_{n}} = ∑_{r=0}^{n} h_{r} ∑_{k=0}^{∞} \frac{r^{k}ε_{n}^{k}}{k!} = ∑_{k=0}^{∞} \frac{ε_{n}^{k}}{k!} ∑_{r=0}^{n} h_{r}r^{k} = ∑_{k=0}^{∞} \frac{ε_{n}^{k}S_{k}^{(n)}}{k!}

and for each k fixed, S_{k}^{(n)} → S_{k} = ∑_{r=0}^{∞} h_{r}r^{k} as n → ∞. Note that if the radius of convergence of ∑ h_{n}z^{n} is 1 then h_{n}(e^{ε}) = ∑_{k=0}^{∞} ε^{k}S_{k}^{(n)}/k! converges for all n and ε > 0, but this is unbounded as n → ∞ so the series cannot possibly be an asymptotic series. To prove the lemma we must estimate the right hand side in (∗). To do this let T_{k}^{(n)} = ∑_{r=0}^{n} r^{k}e^{−λ\sqrt{r}}. We obtain the following bounds on T_{k}^{(n)} :

(1) For k ≥ \frac{1}{2}λ\sqrt{n}, we have
n^{k}e^{−λ\sqrt{n}} ≤ T_{k}^{(n)} ≤ n^{k+1}e^{−λ\sqrt{n}}

(2) In any case,

T_{k}^{(n)} ≤ T_{k} = ∑_{r=0}^{∞} r^{k}e^{−λ\sqrt{r}} = O(k^{3/2}(\frac{2k}{eλ})^{2k}).

To prove the above, consider the function f_{k}(t) = t^{k}e^{−λ\sqrt{t}}. This increases for 0 ≤ t ≤ 4k^{2}/λ^{2} where it reaches a maximum of (2k/eλ)^{2k} after which it decreases. Thus for k ≥ \frac{1}{2}λ\sqrt{n}, the largest term occurs at the end of the series, that is,

n^{k}e^{−λ\sqrt{n}} ≤ T_{k}^{(n)} ≤ n.n^{k}e^{−λ\sqrt{n}}.

Next, let N_{k} = [(2k/λ)^{2}] so that

T_{k} = ∑_{n=1}^{∞} f_{k}(n) = ( ∑_{n=1}^{N_{k}−1} + ∑_{n=N_{k}+2}^{∞})f_{k}(n) + f_{k}(N_{k}) + f_{k}(N_{k} + 1)

≤ (∫_{0}^{(2k/λ)^{2}} + ∫_{(2k/λ)^{2}}^{∞})f_{k}(t) dt + 2(\frac{2k}{eλ})^{2k}

= ∫_{0}^{∞} t^{k}e^{−λ\sqrt{t}} dt + 2(\frac{2k}{eλ})^{2k}

= \frac{(2k + 1)!}{λ^{2k+2}} + 2(\frac{2k}{eλ})^{2k} = O(k^{3/2}(\frac{2k}{eλ})^{2k}).

Using these, we obtain

∑_{k=K}^{∞} \frac{ε_{n}^{k}T_{k}^{(n)}}{k!} = ∑_{K≤k≤λ\sqrt{n}/2} \frac{ε_{n}^{k}T_{k}^{(n)}}{k!} + ∑_{k>λ\sqrt{n}/2} \frac{ε_{n}^{k}T_{k}^{(n)}}{k!}

≤ A ∑_{K≤k≤λ\sqrt{n}/2} \frac{ε_{n}^{k}k^{3/2}}{k!} (\frac{2k}{eλ})^{2k} + ∑_{k>λ\sqrt{n} /2} \frac{ε_{n}^{k}n^{k+1}e^{−λ\sqrt{n}}}{k!}

≤ A′ε_{n}^{K} ∑_{K≤k≤λ\sqrt{n}/2}kε_{n}^{k−K}(\frac{4k}{eλ^{2}} )^{k} + ε_{n}^{K}n^{K+1}e^{−λ\sqrt{n}} ∑_{k>λ\sqrt{n}/2}\frac{(nε_{n})^{k−K}}{(k − K)!}

≤ A′′ε_{n}^{K} ∑_{0≤k≤λ\sqrt{n}/2} k^{K+1}(\frac{4kε_{n}}{eλ^{2}} )^{k} + ε_{n}^{K}n^{K+1}e^{−λ\sqrt{n} +nε_{n}}

≤ A′′ε_{n}^{K} ∑_{k=0}^{∞} k^{K+1}(\frac{2}{e})^{k} + ε_{n}^{K}n^{K+1}e^{−(λ−μ)\sqrt{n}} = O(ε_{n}^{K})

since ε_{n} ≤ μ/\sqrt{n}, from which the result follows.

Note that for k = [λ\sqrt{n}],

\frac{ε_{n}^{k}T_{k}^{(n)}}{k!} ≥ \frac{ε_{n}^{k}n^{k}e^{−λ\sqrt{n}}}{k!} ≥ A(\frac{nε_{n}}{k} )^{k}k^{−1/2} ≥ A(\frac{ε_{n}\sqrt{n}}{λ})^{k}n^{−1/4},

so that ε_{n} < λ\sqrt{n} is necessary for an asymptotic series.

Now, using the above lemma with ε_{n} = μ/\sqrt{n} (0 < μ < λ), we find that

h_{n}(e^{μ/\sqrt{n}} ) = S_{0}^{(n)} + S_{1}^{(n)} \frac{μ}{\sqrt{n}} + O(\frac{1}{n}) = 1 + \frac{μ}{σ\sqrt{n}} + O(\frac{1}{n}) = e^{μ/σ\sqrt{n}+O(1/n)}

since S_{k}^{(n)} = S_{k} + O(n^{−A}) for all A and for any fixed k while S_{0} = 1 and S_{1} = h′(1). Thus

J_{m,n} ≤ h_{n}(e^{μ/\sqrt{n}})^{m}e^{−μ\sqrt{n}} = e^{((μ/σ\sqrt{n})+O(1/n))m−μ\sqrt{n}} = e^{−(μ|m−σn|/σ\sqrt{n})+O(1)}

whenever m < σn. We can now use this bound to obtain

∑_{m<σn−A\sqrt{n} log n} l_{m}J_{m,n} = O(  ∑_{m<σn−A\sqrt{n} log n} l_{m}e^{−μ|m−σn|/σ\sqrt{n}})

= O(l_{[σn]} ∑_{A\sqrt{n} log n}^{∞} e^{−μk/σ\sqrt{n}+o(k/\sqrt{n})})

= O(l_{[σn]} ∫_{A\sqrt{n} log n}^{∞} e^{−μt/2σ\sqrt{n}} dt)

= O(l_{[σn]}\sqrt{n} ∫_{Aμ log n/2σ}^{∞} e^{−y} dy)

= O(l_{[σn]}n^{(1/2)−(Aμ/2σ)}) = o(l_{[σn]})

if A is sufficiently large, for example A = 2σ/μ. As stated earlier, Lemma 2.4 is still valid for m > σn, so now we only need to consider the range |m − σn| = O(\sqrt{n} log n). Looking at Lemma 2.5, we find that we only used the fact that for θ real and small, h(e^{iθ}) = e^{(iθ/σ)−τθ^{2}+O(θ^{3})} . It is not difficult to show that this follows from ∑ n^{3}h_{n} < ∞—which is certainly true in our case. Also, the bound |m − σn| < 2σ\sqrt{n} log n can be replaced by O(\sqrt{n} log n) as only this fact was used in the proof. Hence Lemma 2.5 may be applied and the arguments following Remark 2.6 remain valid until we get to the sum ∑_{m=0}^{∞} J_{m,n}, which is the coefficient of z^{n} in the expansion of 1/1 − h(z). But by the Erdős–Feller– Pollard theorem [6], this tends to σ as desired. Thus we have the more general theorem as follows:

Theorem 2.9. Let f(z) = l(h(z)) where the Taylor coefficients l_{n} of l(z) satisfy (†), and h(z) = ∑_{0}^{∞} h_{n}z^{n} has 0 ≤ h_{n} ≤ Ae^{−λ\sqrt{n}} (some λ > 0) and is not of the form k(z^{r}) for any r > 1 with h(1) = 1. Then the coefficients f_{n} of f(z) satisfy

f_{n} ∼ σl_{[σn]} as n → ∞ where σ = \frac{1}{h′(1)}.

Remark 2.10. If we have h_{n} ≠ O(e^{−λ\sqrt{n}}), and we want to obtain some asymptotic result for f_{n}, then it seems we need to cut down the growth rate of l_{n}. We note that the theorem can be extended to the case where l_{n} = s(e^{ψ(n)}) with log n ≺ ψ(n) ≤ \sqrt{n} given that h_{n} = O(e^{−λψ(n)}) for some λ > 0. We will discuss the details in a separate paper. The case where l_{n} is regularly-varying has been considered by Embrechts et al. ([4], [5]) and Grubel ([8], [9]), particularly for its connection with (generalised) renewal theory.

Our method in deriving the Tauberian theorem can also be applied to study generalized renewal theory.

Given a continuous probability distribution η: (−∞, ∞) → [0, 1] with η(0) = 0 and a sequence (l_{n})_{n≥1} of positive numbers, a generalized renewal process is defined to be

(2)  ϕ(t) = ∑_{n=0}^{∞} l_{n}η^{∗n}(t)

where η^{∗n}(t) is the n-fold convolution of η(t). The special case where l_{n} = 1 for all n is the renewal process treated in [6]. In [5] and [10], Embrechts, Maejima and Omey obtained the asymptotic behaviour of ϕ(t + k) − ϕ(t) as t → ∞ for fixed k > 0, given that l_{n} varies regularly. We obtain a more general result under the assumption that l_{n} = s(e^{\sqrt{n}}) where s is slowly-varying, given certain convergence conditions on η(t). We note that (2) has the form similar to (1) where we had f_{n} = ∑_{m=0}^{∞} l_{m}h_{n}^{∗m}. To make this connection more explicit, we let h(z) = ∫_{0}^{∞} e^{−tz} dη(t) and l(z) = ∑_{n=0}^{∞} l_{n}z^{n}, from which it follows formally that

f(z) =^{def} ∫_{0}^{∞} e^{−tz} dϕ(t) = ∑_{n=0}^{∞} l_{n} ∫_{0}^{∞} e^{−tz} dη^{∗n}(t) = ∑_{n=0}^{∞} l_{n}h(z)^{n} = l(h(z)).

Theorem 2.11. We have

\frac{ϕ(t + k) − ϕ(t)}{k} ∼ σl_{[σt]} as t → ∞

where 1/σ = −h′(0) under the following conditions:

(i) h(z) is analytic in Re(z) > −δ for some δ > 0,

(ii) ∫_{A}^{∞}(|h(c ± ix)|/x) dx converges for every c > −δ (where A > 0), and (iii) l_{n} = s(e^{\sqrt{n}}) for some slowly-varying function s.

Condition (iii) allows us to make l_{n} significantly larger than those considered in [5] and [10], where l_{n} is regularly-varying. By the Riemann–Lebesque theorem, we have |h(c + ix)| → 0 as x → ±∞ through real values for any given c > −δ, so that condition (ii) is not very restrictive.

Proof (main steps). First, by the Laplace inversion formula, we have

η^{∗n}(t) = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} \frac{e^{tz} − 1}{z}h(z)^{n} dz

for any c > −δ. (Here ∫_{c−i∞}^{c+i∞} = lim_{T →∞} ∫_{c−iT}^{c+iT} .) Again, we want to estimate I_{n}(t) = η^{∗n}(t + k) − η^{∗n}(t) as t → ∞ for various n. As in Lemma 2.4 we find that

I_{n}(t) = \{ \begin{matrix}O(e^{−ηt}), O(e^{−η′n}) & for n ≤ \frac{1}{3}σt and n ≥ 3σt respectively, \\ O(e^{−|n−σt|/σ\sqrt{t}} ) & for |n − σt| ≥ 2σ\sqrt{t} log t and \frac{1}{3}σt < n < 3σt \end{matrix}

while for |n − σt| < 2σ\sqrt{t} log t, we have, as in Lemma 2.5,

I_{n}(t) = \frac{k}{2\sqrt{πστt}} exp \{−\frac{(n − σt)^{2}}{4σ^{3}τt} \} + O(\frac{(log t)^{2}}{t} )

where τ = \frac{1}{2}(h′′(0) − h′(0)^{2}) > 0 by Cauchy–Schwarz.

For example, for n ≤ \frac{1}{3}σt, choose (−δ <) c < 0 such that h(c) ≤ e^{−2c/σ}, which is possible since h(z) = e^{−(z/σ)+τz^{2}+O(z^{3})} as z → 0. Hence

|I_{n}(t)| = |\frac{1}{2π} ∫_{−∞}^{∞} \frac{e^{t(c+ix)}(e^{k(c+ix)} − 1)}{c + ix}h(c + ix)^{n} dx|

≤ \frac{1}{π} e^{tc}h(c)^{n−1} ∫_{−∞}^{∞} \frac{|h(c + ix)|}{\sqrt{c^{2} + x^{2}}} dx since |h(c + ix)| ≤ h(c)

= O(e^{tc−2cn/σ}) = O(e^{ct/3}) by condition (ii)

as desired (note that c < 0).

For the ranges \frac{1}{3}σt < n ≤ σt − 2σ\sqrt{t} log t and σt + 2σ\sqrt{t} log t ≤ n < 3σt, take c = −1/\sqrt{t} and 1/\sqrt{t} respectively. We deform the integrals into

∫_{c−i∞}^{c+i∞} = ∫_{c−iπ}^{c+iπ} + ∫_{c+iπ}^{iπ} + ∫_{iπ}^{i∞} + ∫_{−iπ}^{c−iπ} + ∫_{−i∞}^{−iπ} .

Call these last four integrals ∫_{γ_{i}} (i = 1 to 4) respectively. For ∫_{c−iπ}^{c+iπ} we proceed as in the proof of the main theorem, while on γ_{1} we use the following estimate:

|∫_{γ_{1}} | ≤ \frac{e^{tc}(e^{kc} + 1)|c|}{2π^{2}} sup_{0≤x≤c} |h(x + iπ)|^{n}

where c = 1/\sqrt{t} (and similarly for c = −1/\sqrt{t}). But |h(iπ)| < h(0) = 1, (since |h(z)| ≤ h(Re z) with equality occuring if and only if z is real) so that sup < 1 for all |x| sufficiently small, i.e., for all t sufficiently large. Hence |∫_{γ_{1}} | = O(A^{−n}) for some A > 1. For ∫_{γ_{2}} we use a similar trick and the fact that |h(ix)| → 0 as x → ∞ to obtain |∫_{γ_{2}} | = O(A^{−n}) for some A > 1.

Applying the same arguments following Remark 2.6 to ∑_{n=0}^{∞} l_{n}I_{n}(t), we obtain

∑_{n=0}^{∞} l_{n}I_{n}(t) ∼ l_{[σt]} ∑_{n=0}^{∞} I_{n}(t) ∼ kσl_{[σt]},

which gives

\frac{ϕ(t + k) − ϕ(t)}{k} ∼ σl_{[σt]} as t → ∞.

For the special cases l_{n} = 1 and l_{n} = 1/n of renewal theory and harmonic renewal theory respectively, we thus obtain

ϕ(t + k) − ϕ(t) → kσ as t → ∞

and

ϕ(t + k) − ϕ(t) ∼ \frac{k}{t} as t → ∞,

which agree with the known results.

Acknowledgements. I would like to thank Dr. C.-H. Chu for his invaluable comments and suggestions. I would also like to thank Goldsmiths’ College for their financial support.

References

[1] Bender, E.A.: Asymptotic methods in enumeration. - SIAM Rev. 16, 1974, 485–515.

[2] Bingham, N.H., C.M. Goldie, and J.L. Teugels: Regular Variation. - Cambridge University Press, 1987.

[3] de Bruijn, N.G.: Asymptotic Methods in Analysis. - North-Holland Publishing Co., 1970 (3rd edition).

[4] Embrechts, P., and E. Omey: Functions of power series. - Yokohama Math. J. 32:2, 1984, 77–88.

[5] Embrechts, P., M. Maejima, and E. Omey: A renewal theorem of Blackwell type. - Ann. Probab. 12, 1984, 561–570.

[6] Feller, W.: An Introduction to Probability Theory and its Applications, Volumes I, II. - John Wiley, New York, 1968 (3rd edition).

[7] Flajolet, P., and A.M. Odlyzko: Singularity analysis of generating functions. - SIAM J. Discrete Math. 3, 1990, 216–240.

[8] Grübel, R.: Functions of discrete probability measures. - Z. Wahrsch. Verw. Gebiete 64, 1983, 341–357.

204 Titus Hilberdink

[9] Grübel, R.: On subordinated distributions and generalised renewal measures. - Ann. Probab. 15:1, 1987, 394–415.

[10] Maejima, M., and E. Omey: A generalised Blackwell renewal theorem. - Yokohama Math. J. 32, 1984, 123–133.

[11] Meir, A., and J.W. Moon: On an asymptotic method in enumeration. - J. Combin. Theory Ser. A 51, 1989, 77–89.

[12] Odlyzko, A.M.: Asymptotic enumeration methods. - Handbook of Combinatorics, preprint, 1992.

Receoived 22 November 1994