In mathematics, the Euler–Maclaurin formula provides a powerful connection between integrals (see calculus) and sums. It can be used to approximate integrals by finite sums, or conversely to evaluate finite sums and infinite series using integrals and the machinery of calculus. For example, many asymptotic expansions are derived from the formula, and Faulhaber's formula for the sum of powers is an immediate consequence.
The formula was discovered independently by Leonhard Euler and Colin Maclaurin around 1735 (and later generalized as Darboux's formula). Euler needed it to compute slowly converging infinite series while Maclaurin used it to calculate integrals.
If m and n are natural numbers and f(x) is a smooth (meaning: sufficiently often differentiable), analytic function of exponential type < 2π defined for all real numbers x in the interval , then the integral
can be approximated by the sum (or vice versa)
(see trapezoidal rule). The Euler–Maclaurin formula provides expressions for the difference between the sum and the integral in terms of the higher derivatives ƒ(k) at the end points of the interval m and n. Explicitly, for any natural number p, we have
where B1 = +1/2, B2 = 1/6, B3 = 0, B4 = −1/30, B5 = 0, B6 = 1/42, B7 = 0, B8 = −1/30, … are the Bernoulli numbers, and R is an error term which is normally small for suitable values of p and depends on n, m, p and f.
The formula is often written with the subscript taking only even values, since the odd Bernoulli numbers are zero except for B1, in which case we have
The remainder term
Then the periodic Bernoulli functions Pn are defined as
where denotes the largest integer that is not greater than x. Then, in terms of Pn(x), the remainder term R can be written as
or equivalently, integrating by parts, assuming ƒ(2p) is differentiable again and recalling that all odd Bernoulli numbers (but the first one) are zero:
When n > 0, it can be shown that
where ζ denotes the Riemann zeta function (see Lehmer; one approach to prove the inequality is to obtain the Fourier series for the polynomials Bn). The bound is achieved for even n when x is zero. Using this inequality, the size of the remainder term can be estimated using
In the end, we get the following simple formula:
Where 'N' is the number of points in the interval of integration, from to .
The Basel problem
The Basel problem asks to determine the sum
Euler computed this sum to 20 decimal places with only a few terms of the Euler–Maclaurin formula in 1735. This probably convinced him that the sum equals π2 / 6, which he proved in the same year. Parseval's identity for the Fourier series of f(x) = x gives the same result.
Sums involving a polynomial
If f is a polynomial and p is big enough, then the remainder term vanishes. For instance, if f(x) = x3, we can choose p = 2 to obtain after simplification
(see Faulhaber's formula).
The Euler–Maclaurin formula is also used for detailed error analysis in numerical quadrature. It explains the superior performance of the trapezoidal rule on smooth periodic functions and is used in certain extrapolation methods. Clenshaw–Curtis quadrature is essentially a change of variables to cast an arbitrary integral in terms of integrals of periodic functions where the Euler–Maclaurin approach is very accurate (in that particular case the Euler–Maclaurin formula takes the form of a discrete cosine transform). This technique is known as a periodizing transformation.
Asymptotic expansion of sums
where a and b are integers. Often the expansion remains valid even after taking the limits or , or both. In many cases the integral on the right-hand side can be evaluated in closed form in terms of elementary functions even though the sum on the left-hand side cannot. Then all the terms in the asymptotic series can be expressed in terms of elementary functions. For example,
Here the left-hand side is equal to , namely the first-order polygamma function defined through ; the gamma function is equal to if is a positive integer. This results in an asymptotic expansion for . That expansion, in turn, serves as the starting point for one of the derivations of precise error estimates for Stirling's approximation of the factorial function.
Derivation by mathematical induction
We follow the argument given in Apostol.
The Bernoulli polynomials Bn(x), n = 0, 1, 2, … may be defined recursively as follows:
The first several of these are
The values Bn(0) are the Bernoulli numbers. Notice that for n ≠ 1 we have
For n = 1,
We define the periodic Bernoulli functions Pn by
where denotes the largest integer that is not greater than x. So Pn agree with the Bernoulli polynomials on the interval (0, 1) and are periodic with period 1. Thus,
Let k be an integer, and consider the integral
Integrating by parts, we get
Summing the above from k = 0 to k = n − 1, we get
Adding (f(n) - f(0))/2 to both sides and rearranging, we have
The last two terms therefore give the error when the integral is taken to approximate the sum.
Integrating by parts again, we get
Then summing from k = 0 to k = n − 1, and then replacing the last integral in (1) with what we have thus shown to be equal to it, we have
By now the reader will have guessed that this process can be iterated. In this way we get a proof of the Euler–Maclaurin summation formula by mathematical induction, in which the induction step relies on integration by parts and on the identities for periodic Bernoulli functions.
- Devries, Paul L.; Hasbrun, Javier E. (2011). A first course in computational physics. (2nd ed.). Jones and Bartlett Publishers. p. 156.
- Pengelley, David J. "Dances between continuous and discrete: Euler's summation formula", in: Robert Bradley and Ed Sandifer (Eds), Proceedings, Euler 2K+2 Conference (Rumford, Maine, 2002), Euler Society, 2003.
- Abramowitz & Stegun (1972), 23.1.30
- Apostol, T. M. (1 May 1999). "An Elementary View of Euler's Summation Formula". The American Mathematical Monthly (Mathematical Association of America) 106 (5): 409–418. doi:10.2307/2589145. ISSN 0002-9890. JSTOR 2589145.
- Abramowitz, Milton; Stegun, Irene A., eds. (1972). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. New York: Dover Publications. ISBN 978-0-486-61272-0. tenth printing., pp. 16, 806, 886
- Weisstein, Eric W., "Euler–Maclaurin Integration Formulas", MathWorld.
- Gourdon, Xavier; Sebah, Pascal Introduction on Bernoulli's numbers, (2002)
- Lehmer, D.H., "On the Maxima and Minima of Bernoulli Polynomials", American Mathematical Monthly, volume 47, pages 533–538 (1940)
- Montgomery, Hugh L.; Vaughan, Robert C. (2007). Multiplicative number theory I. Classical theory. Cambridge tracts in advanced mathematics 97. pp. 495–519. ISBN 0-521-84903-9.