|
A very classic problem is this: what is the sum of the numbers from $1$ to $100$ ? The answer is $5050$ , and there are a number of ways to see it. Before stating them, we generalize the problem somewhat: What is $\sum_{k=1}^n k$ ?
Theorem 1 $$ \sum_{k=1}^n k = \frac{n(n+1)}{2} $$
Proof. Write the sum twice:
which is exactly $n(n+1)$ , so
Having seen this, it is natural to generalize this question further, and ask: What is $\sum_{k=1}^n k^r$ , for any integer $r>0$ ?
This question, being so general, does not have such a tidy answer, but it can be solved.
Theorem 2 Let $B_m$ denote the $m$ th Bernoulli number, and let $r$ be a positive integer. Then $$ \sum_{k=0}^n k^r = \sum_{l=1}^{r+1} \binom{r+1}{l}\frac{B_{r+1-l}}{r+1}(n+1)^l. $$
Observe that this formula is a polynomial in $n$ of degree $r+1$ ; for a given $r$ , we can look up all the Bernoulli numbers we need and write down the polynomial explicitly. For example: $$ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}, $$ $$ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{(n(n+1))^2}{4}, $$ and $$ 1^4 + 2^4 + 3^4 + \cdots + n^4 = \frac{n(2n+1)(n+1)(3n^2+3n-1)}{30}. $$
We will prove the result by a generating function argument.
Proof. For no obvious reason, let $$ f_n(x) := \frac{x(e^{(n+1)x} - 1)}{(e^x-1)}. $$
On the one hand, we have $$ f_n(x) = x\frac{1-(e^x)^{n+1}}{1-e^x} = x\sum_{k=0}^{n} e^{kx}, $$ and so the coefficient of $x^{r+1}$ is $\sum_{k=0}^{n} k^r/r!$ , more or less the sum we want.
On the other hand, using the definition of the Bernoulli numbers,
so the coefficient of $x^{r+1}$ is $$ \sum_{l=1}^{r+1} \frac{(n+1)^l}{l!}\frac{B_{r+1-l}}{(r+1-l)!}. $$
Combining these two results, we get
Observe that we need not use the Bernoulli numbers directly; any way we can extract the Taylor coefficients of $f_n$ will give us the same results. In practical terms, we can hand $f_n$ to a computer algebra system and it will print out the needed formula.
This proof is given as Exercise 2.23 in generatingfunctionology.
| 
