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 mth term there is a remainder term that can sometimes be bounded. Also, is the kth 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  and Lampret ; 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 kth powers of the first n positive integers.
- Proving Stirling’s approximation for n!. (See Section 9.6 in Concrete Mathematics.)
- Proving that the nth 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”  I use it to prove that
See also Holland’s paper  for another derivation and my letter to the editor  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 , where I needed to prove that
for some more technical calculations later in the paper.
- 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 22.214.171.124.)
- 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.