One of my favorite formulas in all of mathematics is the Euler-Maclaurin summation formula. This post will talk a little about the formula and give several references for applications of it.

Here’s one way to express the infinite series version of the formula:

The series on the right-hand side doesn’t always converge. However, like Taylor’s series, if you truncate it after the *m*th term there is a remainder term that can sometimes be bounded. Also, is the *k*th Bernoulli number.

What I find fascinating about this formula is that it even exists: I would not have expected that such a relationship between the sum of and the corresponding integral of holds for all (sufficiently differentiable) functions . I’m also surprised that I had never even heard of it until I was flipping through Knuth’s *Art of Computer Programming* one day, a couple of years after I finished grad school. Frankly, I think it deserves to be better known.

Euler-Maclaurin can be proved by repeated application of integration by parts. Two good articles on the derivation are by Apostol [1] and Lampret [5]; Wikipedia also has a derivation for the first couple of terms.

Some of the more famous applications of Euler-Maclaurin are

- Deriving Faulhaber’s formula for the sums of the
*k*th powers of the first*n*positive integers. - Proving Stirling’s approximation for
*n*!. (See Section 9.6 in*Concrete Mathematics.*) - Proving that the
*n*th harmonic number has asymptotic . (This is also in Section 9.6 of*Concrete Mathematics*.)

It’s featured prominently in several math.SE answers, as well, such as

- Aryabhata’s answer to “Why is a polynomial with degree in ?”
- Aryabhata’s answer to “How to approximate ?”
- My answer to “Asymptotic behavior of sums of consecutive powers.”
- My answer to “Limit of – Part II.” (Aside: This may be the best answer I’ve ever given on math.SE.)

Finally, I’ve used it in a couple of my papers. In “The Euler-Maclaurin Formula and Sums of Powers” [7] I use it to prove that

See also Holland’s paper [3] for another derivation and my letter to the editor [8] correcting a mistake (!) in the paper and showing that the result can be generalized to

The other paper where I’ve used Euler-Maclaurin was [6], where I needed to prove that

for some more technical calculations later in the paper.

**References**

- Tom Apostol, “An Elementary View of Euler’s Summation Formula,”
*American Mathematical Monthly*106(5), May 1999, pp. 409-418. - Ronald L. Graham, Donald E. Knuth, and Oren Patashnik,
*Concrete Mathematics*, 2nd edition, Addison-Wesley, 1994. (See Chapter 9.) - Finbarr Holland, “,”
*Mathematics Magazine*83 (1), February 2010, pp. 51-54. - Donald E. Knuth,
*The Art of Computer Programming,*Vol. I, 3rd edition, Addison-Wesley, 1997. (See Section 1.2.11.2.) - Vito Lampret, “The Euler-Maclaurin and Taylor Formulas: Twin, Elementary Derivations,”
*Mathematics Magazine*74 (2), April 2001, pp. 109-122. - Michael Z. Spivey, “Asymptotic Moments of the Bottleneck Assignment Problem,”
*Mathematics of Operations Research*, 36 (2), May 2011, pp. 205-226. - Michael Z. Spivey, “The Euler-Maclaurin Formula and Sums of Powers,”
*Mathematics Magazine*, 79 (1), February 2006, pp. 61-65. - Michael Z. Spivey, Letter to the Editor,
*Mathematics Magazine*, 83 (1), February 2010, pp. 54-55.

An application of EM close to my heart is that one can use it to justify a number of applications of the trapezoidal rule. In particular, it can be used to justify the convergence rate of Romberg extrapolation, as well as showing why the trapezoidal rule tends to work well for integrating periodic functions over a period. Well, those are the two I remember…

Thanks for that. I was not aware that Euler-Maclaurin could be used in this way!

A great mathematician. Without the inventions the world would be different.