Nørlund–Rice integral
In mathematics, the Nørlund–Rice integral, sometimes called Rice's method, relates the nth forward difference of a function to a contour integral on the complex plane. It commonly appears in the theory of finite differences and has also been applied in computer science and graph theory to estimate binary tree lengths. It is named in honour of Niels Erik Nørlund and Stephen O. Rice. Nørlund's contribution was to define the integral; Rice's contribution was to demonstrate its utility by applying saddle-point techniques to its evaluation.
Definition
The nth forward difference of a function f is given bywhere is the binomial coefficient.
The Nørlund–Rice integral is given by
where f is understood to be meromorphic, α is an integer,, and the contour of integration is understood to circle the poles located at the integers α,..., n, but encircles neither integers 0,..., nor any of the poles of f. The integral may also be written as
where B is the Euler beta function. If the function is polynomially bounded on the right hand side of the complex plane, then the contour may be extended to infinity on the right hand side, allowing the transform to be written as
where the constant c is to the left of α.
Poisson–Mellin–Newton cycle
The Poisson–Mellin–Newton cycle, noted by Flajolet et al. in 1985, is the observation that the resemblance of the Nørlund–Rice integral to the Mellin transform is not accidental, but is related by means of the binomial transform and the Newton series. In this cycle, let be a sequence, and let g be the corresponding Poisson generating function, that is, letTaking its Mellin transform
one can then regain the original sequence by means of the Nörlund–Rice integral :
where Γ is the gamma function which cancels with the gamma from Ramanujan's Master Theorem.