Finding Sums of Powers

The formulas for the sums of powers shown below can all be proven in a straight-forward way with induction -- but each of these proofs requires that one knows what the formula should be ahead of time.

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}, \quad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}, \quad \sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4}, \ldots$$

How then, might one come up with the formulas in the first place?

The following shows an incredibly clever trick for deducing the formula for $\sum_{i=1}^{n} i^k$ by using all of the related formulas for lesser powers.

Let us demonstrate the technique through an example...

Suppose we wish to find the formula for $\sum_{i=1}^{n} i^3$, assuming that we know the following formulas already $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad \textrm{ and } \quad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ We start by considering the following identity

$$\left[ \sum_{i=1}^{n} i^4 \right] + (n+1)^4 = \sum_{i=0}^{n} (i+1)^4$$

Notice, the expression on the right side can be expanded

$$\begin{array}{rcl} \sum_{i=0}^{n} (i+1)^4 &=& \sum_{i=0}^{n} (i^4 + 4i^3 + 6i^2 + 4i + 1)\\\\ &=& \left[ \sum_{i=0}^{n} i^4 \right] + 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \sum_{i=0}^{n} i^2 \right] + 4 \left[ \sum_{i=0}^{n} i \right] + \left[ \sum_{i=0}^{n} 1 \right]\\\\ \end{array}$$ So, $$\left[ \sum_{i=1}^{n} i^4 \right] + (n+1)^4 = \left[ \sum_{i=0}^{n} i^4 \right] + 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \sum_{i=0}^{n} i^2 \right] + 4 \left[ \sum_{i=0}^{n} i \right] + \left[ \sum_{i=0}^{n} 1 \right]$$ Canceling the sums of the fourth powers on both sides, we arrive at $$(n+1)^4 = 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \sum_{i=0}^{n} i^2 \right] + 4 \left[ \sum_{i=0}^{n} i \right] + \left[ \sum_{i=0}^{n} 1 \right]$$ Substituting the formulas for the sums associated with the lesser powers lets us solve for the remaining sum: $$\begin{array}{rcl} (n+1)^4 &=& 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \frac{n(n+1)(2n+1)}{6} \right] + 4 \left[ \frac{n(n+1)}{2} \right] + (n+1)\\\\ (n+1)^4 &=& 4 \left[ \sum_{i=0}^{n} i^3 \right] + n(n+1)(2n+1) + 2n(n+1) + (n+1)\\\\ \end{array}$$ Isolating the summation on the left side, we have $$\begin{array}{rcl} \sum_{i=0}^{n} i^3 &=& \frac{(n+1)^4 - n(n+1)(2n+1) - 2n(n+1) - (n+1)}{4}\\\\ &=& \frac{(n+1)[(n+1)^3 - n(2n+1) - 2n]}{4}\\\\ &=& \frac{(n+1)(n^3 + 3n^2 + 3n + 1 - 2n^2 - n - 2n - 1)}{4}\\\\ &=& \frac{(n+1)(n^3 + n^2)}{4}\\\\ &=& \frac{n^2(n+1)^2}{4} \end{array}$$ This yields the formula we sought to acquire: $$\sum_{i=0}^{n} i^3 = \frac{n^2(n+1)^2}{4}$$ Isn't that just a delightfully beautiful trick! Note, we can then just as easily find a formula for $\sum_{i=1}^{n} i^4$ by starting over with the following identity: $$\left[ \sum_{i=1}^{n} i^5 \right] + (n+1)^5 = \sum_{i=0}^{n} (i+1)^5$$