Informatics Educational Institutions & Programs

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 $m$ and $n$ are natural numbers and $f (x)$ is a real or complex valued continuous function for real numbers $x$ in the interval $[m, n]$ , then the integral

I=\int _{m}^{n}f(x)\,dx

can be approximated by the sum (or vice versa)

S=f(m+1)+\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

f (k) (x)

evaluated at the endpoints of the interval, that is to say

x = m

and

x = n

.

Explicitly, for $p$ a positive integer and a function $f (x)$ that is $p$ times continuously differentiable on the interval $[m, n]$ , we have

S-I=\sum _{k=1}^{p}{{\frac {B_{k}}{k!}}\left(f^{(k-1)}(n)-f^{(k-1)}(m)\right)}+R_{p},

where

B k

is the

k

th Bernoulli number (with

B 1 = 1 / 2

) and

R p

is an error term which depends on

n

,

m

,

p

, and

f

and is usually small for suitable values of

p

.

The formula is often written with the subscript taking only even values, since the odd Bernoulli numbers are zero except for $B 1$ . In this case we have^[1]^[2]

\sum _{i=m}^{n}f(i)=\int _{m}^{n}f(x)\,dx+{\frac {f(n)+f(m)}{2}}+\sum _{k=1}^{\left\lfloor {\frac {p}{2}}\right\rfloor }{\frac {B_{2k}}{(2k)!}}\left(f^{(2k-1)}(n)-f^{(2k-1)}(m)\right)+R_{p},

or alternatively

\sum _{i=m+1}^{n}f(i)=\int _{m}^{n}f(x)\,dx+{\frac {f(n)-f(m)}{2}}+\sum _{k=1}^{\left\lfloor {\frac {p}{2}}\right\rfloor }{\frac {B_{2k}}{(2k)!}}\left(f^{(2k-1)}(n)-f^{(2k-1)}(m)\right)+R_{p}.

The remainder term

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 $[r, r + 1]$ for $r = m, m + 1, \dots, n - 1$ . 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 $P k (x)$ . The Bernoulli polynomials may be defined recursively by $B 0 (x) = 1$ and, for $k \geq 1$ ,

{\begin{aligned}B_{k}'(x)&=kB_{k-1}(x),\\\int _{0}^{1}B_{k}(x)\,dx&=0.\end{aligned}}

The periodized Bernoulli functions are defined as

P_{k}(x)=B_{k}{\bigl (}x-\lfloor x\rfloor {\bigr )},

where

⌊ x ⌋

denotes the largest integer less than or equal to

x

, so that

x - ⌊ x ⌋

always lies in the interval

[0,1)

.

With this notation, the remainder term $R p$ equals

R_{p}=(-1)^{p+1}\int _{m}^{n}f^{(p)}(x){\frac {P_{p}(x)}{p!}}\,dx.

When $k > 0$ , it can be shown that for $0 \leq x \leq 1$ ,

{\bigl |}B_{k}(x){\bigr |}\leq {\frac {2\cdot k!}{(2\pi )^{k}}}\zeta (k),

where

ζ

denotes the Riemann zeta function; one approach to prove this inequality is to obtain the Fourier series for the polynomials

B k (x)

. The bound is achieved for even

k

when

x

is zero. The term

ζ (k)

may be omitted for odd

k

but the proof in this case is more complex (see Lehmer).^[3] Using this inequality, the size of the remainder term can be estimated as

\left|R_{p}\right|\leq {\frac {2\zeta (p)}{(2\pi )^{p}}}\int _{m}^{n}\left|f^{(p)}(x)\right|\,dx.

Low-order cases

The Bernoulli numbers from $B 1$ to $B 7$ are $1 / 2, 1 / 6, 0, - 1 / 30, 0, 1 / 42, 0$ . Therefore the low-order cases of the Euler–Maclaurin formula are:

{\begin{aligned}\sum _{i=m}^{n}f(i)-\int _{m}^{n}f(x)\,dx&={\frac {f(m)+f(n)}{2}}+\int _{m}^{n}f'(x)P_{1}(x)\,dx\\&={\frac {f(m)+f(n)}{2}}+{\frac {1}{6}}{\frac {f'(n)-f'(m)}{2!}}-\int _{m}^{n}f''(x){\frac {P_{2}(x)}{2!}}\,dx\\&={\frac {f(m)+f(n)}{2}}+{\frac {1}{6}}{\frac {f'(n)-f'(m)}{2!}}+\int _{m}^{n}f'''(x){\frac {P_{3}(x)}{3!}}\,dx\\&={\frac {f(m)+f(n)}{2}}+{\frac {1}{6}}{\frac {f'(n)-f'(m)}{2!}}-{\frac {1}{30}}{\frac {f'''(n)-f'''(m)}{4!}}-\int _{m}^{n}f^{(4)}(x){\frac {P_{4}(x)}{4!}}\,dx\\&={\frac {f(m)+f(n)}{2}}+{\frac {1}{6}}{\frac {f'(n)-f'(m)}{2!}}-{\frac {1}{30}}{\frac {f'''(n)-f'''(m)}{4!}}+\int _{m}^{n}f^{(5)}(x){\frac {P_{5}(x)}{5!}}\,dx\\&={\frac {f(m)+f(n)}{2}}+{\frac {1}{6}}{\frac {f'(n)-f'(m)}{2!}}-{\frac {1}{30}}{\frac {f'''(n)-f'''(m)}{4!}}+{\frac {1}{42}}{\frac {f^{(5)}(n)-f^{(5)}(m)}{6!}}-\int _{m}^{n}f^{(6)}(x){\frac {P_{6}(x)}{6!}}\,dx\\&={\frac {f(m)+f(n)}{2}}+{\frac {1}{6}}{\frac {f'(n)-f'(m)}{2!}}-{\frac {1}{30}}{\frac {f'''(n)-f'''(m)}{4!}}+{\frac {1}{42}}{\frac {f^{(5)}(n)-f^{(5)}(m)}{6!}}+\int _{m}^{n}f^{(7)}(x){\frac {P_{7}(x)}{7!}}\,dx.\end{aligned}}

Applications

The Basel problem

The Basel problem is to determine the sum

1+{\frac {1}{4}}+{\frac {1}{9}}+{\frac {1}{16}}+{\frac {1}{25}}+\cdots =\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}.

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.^[4]

