Euler–Maclaurin formula
Euler–Maclaurin formula
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
![[m,n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/96654677b42a0d452d661331233f97a1facc9a1e)
can be approximated by the sum (or vice versa)
or alternatively
The remainder term
![[r,r+1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad82a58e42a973da1a88c8d9bfdab31275a38c83)
The periodized Bernoulli functions are defined as
Low-order cases
Applications
The Basel problem
The Basel problem is to determine the sum
Sums involving a polynomial
Approximation of integrals
![{\displaystyle {\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}}[f'(x_{1})-f'(x_{N})]-{\frac {h^{4}}{720}}[f'''(x_{1})-f'''(x_{N})]+\cdots .\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9440b1d62e73ff7552fe73e2b9a982cdadbedf3d)
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
Examples
If s is an integer greater than 1 we have:
![{\displaystyle \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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a74bba0fefc07c90b9eb752cb72358f54b1ad3b2)
Collecting the constants into a value of the Riemann zeta function, we can write an asymptotic expansion:
For s equal to 2 this simplifies to
or
When s = 1, the corresponding technique gives an asymptotic expansion for the harmonic numbers:
Proofs
Derivation by mathematical induction
We outline the argument given in Apostol.[1]
The Bernoulli polynomials Bn(x) and the periodic Bernoulli functions Pn(x) for n = 0, 1, 2, ... were introduced above.
The first several Bernoulli polynomials are
The values Bn(0) are the Bernoulli numbers B**n. Notice that for n ≠ 1 we have
and for n = 1,
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,
Let k be an integer, and consider the integral
where
Integrating by parts, we get
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8025cd6b9b630485eda98e72fce7c31a2e6245ff)
Adding (f(n) − f(0))/2 to both sides and rearranging, we have
This is the p = 1 case of the summation formula. To continue the induction, we apply integration by parts to the error term:
where
The result of integrating by parts is
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e5e2b4c4601927898b969a856ce5f38cfe2c85b)
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,
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
Euler summation
Gauss–Kronrod quadrature formula
Darboux's formula
Euler–Boole summation