The Euler-Maclaurin Summation Formula

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:

\sum_{j=0}^{m-1} f(j) = \int_0^m f(x) dx + \sum_{k=1}^{\infty} \frac{B_k}{k!} \Big(f^{(k-1)}(m)-f^{(k-1)}(0)\Big).

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, B_k 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 f(x) and the corresponding integral of f(x) holds for all (sufficiently differentiable) functions f.  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

  1. Deriving Faulhaber’s formula for the sums of the kth powers of the first n positive integers.
  2. Proving Stirling’s approximation for n!.  (See Section 9.6 in Concrete Mathematics.)
  3. Proving that the nth harmonic number H_n has asymptotic H_n = \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + O(n^{-4}).  (This is also in Section 9.6 of Concrete Mathematics.)

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

  1. Aryabhata’s answer to “Why is \sum\limits_{k=1}^{n} k^m  a polynomial with degree m+1  in n?”
  2. Aryabhata’s answer to “How to approximate \sum_{k=n}^{\infty}\dfrac{(\ln(k))^{2}}{k^{3}}?”
  3. My answer to “Asymptotic behavior of sums of consecutive powers.”
  4. My answer to “Limit of S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right) – 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

\lim_{m \rightarrow \infty} \bigg[ \bigg(\frac{1}{m}\bigg)^m + \bigg(\frac{2}{m}\bigg)^m + \cdots + \bigg(\frac{m-1}{m}\bigg)^m \bigg] = \frac{1}{e-1}.

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 \lim_{m \rightarrow \infty} \bigg[ \bigg(\frac{1}{m}\bigg)^m + \bigg(\frac{2}{m}\bigg)^m + \cdots + \bigg(\frac{m+k}{m}\bigg)^m \bigg] = \frac{e^{k+1}}{e-1}.

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

\sum_{k=1}^{n} \frac{(\log k)^p}{k} = \frac{1}{p+1} (\log n)^{p+1} + O\left(\frac{(\log n)^p}{n}\right)

for some more technical calculations later in the paper.

References

  1. Tom Apostol, “An Elementary View of Euler’s Summation Formula,” American Mathematical Monthly 106(5), May 1999, pp. 409-418.
  2. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.  (See Chapter 9.)
  3. Finbarr Holland, “\lim_{m \to \infty} (k/m)^m = e/(e-1),” Mathematics Magazine 83 (1), February 2010, pp. 51-54.
  4. Donald E. Knuth, The Art of Computer Programming, Vol. I, 3rd edition, Addison-Wesley, 1997.  (See Section 1.2.11.2.)
  5. Vito Lampret, “The Euler-Maclaurin and Taylor Formulas: Twin, Elementary Derivations,” Mathematics Magazine 74 (2), April 2001, pp. 109-122.
  6. Michael Z. Spivey, “Asymptotic Moments of the Bottleneck Assignment Problem,” Mathematics of Operations Research, 36 (2), May 2011, pp. 205-226.
  7. Michael Z. Spivey, “The Euler-Maclaurin Formula and Sums of Powers,” Mathematics Magazine, 79 (1), February 2006, pp. 61-65.
  8. Michael Z. Spivey, Letter to the Editor, Mathematics Magazine, 83 (1), February 2010, pp. 54-55.
Advertisements
This entry was posted in asymptotics, sequences and series. Bookmark the permalink.

3 Responses to The Euler-Maclaurin Summation Formula

  1. tpfto says:

    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…

  2. Aryabhatta says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s