Sum of Sequence of Binomial Coefficients by Sum of Powers of Integers

Theorem

Let $n, k \in \Z_{\ge 0}$ be positive integers.

Let $S_k = \ds \sum_{i \mathop = 1}^n i^k$.

Then:

$\ds \sum_{i \mathop = 1}^k \binom {k + 1} i S_i = \paren {n + 1}^{k + 1} - \paren {n + 1}$

Then:

$\ds \paren {N + 1}^{k + 1} - N^{k + 1}$

$=$

$\ds \sum_{i \mathop = 0}^{k + 1} \binom {k + 1} i N^i - N^{k + 1}$

$\ds $

$=$

$\ds \binom {k + 1} 0 + \sum_{i \mathop = 1}^k \binom {k + 1} i N^i + \binom {k + 1} {k + 1} N^{k + 1} - N^{k + 1}$

$\ds $

$=$

$\ds 1 + \sum_{i \mathop = 1}^k \binom {k + 1} i N^i$

Summing from $N = 1$ to $N = n$, we have on the left hand side:

$\ds \sum_{N \mathop = 1}^n \paren {\paren {N + 1}^{k + 1} - N^{k + 1} }$

$=$

$\ds \paren {n + 1}^{k + 1} - 1^{k + 1}$

$\ds $

$=$

$\ds \paren {n + 1}^{k + 1} - 1$

So, we have:

$\ds \paren {n + 1}^{k + 1} - 1$

$=$

$\ds \sum_{N \mathop = 1}^n \paren {1 + \sum_{i \mathop = 1}^k \binom {k + 1} i N^i}$

$\ds $

$=$

$\ds \sum_{N \mathop = 1}^n 1 + \sum_{i \mathop = 1}^k \binom {k + 1} i \sum_{N \mathop = 1}^n N^i$

$\ds $

$=$

$\ds n + \sum_{i \mathop = 1}^k \binom {k + 1} i S_i$

giving:

$\ds \sum_{i \mathop = 1}^k \binom {k + 1} i S_i = \paren {n + 1}^{k + 1} - \paren {n + 1}$

$\blacksquare$