Bernoulli Numbers and Faulhaber’s Formula

What is 200^5 + 201^5 + 202^5 + \cdots + 500^5?

Well, if a formula could be found for F_t(n) = \sum_{k=1}^n k^t, then this would just be F_5(500) - F_5(199). Enter Faulhaber…

I find the following sequence of formulae fascinating:

F_0(n) = \sum_{k=1}^n 1
= n;
F_1(n) = \sum_{k=1}^n k
= n(n+1)/2
= \frac{1}{2}n^2 + \frac{1}{2}n
F_2(n) = \sum_{k=1}^n k^2
= n(n+1)(2n+1)/6
= n(n+\frac{1}{2})(n+1)/12
= \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n
F_2(n) = \sum_{k=1}^n k^2
= n(n+1)(2n+1)/6
= n(n+\frac{1}{2})(n+1)/12
= \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n
F_3(n) = \sum_{k=1}^n k^3
= n^2(n+1)^2/4
= \frac{1}{4}n^4 + \frac{1}{2}n^3 + \frac{1}{4}n^2
F_4(n) = \sum_{k=1}^n k^4
= n(n+1)(2n+1)(3n^3+3n-1)/30
= \frac{1}{5}n^5 + \frac{1}{2}n^4 + \frac{1}{3}n^3 - \frac{1}{30}n
= n(n+\frac{1}{2})(n+1)\left(n+\dfrac{3+\sqrt{21}}{6}\right)\left(n+\dfrac{3-\sqrt{21}}{6}\right)
F_5(n) = \sum_{k=1}^n k^5
= n^2(n+1)^2(2n^2+2n-1)/12
= \frac{1}{6}n^6 + \frac{1}{2}n^5 + \frac{5}{12}n^4 - \frac{1}{12}n^2

… and so on …

(The right-hand sides may be expressed as polynomials in many forms: with one or many integral polynomial factors over an integer; with one or many monic polynomial factors over an integer; as separated terms with rational coefficients.)

What is fascinating is this: the left-hand sides of these equations have n terms, where n could be very large; but, the right-hand sides have a number of terms fixed by, and no greater than, t+1.

Faulhaber (perhaps; this is disputed) found the following general formula:

F_t(n) = \sum_{k=1}^n k^t

F_{t-1}(n) = \sum_{k=1}^n k^{t-1} = \dfrac{1}{t} \sum_{j=1}^{t} \dbinom{t}{j}B^*_{t-j}n^j

i.e.

F_t(n) = \sum_{k=1}^n k^t = \sum_{j=1}^{t+1} c_j n^j

where

c_j = \dfrac{1}{t+1} \dbinom{t+1}{j}B^*_{t+1-j}

where

\dbinom{s}{j} = \dfrac{s!}{j!(s-j)!} is a binomial coefficient, and

B^*_i = (-1)^i B_i where B_i is a Bernoulli number.

Finally, the Bernoulli numbers are generated by the recurrence

\sum_{k=0}^n \dbinom{n+1}{k}B_k = [n = 0]

i.e.

B_0 = 1 and \sum_{k=0}^n \dbinom{n+1}{k}B_k = 0 \;\bullet\;\forall n > 0.

It so happens that B_i = 0 \;\bullet\;\forall \text{ odd } i \ge 3, so

B^*_1 = -B_1 = \frac{1}{2}; and
B^*_i = B_i \;\bullet\;\forall i \ne 1.

Here’s a table of the first few (sign-adjusted) Bernoulli numbers:

i B^*_i
0 1
1 (+) 1/2
2 1/6 (corrected 2009/10/17)
3 0
4 −1/30
6 1/42
8 −1/30 (again)
10 5/66
12 −691/2730

(Oh, the answer is F_5(500) - F_5(199)
= 2,619,817,708,312,500 - 10,507,333,330,000
= 2,609,310,374,982,500.)

Advertisements

6 Responses to “Bernoulli Numbers and Faulhaber’s Formula”

  1. David Woodford Says:

    Great Post,
    I’m guessing the Bernoulli numbers have other uses as well.

    David

    • Rob Says:

      Hello David,

      Yes, the sequence of Bernoulli numbers crops up all over the place. I first came across it in the context of Taylor series (power series) for trigonometric functions: Taylor series of tan.

      Here are a couple of links for Bernoulli numbers:
      on Wikipedia;
      on Mathworld.

      Beware that some mathematicians define the Bernoulli numbers differently. (Some use “B_n” to mean B_2n or (−1)^n B_n, for example.)

      In fact, you’ll find the name Bernoulli cropping up elsewhere too, because there were many mathematicians in the Bernoulli family.

      Some other sequences and series you might wish to read about include the the binomial coefficients, the Eulerian numbers, the Fibonacci sequence and the Catalan numbers. Again, these are numbers that crop up in many places (even in nature).

      Thanks for your comment. (It’s the first from someone other than the person who suggested that I should start a blog.)

      How did you discover my post please? I’d guess that it was through WordPress rather than Google. I see that you have some useful posts too (also on WordPress—presumably one of these is a mirror of the other); I shall be browsing through those.

      Rob.

  2. David Woodford Says:

    I found it through wordpress, a search for maths I think, though I first arrived at a different page but looked at this one because it looked interesting.

    Your links are also usefull.

    With my blog I initially set it up on wordpress.com but am now trying to launch a self hosted version.

    Thanks,
    David

  3. Rob Says:

    (I have made a correction [typo; B_2 is +1/6, not -1/6]
    and have slightly improved the formatting.)

  4. Interesting Series and Sequences | B. Doyle Says:

    […] about Johann Faulhaber, I will refer you to [1] and the introductory remarks of [2]. [Also see this post for excellent examples and discussion of Faulhaber’s formula and Bernoulli numbers.] Just by […]

    • Rob Says:

      I highly recommend reading B. Doyle’s post in the above link:
      http://aperiodicity.com/2016/01/02/interesting-series-and-sequences/, and the references mentioned there, in particular: D. Knuth’s https://ia601000.us.archive.org/18/items/arxiv-math9207222/math9207222.pdf.

      One comment that B. Doyle makes is that B₁ should be −½ rather than +½. Whether B₁ should be ±½ seems to vary across the literature, and seems to be a matter of taste. Sometimes one is preferred over another in order to avoid an awkward (−1)^k factor in a sum (for the sake of the single oddly-indexed Bernoulli number for which it makes a difference: B₁).

      As I mentioned in an earlier comment, some authors even prefer to index over just our evenly-indexed values.

      As a result, when reading about the Bernoulli numbers, you should take careful note of which variant has been chosen.

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


%d bloggers like this: