(p.558) Appendix D Asymptotic approximations
(p.558) Appendix D Asymptotic approximations
The Stirling approximation for the factorial  is given by
Lower and upper bounds on the factorial are
is from a numerical point of view very accurate.
Stirling’s approximation can also be stated as
from which it follows, for example,
More on Stirling’s approximation may be found in reference .
Catalan numbers are defined by
By putting both and in equation (D.5) and keeping more terms in the Stirling approximation, one finds that
(p.559) D.1 Approximation of the binomial coefficient
The binomial coefficient can be approximated using approximations for the factorial. A more interesting approach is to consider random walks in .
Consider a random walk from 0 in giving left or right steps. Assign a generating variable t with each right step so that represents a left step.
The generating function of walks of length n is , and the coefficient of is the number of walks ending at from the origin. Thus, by the binomial theorem, the number of walks ending at k is , since the walk ends at k if it gives right steps (and left steps).
Assume that and suppose that the walk steps to the right with probability and to the left with probability . Let Xk be the final position of the walk after k steps. Then .
Note that Xk is a random variable and that for with probability
The value of is 0 if n and k do not have the same parity (are not both even, or not both odd).
Asymptotically, n and k have the same parity with probability , and the distribution of Xn is given by
By the central limit theorem, the random variable Xn is asymptotically normally distributed with mean and variance , where
Thus, it follows that
This is maximal when , with μ given above. In particular, if , then one may solve for t to obtain
Since , select the positive root . In this event, it follows that, if , then . For this choice of k and with , one may solve for the binomial coefficient in equation (D.9):
Substitute into equation (D.12) to obtain the following approximation for the binomial:
The binomial coefficient is approximated by
Next, replace for and simplify to obtain
For large values of n, the above can be approximated by
Taking gives Corollary D.2.
The rate of growth of binomial coefficients is given by
for . The function has infinite right- and left-derivatives at , and , respectively. Moreover, , and .
One may replace or by or with few, if any changes, in Corollary D.2.
More generally, for , and , one may consider the function
which has a maximum for fixed given by
Similar to in Corollary D.2, has infinite right- and left-derivatives at , and , for fixed .
(p.561) The function for , and , defined by
similarly has the maximum
for fixed . The function has infinite left- and right-derivatives at , and , respectively.
Let and suppose . Then
Let so that . Then
Consider p to be the probability that a biased tossed coin will land heads. Let η be the number of heads in n tosses of the coin. Then the probability that there are at most heads in n tosses is
If is a random variable equal to 1 if , and 0 otherwise, then the expectation of is . By Jensen’s inequality,
The right-hand side is a minimum when . Thus, substituting for t gives(D.19)
Substitute , take the power and take .
This completes the proof.
(p.562) D.2 Approximation of trinomial coefficients
Trinomial coefficients are defined by
The term ‘trinomial coefficient’ is used as in reference ; that is, ‘trinomial coefficient’ is used synonymously with ‘central trinomial coefficient’.
Trinomial coefficients are given in terms of binomial coefficients by
The properties of a random walker in can be used to find approximations to trinomial coefficients. Let the position of the walker be xn and suppose it gives right or left unit length steps in , or a neutral step where it stays put at xn, so that , or .
Let and suppose the random walker gives right, neutral and left steps with probabilities , P0 and , respectively. Suppose , let and let
The probability that for is given by
since if the walk gives right steps and p left steps, and since the number of walks ending at k is exactly given by the trinomial coefficient.
The central limit theorem states that the random variable xn is asymptotically normal with mean and variance , where
Thus, it follows that
Substitute , substitute and solve for t:
Since , select so that and solve for the trinomial coefficient in equation (D.22). If , and , then this gives
Simplification gives theorem D.4.
The trinomial coefficient is approximated by
For large values of n, one may use Corollary D.5.
The trinomial coefficient
The rate of exponential growth of the trinomial coefficient is given by Corollary D.6.
The rate of growth of the generating function of trinomial coefficients is defined by
Given an n, there is a value of j, say , which maximises the summand.
(p.564) Assuming that , where is a function of z, it follows that
By differentiating and solving for , the supremum is realised when
It follows that if , and so the supremum is achieved when when at . These results show that, after simplification,
The function is given by(D.32)
D.3 The Euler-Maclaurin formula
The Euler-Maclaurin formula (see for example ) is a useful method for approximating series by integrals. The formula is useful because it gives precise remainders, allowing estimates of the error in the approximation.
Theorem D.8 (Euler-Maclaurin)
If for some , and both and , then
where the remainder term is given by
The function is the n-th Bernoulli polynomial; , and is the n-th periodic Bernoulli polynomial.
(p.565) In some applications the remainder term Rm approaches 0 with (derivatives of f exist to all orders), and one may able to show that the series is convergent.
The remainder term can be bounded by
The Bernoulli functions are defined by the recurrence , with , and , for . The first few are given by ; ; ; and .
The Bernoulli numbers are defined by the exponential generating function . Notably, if (that is ), and the first few non-zero Bernoullui numbers are ; ; ; and .
The Stirling approximation for is obtained as follows. Consider the integral
Applying the Euler-Maclaurin formula to the integral on the left-hand side gives
The infinite series in the above is a polygamma function and
Take the anti-derivative of this twice to obtain
The constant C is computed from the Legendre duplication formula
This gives . Finally,
This is an asymptotic series approximating . By truncating the infinite series, the error in the approximation is less than the magnitude of the first omitted term. If the series is discarded in its entirety, then the Stirling approximation in equation (D.1) is found.
(p.566) D.4 Saddle point approximations of the integral
Suppose that f is an analytic complex function of the complex variable . Then , and satisfies the Cauchy-Riemann equations. Consequently, it may be shown that u satisfies the Laplace equation:
At any stationary point of f, if , then . That is, if f is real valued, then its stationary points are necessarily saddle points.
The function f may be approximated in the vicinity of a saddle point z0 by
This approximation of f near its saddle points allows the approximation of integrals of the form
where N is large, and is slowly varying.
Insert the approximation of f in the above and replace . Deform the contour of integration from a to b into a contour C in the complex plane passing through z0. This gives
Put and let . The integration will be along r, with ϕ fixed at a convenient value, namely, . The integration is approximated by integrating from to . These substitutions simplify the integral above into a Gaussian integral:
Evaluating the integral gives the saddle point approximation
The phase ϕ is determined by solving for .
It is possible to refine the above approximations by keeping more terms in the expansion (D.35). This approximation also has the implicit assumption that the only significant contribution to the integral along the contour C is from the vicinity of the saddle point (this means that if is ‘large’. This may not be necessarily the case. For more on this method, which is related to steepest descent methods, see, for example, reference .
(p.567) D.5 Asymptotic formulae for the q-factorial and related functions
The q-deformations of special functions are obtained from an arithmetic based on q-integers, and defined by
where . These q-integers retain many of the properties of the usual integers. A q-integer is sometimes called a q-bracket or a basic integer.
The q-Pochhammer function is a finite product formally defined by
is an infinite product.
The q-Pochhammer function is an analytic function inside the unit disk in the q-plane. Euler’s function is defined by . Observe that and
Put in the above to find an infinite product representation of .
A partition identity (see for example reference ) shows that
Note that the usual factorial in the definition of the exponential is replaced by . For this reason, is sometimes called the q-exponential; however, see equation (D.46) below.
(p.568) The natural definition of the q-analogue of the factorial is in terms of q-integers:
and these are also called basic factorials or Gaussian factorials. This gives rise to the q-analogue of the gamma function or the q-gamma function:
which becomes if . Observe that, if in each of the above, then the usual integers, factorials and gamma functions are recovered.
The natural definition of the q-exponential is
Observe that .
These definitions of the exponential give rise to q-analogues of the trigonometric functions sine and cosine. There are also q-analogues of special functions. For example, q-deformed Bessel functions are defined by
More on q-calculus can be found, for example, in reference .
D.5.1 The q-binomial coefficient
The above definitions extend to the q-binomial coefficient, defined by
and, if , and , then this becomes
Observe that and that satisfies the following q-binomial identities:
Lemma D.9 is not obvious.
If , and , then the Gaussian binomial coefficient is a polynomial of degree with non-negative integer coefficients. In other words,
Observe that and is a polynomial of degree 0.
The proof proceeds by induction.
Suppose that is a polynomial with coefficients in and with degree , where , and . By equation (D.51),
The largest power of q in the above is as required, and the coefficients of on the right-hand side are sums over integers in .
Similarly, again by equation (D.51),
Hence, if is a polynomial in q of degree and with coefficients in , then is a polynomial in q of degree and with coefficients in . Notice that .
The q-binomial theorem is usually stated as
but it is also encountered as
The proof of the last equality proceeds by the counting of partitions.
The q-binomial theorem gives rise to the Jacobi triple product identity
D.5.2 Directed paths and the q-binomial coefficient
There is a close connection between Gaussian binomial coefficients and D.9 (see reference ). Consider the square lattice and let be the positive half-lattice with the boundary as the x-axis. In figure D.1, directed paths from the origin in give only north and east steps. The path oversteps area α in the first quadrant of underneath the path and to the left of the endpoint of the path.
The number of square lattice directed paths in , of length n, from the origin to the point , giving only north and east steps and which overstep an area of size α in the first quadrant of is .
This is true for any α if , and . Suppose that the lemma is true for any .
Consider . By equation (D.51),
If coefficients of are compared, then
This result is interpreted in figure D.2. By the induction hypothesis, the term counts the number of walks of length n, from to , and overstepping area α.
Appending a vertical step to paths turn these into walks of length which contribute towards
In a similar fashion, counts the number of walks from the origin to and which enclose the area . If a horizontal edge is appended from to , then it encloses area α. Thus, counts the number of walks from to and which overstep area α.
Putting gives the corollary
Figure D.1 is also a Ferrer’s diagram of a partition. Thus, let the number of partitions of into r parts with largest part k be denoted . Then .
The generating function of for fixed k and r is
See reference  for a different proof of this result.
The generating function of partitions follows from this as
where t is the generating variable conjugate to perimeter length.
D.5.3 Theta functions, and partial theta functions
The Jacobi θ-function is defined by
(p.572) is the Ramanujan θ-function. The Jacobi triple product identity may be cast as
By expanding the second and third products on the left-hand side, this becomes
where . Putting gives
This last identity may also be obtained from the Ramanujan θ-function, which is defined as
The Jacobi triple product becomes
By choosing in the above, Ramanujan’s ϕ-function is recovered:
Other identities may be recovered; for example, if , and , then
and, if , and , then
This identity is the famous pentagonal number theorem .
(p.573) The summation in the series definitions of θ-functions given above is over all of . It may in some instances be necessary to have to have the summation only over . This restriction gives rise to partial θ-functions. An example is encountered in equation (D.63), which may be stated as
This is related to Gauss’s formula (see for example ):
More generally, a partial θ-function has the form
Some identities for partial θ-functions are known. For example, in reference  it is shown that
D.5.4 Asymptotics for
A good starting point is the identity in equation (D.68). The left-hand side converges quickly if , but, when q is close to 1, another approach is necessary.
Theorem D.11 (Poisson’s sum formula)
Suppose that f is continuous for all , and is uniformly convergent for . Then
for all values of t where the right-hand side converges.
is continuous and periodic with period . In a Fourier expansion of h the coefficients would be
Moreover, by Fejér’s theorem, is Cesàro summable to for all t (since h is continuous and periodic).
(p.574) Hence, by replacing h in the last integral with the uniformly convergent series over f, one obtains
The right-hand side evaluates to an, and therefore the Fourier series for is as claimed above.
Corollary D.12 (The θ-transformation formula)
For all values of , such that ,
Put in theorem D.11. Then converges uniformly for , and . The Poisson sum formula gives(D.73)
where the integral above gives the Fourier coefficients. It remains to evaluate these coefficients.
Assume that and substitute :
The contour integral on the right evaluates as
using Cauchy’s theorem. This completes the evaluation of the Fourier coefficients in equation (D.73).
Substitution of the result and replacing in the summation on the right-hand side of equation (D.73) completes the proof.
For Euler’s function,
where . For the right-hand side converges quickly.
Put , put and define r by . Substitute these variables in the left-hand side of Corollary D.12 and then simplify. This shows that
Comparison to equation (D.68) gives
It remains to simplify the right-hand side.
Substitute t and s on the right-hand side and simplify:
The sum on the right-hand side is absolutely convergent if . Collecting terms,
The right-hand side is evaluated by summing along n in residue classes modulo 6: replace and sum over ℓ from to 2.
Comparing the terms in the sum over ℓ shows that the terms for and cancel. The terms for both and are equal under the exchange of , up to phase factors. This is similarly the case for and . This simplifies the expressions above to
Evaluate the cosines and replace to complete the proof.
Taking logarithms of the result in theorem D.13 and keeping the term gives the following asymptotic formula for as :
The function .
(p.576) This gives the approximation
For additional results, see, for example, the paper by Moak .
D.5.5 Asymptotics for
First examine the limit for and assume that for all .
If , and for all , then .
Surely, for all , and is monotone decreasing, so the limit exists and is less than or equal to 1.
It remains to show that the limit is not 0.
For any positive , . Moreover, for any small , there exists a such that if , since and since . Hence, if .
Thus, assume that ; then
Take to obtain
which is greater than 0.
Asymptotic approximations for the q-Pochhammer function can be determined using the Euler-Maclaurin theorem. This can be determined directly or indirectly by first determining an approximation for the q-gamma function (see, for example, references  and ).
Define to be the dilogarithm:
(p.577) Theorem D.16
If , and , then
For fixed , this term vanishes as .
The Euler-Maclaurin formula gives
The integral over can be done by expanding first the logarithm and then integrating term by term; the result is a sequence of terms giving rise to dilogarithms and logarithms.
It remains only to examine the remainder. Observe that
Next, consider the derivative in R1 above and compute it to see that
This completes the proof.
Taking in theorem D.16 gives the following corollary:
If , and , and if , then
or if is used, then
where R1 approaches 0 uniformly as for any .
(p.578) By this corollary,
where uniformly as . For example, if for , then
D.6 Asymptotics from the generating function
If the generating function of a function qn on , defined by
is known, then qn may in principle be found by using Darboux’s theorem. Darboux’s theorem has the following formulation (see, for example, reference ).
Theorem D.18 (Darboux’s theorem)
Let be an analytic function with Laurent expansion
in the annulus .
Let be a function which is analytic in and with Laurent expansion given by
Suppose that the difference of the m-th derivatives of and has a finite number of singularities at such that
for some positive constants , as . Then
(p.579) D.7 Convergence of continued fractions
Finite fractions are denoted by
(For example, , and ).
Taking gives the infinite continued fraction . The n-th approximation to is , obtained by truncating the fraction at n and putting :
Useful theorems on the convergence of continued fractions are the following.
(Pringsheim ) Let and be sequences in such that . Then the continued fraction converges absolutely to with .
(Worpitzky ) Let be a sequence in and let K be a continued fraction given by
If for all , then K converges absolutely and . Moreover, if, in addition, , where and is the n-th approximant of K, then .
Theorem D.21 (Van Vleck )
If , then a condition that is necessary for the continued fraction
to converge for all values of is that the series
is convergent. This condition is also sufficient if for all values of n.