Sums involving a polynomial

If $f$ is a polynomial and $p$ is big enough, then the remainder term vanishes. For instance, if $f (x) = x 3$ , we can choose $p = 2$ to obtain, after simplification,

\sum _{i=0}^{n}i^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}.

Approximation of integrals

The formula provides a means of approximating a finite integral. Let $a < b$ be the endpoints of the interval of integration. Fix $N$ , the number of points to use in the approximation, and denote the corresponding step size by $h = b - a / N - 1$ . Set $x i = a + (i - 1) h$ , so that $x 1 = a$ and $x N = b$ . Then:^[5]

{\begin{aligned}I&=\int _{a}^{b}f(x)\,dx\\&\sim h\left({\frac {f(x_{1})}{2}}+f(x_{2})+\cdots +f(x_{N-1})+{\frac {f(x_{N})}{2}}\right)+{\frac {h^{2}}{12}}{\bigl [}f'(x_{1})-f'(x_{N}){\bigr ]}-{\frac {h^{4}}{720}}{\bigl [}f'''(x_{1})-f'''(x_{N}){\bigr ]}+\cdots \end{aligned}}

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 $p$ , depending upon $f$ and $h$ , such that the terms past order $p$ increase rapidly. Thus, the remainder term generally demands close attention.^[5]

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

\sum _{n=a}^{b}f(n)\sim \int _{a}^{b}f(x)\,dx+{\frac {f(b)+f(a)}{2}}+\sum _{k=1}^{\infty }\,{\frac {B_{2k}}{(2k)!}}\left(f^{(2k-1)}(b)-f^{(2k-1)}(a)\right),

where $a$ and $b$ are integers.^[6] Often the expansion remains valid even after taking the limits $a \to -\infty$ or $b \to +\infty$ 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,

\sum _{k=0}^{\infty }{\frac {1}{(z+k)^{2}}}\sim \underbrace {\int _{0}^{\infty }{\frac {1}{(z+k)^{2}}}\,dk} _{={\dfrac {1}{z}}}+{\frac {1}{2z^{2}}}+\sum _{t=1}^{\infty }{\frac {B_{2t}}{z^{2t+1}}}.

Here the left-hand side is equal to $ψ (1) (z)$ , namely the first-order polygamma function defined by

\psi ^{(1)}(z)={\frac {d^{2}}{dz^{2}}}\log \Gamma (z);

the gamma function $Γ(z)$ is equal to $(z - 1)!$ when $z$ is a positive integer. This results in an asymptotic expansion for $ψ (1) (z)$ . 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 $s$ is an integer greater than 1 we have:

\sum _{k=1}^{n}{\frac {1}{k^{s}}}\approx {\frac {1}{s-1}}+{\frac {1}{2}}-{\frac {1}{(s-1)n^{s-1}}}+{\frac {1}{2n^{s}}}+\sum _{i=1}{\frac {B_{2i}}{(2i)!}}\left[{\frac {(s+2i-2)!}{(s-1)!}}-{\frac {(s+2i-2)!}{(s-1)!n^{s+2i-1}}}\right].

Collecting the constants into a value of the Riemann zeta function, we can write an asymptotic expansion:

\sum _{k=1}^{n}{\frac {1}{k^{s}}}\sim \zeta (s)-{\frac {1}{(s-1)n^{s-1}}}+{\frac {1}{2n^{s}}}-\sum _{i=1}{\frac {B_{2i}}{(2i)!}}{\frac {(s+2i-2)!}{(s-1)!n^{s+2i-1}}}.

For $s$ equal to 2 this simplifies to

\sum _{k=1}^{n}{\frac {1}{k^{2}}}\sim \zeta (2)-{\frac {1}{n}}+{\frac {1}{2n^{2}}}-\sum _{i=1}{\frac {B_{2i}}{n^{2i+1}}},

or

\sum _{k=1}^{n}{\frac {1}{k^{2}}}\sim {\frac {\pi ^{2}}{6}}-{\frac {1}{n}}+{\frac {1}{2n^{2}}}-{\frac {1}{6n^{3}}}+{\frac {1}{30n^{5}}}-{\frac {1}{42n^{7}}}+\cdots .

When $s = 1$ , the corresponding technique gives an asymptotic expansion for the harmonic numbers:

\sum _{k=1}^{n}{\frac {1}{k}}\sim \gamma +\log n+{\frac {1}{2n}}-\sum _{k=1}^{\infty }{\frac {B_{2k}}{2kn^{2k}}},

where

γ \approx 0.5772...

is the Euler–Mascheroni constant.

Proofs

Derivation by mathematical induction

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

The Bernoulli polynomials $B n (x)$ and the periodic Bernoulli functions $P n (x)$ for $n = 0, 1, 2, ...$ were introduced above.

The first several Bernoulli polynomials are

{\begin{aligned}B_{0}(x)&=1,\\B_{1}(x)&=x-{\tfrac {1}{2}},\\B_{2}(x)&=x^{2}-x+{\tfrac {1}{6}},\\B_{3}(x)&=x^{3}-{\tfrac {3}{2}}x^{2}+{\tfrac {1}{2}}x,\\B_{4}(x)&=x^{4}-2x^{3}+x^{2}-{\tfrac {1}{30}},\\&\,\,\,\vdots \end{aligned}}

The values $B n (1)$ are the Bernoulli numbers $B n$ . Notice that for $n \neq 1$ we have

B_{n}=B_{n}(1)=B_{n}(0),

and for

n = 1

,

B_{1}=B_{1}(1)=-B_{1}(0).

The functions $P n$ agree with the Bernoulli polynomials on the interval $[0, 1]$ and are periodic with period 1. Furthermore, except when $n = 1$ , they are also continuous. Thus,

P_{n}(0)=P_{n}(1)=B_{n}\quad {\text{for }}n\neq 1.

Let $k$ be an integer, and consider the integral

\int _{k}^{k+1}f(x)\,dx=\int _{k}^{k+1}u\,dv,

where

