Euler–Maclaurin formula explained

In mathematics, the Euler–Maclaurin formula is a formula for the difference between an integral and a closely related sum. 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. Euler needed it to compute slowly converging infinite series while Maclaurin used it to calculate integrals. It was later generalized to Darboux's formula.

The formula

If and are natural numbers and is a real or complex valued continuous function for real numbers in the interval, then the integral$$I\; =\; \backslash int\_m^n\; f(x)\backslash ,dx$$can be approximated by the sum (or vice versa)$$S\; =\; f(m\; +\; 1)\; +\; \backslash cdots\; +\; f(n\; -\; 1)\; +\; f(n)$$(see rectangle method). The Euler–Maclaurin formula provides expressions for the difference between the sum and the integral in terms of the higher derivatives evaluated at the endpoints of the interval, that is to say and .

Explicitly, for a positive integer and a function that is times continuously differentiable on the interval, we have$$S\; -\; I\; =\; \backslash sum\_^p\; +\; R\_p,$$where is the th Bernoulli number (with) and is an error term which depends on,,, and and is usually small for suitable values of .

The formula is often written with the subscript taking only even values, since the odd Bernoulli numbers are zero except for . In this case we have^[1] $$\backslash sum\_^n\; f(i)\; =\; \backslash int^n\_m\; f(x)\backslash ,dx\; +\; \backslash frac\; +\; \backslash sum\_^\; \backslash frac\; \backslash left(f^(n)\; -\; f^(m)\backslash right)\; +\; R\_p,$$or alternatively$$\backslash sum\_^n\; f(i)\; =\; \backslash int^n\_m\; f(x)\backslash ,dx\; +\; \backslash frac\; +\; \backslash sum\_^\; \backslash frac\; \backslash left(f^(n)\; -\; f^(m)\backslash right)\; +\; R\_p.$$

The remainder term

See also: Bernoulli polynomials.

The remainder term arises because the integral is usually not exactly equal to the sum. The formula may be derived by applying repeated integration by parts to successive intervals for . The boundary terms in these integrations lead to the main terms of the formula, and the leftover integrals form the remainder term.

The remainder term has an exact expression in terms of the periodized Bernoulli functions . The Bernoulli polynomials may be defined recursively by and, for,The periodized Bernoulli functions are defined as$$P\_k(x)\; =\; B\_k\backslash bigl(x\; -\; \backslash lfloor\; x\backslash rfloor\backslash bigr),$$where denotes the largest integer less than or equal to, so that always lies in the interval .

With this notation, the remainder term equals$$R\_\; =\; (-1)^\backslash int\_m^n\; f^(x)\; \backslash frac\backslash ,dx.$$

When, it can be shown that for,$$\backslash bigl|B\_k(x)\backslash bigr|\; \backslash le\; \backslash frac\backslash zeta(k),$$where denotes the Riemann zeta function; one approach to prove this inequality is to obtain the Fourier series for the polynomials . The bound is achieved for even when is zero. The term may be omitted for odd but the proof in this case is more complex (see Lehmer).^[2] Using this inequality, the size of the remainder term can be estimated as$$\backslash left|R\_p\backslash right|\; \backslash leq\; \backslash frac\backslash int\_m^n\; \backslash left|f^(x)\backslash right|\backslash ,dx.$$

Low-order cases

The Bernoulli numbers from to are . Therefore the low-order cases of the Euler–Maclaurin formula are:(x)\frac\,dx \\&=\frac + \frac\frac + \int_m^n f(x)\frac\,dx \\&=\frac + \frac\frac - \frac\frac-\int_m^n f^(x) \frac\, dx \\&=\frac + \frac\frac - \frac\frac + \int_m^n f^(x)\frac\,dx \\&=\frac + \frac\frac - \frac\frac + \frac\frac - \int_m^n f^(x)\frac\,dx \\&=\frac + \frac\frac - \frac\frac + \frac\frac + \int_m^n f^(x)\frac\,dx.\end

Applications

The Basel problem

