## Proof of the Recursive Identity for the Bernoulli Numbers

The Bernoulli numbers $B_n$ satisfy the recursive relationship $\displaystyle \sum_{k=0}^n \binom{n+1}{k} B_k = [n=0]$.  (Here, $[P]$ is the Iverson bracket, where $[P]$ evaluates to 1 if P is true and 0 if P is false.)  The relationship can be used to calculate the Bernoulli numbers fairly easily.  This post gives a proof of this relationship.

The exponential generating function for the Bernoulli numbers is given by $\displaystyle \frac{x}{e^x-1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}$.  The exponential generating function for the sequence consisting of 0 followed by an infinite number of 1’s is given by $\displaystyle e^x-1 = \sum_{n=1}^{\infty} \frac{x^n}{n!}$.  Multiplying these together, we obtain, thanks to the multiplication principle for exponential generating functions (see, for example, Concrete Mathematics [1], p. 365)

$\displaystyle x = \left(\sum_{n=1}^{\infty} \frac{x^n}{n!} \right) \left( \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}\right) = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n-1} \binom{n}{k} B_k \right) \frac{x^n}{n!}.$

But $x$ has generating function $\displaystyle \sum_{n=0}^{\infty} [n=1] \frac{x^n}{n!}$.  Thus we have $\displaystyle \sum_{k=0}^{n-1} \binom{n}{k} B_k = [n=1]$.  Replacing $n-1$ with n, we have the formula we were trying to prove:

$\displaystyle \sum_{k=0}^n \binom{n+1}{k} B_k = [n=0]$.

(As a side note, the Concrete Mathematics reference, p. 365, derives the exponential generating function for the Bernoulli numbers from the recurrence relation.)

References

1.  Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  Concrete Mathematics, 2nd edition.  Addison-Wesley, 1994.