# 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}$

## Proof

Let $N$ be a positive integer.

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}$ Binomial Theorem: Integral Index $\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$ Definition of Binomial Coefficient

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}$ Telescoping Series: Example 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$