The Basel problem is to determine the sum$$1\; +\; \backslash frac14\; +\; \backslash frac19\; +\; \backslash frac1\; +\; \backslash frac1\; +\; \backslash cdots\; =\; \backslash sum\_^\backslash infty\; \backslash frac.$$

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, which he proved in the same year.^[3]

Sums involving a polynomial

See also: Faulhaber's formula. If is a polynomial and is big enough, then the remainder term vanishes. For instance, if, we can choose to obtain, after simplification,$$\backslash sum\_^n\; i^3\; =\; \backslash left(\backslash frac\backslash right)^2.$$

Approximation of integrals

The formula provides a means of approximating a finite integral. Let be the endpoints of the interval of integration. Fix, the number of points to use in the approximation, and denote the corresponding step size by . Set, so that and . Then:^[4]

This may be viewed as an extension of the trapezoid rule by the inclusion of correction terms. Note that this asymptotic expansion is usually not convergent; there is some, depending upon and, such that the terms past order increase rapidly. Thus, the remainder term generally demands close attention.^[4]

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

In the context of computing asymptotic expansions of sums and series, usually the most useful form of the Euler–Maclaurin formula is$$\backslash sum\_^b\; f(n)\; \backslash sim\; \backslash int\_a^b\; f(x)\backslash ,dx\; +\; \backslash frac\; +\; \backslash sum\_^\backslash infty\; \backslash ,\backslash frac\; \backslash left(f^(b)\; -\; f^(a)\backslash right),$$

where and are integers.^[5] 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,$$\backslash sum\_^\backslash infty\; \backslash frac\; \backslash sim\; \backslash underbrace\_\; +\; \backslash frac\; +\; \backslash sum\_^\backslash infty\; \backslash frac.$$

Here the left-hand side is equal to, namely the first-order polygamma function defined by

\psi ^{(1)} (z) = (d ^{2})/(dz ^{2}) log \Gamma(z); the gamma function is equal to when 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.

Examples

If is an integer greater than 1 we have:$$\backslash sum\_^n\; \backslash frac\; \backslash approx\; \backslash frac\; 1+\backslash frac\; 12-\backslash frac\; 1+\backslash frac\; 1+\backslash sum\_\backslash frac\backslash left[\backslash frac\{(s+2i-2)!\}\{(s-1)!\}-\backslash frac\{(s+2i-2)!\}\{(s-1)!n^\{s+2i-1\}\}\backslash right].$$

Collecting the constants into a value of the Riemann zeta function, we can write an asymptotic expansion:$$\backslash sum\_^n\; \backslash frac\; \backslash sim\backslash zeta(s)-\backslash frac\; 1+\backslash frac\; 1-\backslash sum\_\backslash frac\backslash frac.$$

For equal to 2 this simplifies to$$\backslash sum\_^n\; \backslash frac\; \backslash sim\backslash zeta(2)-\backslash frac\; 1n+\backslash frac\; 1-\backslash sum\_\backslash frac,$$or$$\backslash sum\_^n\; \backslash frac\; \backslash sim\; \backslash frac\; -\backslash frac\; +\backslash frac\; -\backslash frac+\backslash frac-\backslash frac\; +\; \backslash cdots.$$

When, the corresponding technique gives an asymptotic expansion for the harmonic numbers:$$\backslash sum\_^n\; \backslash frac\; \backslash sim\; \backslash gamma\; +\; \backslash log\; n\; +\; \backslash frac\; -\; \backslash sum\_^\backslash infty\; \backslash frac,$$where is the Euler–Mascheroni constant.

Proofs

Derivation by mathematical induction

We outline the argument given in Apostol.^[6]

The Bernoulli polynomials and the periodic Bernoulli functions for were introduced above.

The first several Bernoulli polynomials are

The values are the Bernoulli numbers . Notice that for we have$$B\_n\; =\; B\_n(1)\; =\; B\_n(0),$$and for,$$B\_1\; =\; B\_1(1)\; =\; -B\_1(0).$$

The functions agree with the Bernoulli polynomials on the interval and are periodic with period 1. Furthermore, except when, they are also continuous. Thus,$$P\_n(0)\; =\; P\_n(1)\; =\; B\_n\; \backslash quad\; \backslash textn\; \backslash neq\; 1.$$

