Proof that $\sum_{i=0}^n i^k = \sum_{i=0}^n (n-i)((i+1)^k-i^k)$

Question

This is something I stumbled upon a few years back, and has a geometrically intuitive explanation, as well as being useful in summing powers of integers. However, with some occasional attempts at an inductive proof, nothing's quite worked. This came from looking at the staircase pattern the sum of powers makes visually. For example, when $k = 2$, $\sum_{i=0}^n i^2$ directly sums the square layers making up a quarter pyramid, while $\sum_{i=0}^n (n-i)((i+1)^2-i^2) = \sum_{i=0}^n (n-i)(2i-1)$ breaks up each layer into nested pairs of edges, with $2i+1$ being the volume of the edges, and $n-i$ being the number of edges of that size. You can use this to calculate, for example, $\sum_{i=0}^n i^2 = \sum_{i=0}^n (n-i)(2i+1) = (2n-1)\sum_{i=0}^n i - 2\sum_{i=0}^n i^2 + n\sum_{i=0}^n 1$, which then rearranges to the well-known $\sum_{i=0}^n i^2 = \frac{(2n+1)n(n+1)}{6}$, substituting $\sum_{i=0}^n 1 = n+1$ and $\sum_{i=0}^n i = \frac{n(n+1)}{2}$. Can anyone see a way to prove the formula, or know how to, as I'd be rather surprised if this was a brand-new result, given how visually straight forward it is?

Answer 1

Proof by induction on $n$. The base case is obviously trivial. Now, let us assume $\sum_{i=0}^n i^k = \sum_{i=0}^n (n-i)((i+1)^k - i^k)$ holds for every $n, k \in \mathbb{N}$. Therefore, \begin{align} \sum_{i=0}^{n+1} i^k &= \sum_{i=0}^n i^k + (n+1)^k \\ &= \sum_{i=0}^n (n-i)((i+1)^k - i^k) + (n+1)^k \end{align} by the induction hypothesis. From $$ \sum_{i=0}^{n} ((i+1)^k - i^k) = \sum_{i=1}^{n+1} i^k - \sum_{i=0}^{n} i^k = (n+1)^k $$ it follows that \begin{align} \sum_{i=0}^n (n-i)((i+1)^k - i^k) + (n+1)^k &= \sum_{i=0}^n (n-i)((i+1)^k - i^k) + \sum_{i=0}^{n} ((i+1)^k - i^k) \\ &= \sum_{i=0}^n (n-i + 1)((i+1)^k - i^k) \\ &= \sum_{i=0}^{n+1} ((n+1)-i)((i+1)^k - i^k). \end{align} This finishes the proof.

Answer 2

More generally, it's true that $\sum_{i=0}^n f(i) = \sum_{i=0}^n (n-i)\bigl(f(i+1)-f(i)\bigr)$ for any function $f$ with $f(0)=0$. This is just a summation by parts formula: \begin{align*} \sum_{i=0}^n (n-i)\bigl(f(i+1)-f(i)\bigr) &= \sum_{i=0}^n (n-i)f(i+1) - \sum_{i=0}^n (n-i)f(i) \\ &= \sum_{i=1}^{n+1} (n-(i-1))f(i) - \sum_{i=0}^n (n-i)f(i) \\ &= (n-((n+1)-1)f(n+1) \\ &\qquad{}+ \sum_{i=1}^n \bigl( (n-(i-1)) - (n-i) \bigr) f(i) - (n-0)f(0) \\ &= 0f(n+1) + \sum_{i=1}^n f(i) - nf(0) = \sum_{i=1}^n f(i). \end{align*}