13.2: Sums of Powers
- Page ID
- 48387
In Chapter 5, we verified the formula (13.1), but the source of this formula is still a mystery. Sure, we can prove that it’s true by using well ordering or induction, but where did the expression on the right come from in the first place? Even more inexplicable is the closed form expression for the sum of consecutive squares:
\[\label{13.2.1} \sum_{i=1}^{n} i^2 = \dfrac{(2n+1)(n+1)n}{6}.\]
It turns out that there is a way to derive these expressions, but before we explain it, we thought it would be fun—OK, our definition of “fun” may be different than yours—to show you how Gauss is supposed to have proved equation 13.1 when he was a young boy
Gauss’s idea is related to the perturbation method we used in Section 13.1.2. Let
\[\nonumber S = \sum_{i=1}^{n}i.\]
Then we can write the sum in two orders:
\[\nonumber S = 1 + 2 + ... + (n-1) + n,\]
\[\nonumber S = n + (n-1) + ... + 2 + 1.\]
Adding these two equations gives
\[\begin{aligned} 2S &= (n+1) + (n+1) + \cdots + (n+1) + (n+1) \\ &= n(n+1). \end{aligned}\]
Hence,
\[\nonumber S = \dfrac{n(n+1)}{2}.\]
Not bad for a young child—Gauss showed some potential....
Unfortunately, the same trick does not work for summing consecutive squares. However, we can observe that the result might be a third-degree polynomial in \(n\), since the sum contains \(n\) terms that average out to a value that grows quadratically in \(n\). So we might guess that
\[\nonumber \sum_{i=1}^{n} i^2 = an^3 + bn^2 + cn + d.\]
If our guess is correct, then we can determine the parameters \(a, b, c,\) and \(d\) by plugging in a few values for \(n\). Each such value gives a linear equation in \(a, b, c,\) and \(d\). If we plug in enough values, we may get a linear system with a unique solution. Applying this method to our example gives:
\[\begin{aligned} n &= 0 \text{ implies } 0 = d \\ n &= 1 \text{ implies } 1 = a + b + c + d \\ n &= 2 \text{ implies } 5 = 8a + 4b + 2c + d \\ n &= 3 \text{ implies } 14 = 27a + 9b + 3c + d. \end{aligned}\]
Solving this system gives the solution \(a = 1/3, b = 1/2, c = 1/6, d = 0\). Therefore, if our initial guess at the form of the solution was correct, then the summation is equal to \(n^3/3 + n^2/2 + n/6\), which matches equation \(\ref{13.2.1}\).
The point is that if the desired formula turns out to be a polynomial, then once you get an estimate of the degree of the polynomial, all the coefficients of the polynomial can be found automatically.
Be careful! This method lets you discover formulas, but it doesn’t guarantee they are right! After obtaining a formula by this method, it’s important to go back and prove it by induction or some other method. If the initial guess at the solution was not of the right form, then the resulting formula will be completely wrong! A later chapter will describe a method based on generating functions that does not require any guessing at all.