{\begin{aligned}u&=f(x),\\du&=f'(x)\,dx,\\dv&=P_{0}(x)\,dx&{\text{since }}P_{0}(x)&=1,\\v&=P_{1}(x).\end{aligned}}

Integrating by parts, we get

{\begin{aligned}\int _{k}^{k+1}f(x)\,dx&={\bigl [}uv{\bigr ]}_{k}^{k+1}-\int _{k}^{k+1}v\,du\\&={\bigl [}f(x)P_{1}(x){\bigr ]}_{k}^{k+1}-\int _{k}^{k+1}f'(x)P_{1}(x)\,dx\\&=B_{1}(1)f(k+1)-B_{1}(0)f(k)-\int _{k}^{k+1}f'(x)P_{1}(x)\,dx.\end{aligned}}

Using $B 1 (0) = - 1 / 2$ , $B 1 (1) = 1 / 2$ , and summing the above from $k = 0$ to $k = n - 1$ , we get

{\begin{aligned}\int _{0}^{n}f(x)\,dx&=\int _{0}^{1}f(x)\,dx+\cdots +\int _{n-1}^{n}f(x)\,dx\\&={\frac {f(0)}{2}}+f(1)+\dotsb +f(n-1)+{\frac {f(n)}{2}}-\int _{0}^{n}f'(x)P_{1}(x)\,dx.\end{aligned}}

Adding $f (n) - f (0) / 2$ to both sides and rearranging, we have

\sum _{k=1}^{n}f(k)=\int _{0}^{n}f(x)\,dx+{\frac {f(n)-f(0)}{2}}+\int _{0}^{n}f'(x)P_{1}(x)\,dx.

This is the $p = 1$ case of the summation formula. To continue the induction, we apply integration by parts to the error term:

\int _{k}^{k+1}f'(x)P_{1}(x)\,dx=\int _{k}^{k+1}u\,dv,

where

{\begin{aligned}u&=f'(x),\\du&=f''(x)\,dx,\\dv&=P_{1}(x)\,dx,\\v&={\tfrac {1}{2}}P_{2}(x).\end{aligned}}

The result of integrating by parts is

{\begin{aligned}{\bigl [}uv{\bigr ]}_{k}^{k+1}-\int _{k}^{k+1}v\,du&=\left[{\frac {f'(x)P_{2}(x)}{2}}\right]_{k}^{k+1}-{\frac {1}{2}}\int _{k}^{k+1}f''(x)P_{2}(x)\,dx\\&={\frac {B_{2}}{2}}(f'(k+1)-f'(k))-{\frac {1}{2}}\int _{k}^{k+1}f''(x)P_{2}(x)\,dx.\end{aligned}}

Summing from $k = 0$ to $k = n - 1$ and substituting this for the lower order error term results in the $p = 2$ case of the formula,

\sum _{k=1}^{n}f(k)=\int _{0}^{n}f(x)\,dx+{\frac {f(n)-f(0)}{2}}+{\frac {B_{2}}{2}}{\bigl (}f'(n)-f'(0){\bigr )}-{\frac {1}{2}}\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.

References

^ ^a ^b Apostol, T. M. (1 May 1999). "An Elementary View of Euler's Summation Formula". The American Mathematical Monthly. 106 (5). Mathematical Association of America: 409–418. doi:10.2307/2589145. ISSN 0002-9890. JSTOR 2589145.
^ "Digital Library of Mathematical Functions: Sums and Sequences". National Institute of Standards and Technology.
^ Lehmer, D. H. (1940). "On the maxima and minima of Bernoulli polynomials". The American Mathematical Monthly. 47 (8): 533–538. doi:10.2307/2303833. JSTOR 2303833.
^ Pengelley, David J. (2007). "Dances between continuous and discrete: Euler's summation formula". Euler at 300. MAA Spectrum. Washington, DC: Mathematical Association of America. pp. 169–189. arXiv:1912.03527. MR 2349549.
^ ^a ^b Devries, Paul L.; Hasbrun, Javier E. (2011). A first course in computational physics (2nd ed.). Jones and Bartlett Publishers. p. 156.
^ Abramowitz, Milton; Stegun, Irene A., eds. (1972). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. New York: Dover Publications. pp. 16, 806, 886. ISBN 978-0-486-61272-0.

External links

Weisstein, Eric W. "Euler–Maclaurin Integration Formulas". MathWorld.

[:0-1] Apostol, T. M. (1 May 1999). "An Elementary View of Euler's Summation Formula". The American Mathematical Monthly. 106 (5). Mathematical Association of America: 409–418. doi:10.2307/2589145. ISSN 0002-9890. JSTOR 2589145.

[DLMF-2] "Digital Library of Mathematical Functions: Sums and Sequences". National Institute of Standards and Technology.

[Lehmer-3] Lehmer, D. H. (1940). "On the maxima and minima of Bernoulli polynomials". The American Mathematical Monthly. 47 (8): 533–538. doi:10.2307/2303833. JSTOR 2303833.

[4] Pengelley, David J. (2007). "Dances between continuous and discrete: Euler's summation formula". Euler at 300. MAA Spectrum. Washington, DC: Mathematical Association of America. pp. 169–189. arXiv:1912.03527. MR 2349549.

[Devries-5] Devries, Paul L.; Hasbrun, Javier E. (2011). A first course in computational physics (2nd ed.). Jones and Bartlett Publishers. p. 156.

[6] Abramowitz, Milton; Stegun, Irene A., eds. (1972). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. New York: Dover Publications. pp. 16, 806, 886. ISBN 978-0-486-61272-0.

[1]

[2]

[3]

[4]

[5]

[6]

Calculus
Precalculus	Binomial theorem Concave function Continuous function Factorial Finite difference Free variables and bound variables Graph of a function Linear function Radian Rolle's theorem Secant Slope Tangent
Limits	Indeterminate form Limit of a function One-sided limit Limit of a sequence Order of approximation (ε, δ)-definition of limit
Differential calculus	Derivative Second derivative Partial derivative Differential Differential operator Mean value theorem Notation Leibniz's notation Newton's notation Rules of differentiation linearity Power Sum Chain L'Hôpital's Product General Leibniz's rule Quotient Other techniques Implicit differentiation Inverse functions and differentiation Logarithmic derivative Related rates Stationary points First derivative test Second derivative test Extreme value theorem Maximum and minimum Further applications Newton's method Taylor's theorem Differential equation Ordinary differential equation Partial differential equation Stochastic differential equation
Integral calculus	Antiderivative Arc length Riemann integral Basic properties Constant of integration Fundamental theorem of calculus Differentiating under the integral sign Integration by parts Integration by substitution trigonometric Euler Tangent half-angle substitution Partial fractions in integration Quadratic integral Trapezoidal rule Volumes Washer method Shell method Integral equation Integro-differential equation
Vector calculus	Derivatives Curl Directional derivative Divergence Gradient Laplacian Basic theorems Line integrals Green's Stokes' Gauss'
Multivariable calculus	Divergence theorem Geometric Hessian matrix Jacobian matrix and determinant Lagrange multiplier Line integral Matrix Multiple integral Partial derivative Surface integral Volume integral Advanced topics Differential forms Exterior derivative Generalized Stokes' theorem Tensor calculus
Sequences and series	Arithmetico-geometric sequence Types of series Alternating Binomial Fourier Geometric Harmonic Infinite Power Maclaurin Taylor Telescoping Tests of convergence Abel's Alternating series Cauchy condensation Direct comparison Dirichlet's Integral Limit comparison Ratio Root Term
Special functions and numbers	Bernoulli numbers e (mathematical constant) Exponential function Natural logarithm Stirling's approximation
History of calculus	Adequality Brook Taylor Colin Maclaurin Generality of algebra Gottfried Wilhelm Leibniz Infinitesimal Infinitesimal calculus Isaac Newton Fluxion Law of Continuity Leonhard Euler Method of Fluxions The Method of Mechanical Theorems
Lists	Differentiation rules List of integrals of exponential functions List of integrals of hyperbolic functions List of integrals of inverse hyperbolic functions List of integrals of inverse trigonometric functions List of integrals of irrational functions List of integrals of logarithmic functions List of integrals of rational functions List of integrals of trigonometric functions Secant Secant cubed List of limits Lists of integrals
Miscellaneous topics	Complex calculus Contour integral Differential geometry Manifold Curvature of curves of surfaces Tensor Euler–Maclaurin formula Gabriel's horn Integration Bee Proof that 22/7 exceeds π Regiomontanus' angle maximization problem Steinmetz solid

Informatics Educational Institutions & Programs

The formula

The remainder term

Low-order cases

Applications

The Basel problem

Sums involving a polynomial

Approximation of integrals

Asymptotic expansion of sums

Examples

Proofs

Derivation by mathematical induction

See also

References

Further reading

External links