Let be an integer, and consider the integral$$\backslash int\_k^\; f(x)\backslash ,dx\; =\; \backslash int\_k^\; u\backslash ,dv,$$where

Integrating by parts, we get

Using,, and summing the above from to, we get

Adding to both sides and rearranging, we have$$\backslash sum\_^n\; f(k)\; =\; \backslash int\_0^n\; f(x)\backslash ,dx\; +\; \backslash frac\; +\; \backslash int\_0^n\; f\text{'}(x)\; P\_1(x)\backslash ,dx.$$

This is the case of the summation formula. To continue the induction, we apply integration by parts to the error term:$$\backslash int\_k^\; f\text{'}(x)P\_1(x)\backslash ,dx\; =\; \backslash int\_k^\; u\backslash ,dv,$$where(x)\,dx, \\ dv &= P_1(x)\,dx, \\ v &= \tfracP_2(x).\end

The result of integrating by parts is(x)P_2(x)\,dx \\ &= \frac(f'(k + 1) - f'(k)) - \frac\int_k^ f(x)P_2(x)\,dx.\end

Summing from to and substituting this for the lower order error term results in the case of the formula,$$\backslash sum\_^n\; f(k)\; =\; \backslash int\_0^n\; f(x)\backslash ,dx\; +\; \backslash frac\; +\; \backslash frac\backslash bigl(f\text{'}(n)\; -\; f\text{'}(0)\backslash bigr)\; -\; \backslash frac\backslash int\_0^n\; f$$(x)P_2(x)\,dx.

This process can be iterated. In this way we get a proof of the Euler–Maclaurin summation formula which can be formalized by mathematical induction, in which the induction step relies on integration by parts and on identities for periodic Bernoulli functions.

See also

• Cesàro summation
• Euler summation
• Gauss–Kronrod quadrature formula
• Darboux's formula
• Euler–Boole summation

Further reading

• H. W. . Gould . William . Squire . Maclaurin's second formula and its generalization . 1963. Amer. Math. Monthly . 70 . 1 . 44–52. 2312783 . 0146551 . 10.2307/2312783.
• Web site: Gourdon . Xavier. Sebah. Pascal . Introduction on Bernoulli's numbers. 2002.
• Erich . Martensen . On the generalized Euler-Maclaurin formula. Z. Angew. Math. Mech. . 85 . 12 . 858–863 . 10.1002/zamm.200410217 . 2184846 . 2005. 2005ZaMM...85..858M . 123419717 .
• Book: Hugh L. . Montgomery . Hugh Montgomery (mathematician) . Robert C. . Vaughan . Robert Charles Vaughan (mathematician) . Multiplicative number theory I. Classical theory . Cambridge tracts in advanced mathematics . 97 . 2007 . 978-0-521-84903-6 . 495–519.

Notes and References

1. Web site: Digital Library of Mathematical Functions: Sums and Sequences. National Institute of Standards and Technology.
2. Lehmer. D. H.. D. H. Lehmer . On the maxima and minima of Bernoulli polynomials . 1940 . The American Mathematical Monthly. 47. 8. 533–538 . 10.2307/2303833. 2303833.
3. Book: Pengelley, David J. . 1912.03527 . Dances between continuous and discrete: Euler's summation formula . Washington, DC . 2349549 . 169–189 . Mathematical Association of America . MAA Spectrum . Euler at 300 . 2007.
4. Book: Devries . Paul L. . Hasbrun . Javier E. . A first course in computational physics. . 2nd . Jones and Bartlett Publishers . 2011 . 156.
5. Book: Abramowitz . Milton . Milton Abramowitz . Stegun . Irene A. . Irene Stegun . . . New York . 978-0-486-61272-0 . 1972 . 16, 806, 886.
6. T. M. . An Elementary View of Euler's Summation Formula . . 106 . 1 May 1999 . 5 . 409–418 . 0002-9890. Apostol . 10.2307/2589145. Tom M. Apostol. Mathematical Association of America. 2589145.