Last week we looked at problems about counting the squares of all sizes in a checkerboard. Some solutions required finding the sum of consecutive squares, \(1^2+2^2+3^2+\dots+n^2\), for which we used a formula whose derivation I deferred to this week. Here we’ll see a couple proofs that require knowing the formula ahead of time, and a couple derivations that discover the formula without needing to know it first.
Proof by mathematical induction
In 1997, three years after that post we started with last week, we got a question asking for more information about it, which was added to that page:
Chessboard Squares
You said the formula was n(n+1)(2n+1) ------------- 6 which works out perfectly. I have some questions though. Where is your work, how did you get that answer, how did you get divided by six, how did you get your proof? Thank you Jason
One of us (somehow, the name was lost) answered:
Hi Jason - Here are two things that might help you understand this problem. The first is a proof of why the formula works. The second is something that might help your intuitive sense of why it works. I wish I knew a nice way to explain the formula, something like "the n(n+1) comes from the triangular numbers, and then you multiply by (2n+1)/6 because...." Unfortunately I don't know how to explain the formula like that. Here's the proof, using a concept called "mathematical induction": Assume that the formula works for the first few values of n (which you can check just by plugging in numbers). We'll show that if it works for n, then it works for n+1. So if it works for n=5, it works for n=6. And if it works for n=6, it works for n=7. And so on. This will show that the formula works no matter how high we go, so it works for all values of n.
We want to prove that $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$
We showed an induction proof for this among four examples of induction in January.
The base case is easy; for \(n=1\), the sum is obviously 1, and the formula yields $$\sum_{k=1}^1 k^2 = \frac{1(1+1)(2\cdot1+1)}{6}=1$$ Then, assuming the formula works for n, we add another term and simplify with the goal of showing that $$\sum_{k=1}^{n+1} k^2 = \frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}$$
Here's how it works: if the sum of the first n squares is n(n+1)(2n+1)/6, then let's add another square. So the sum of the first n+1 squares is:
n(n+1)(2n+1) 6(n+1)^2 + n(n+1)(2n+1)
------------ + (n+1)^2 = -----------------------
6 6
(n+1)[6(n+1) + n(2n+1)]
Factor out (n+1): = -----------------------
6
(n+1)[6n + 6 + 2n^2 + n]
= ------------------------
6
(n+1)[2n^2 + 7n + 6]
= --------------------
6
(n+1)[(n+2)(2n+3)]
Factor: = ------------------
6
(n+1)(n+1 + 1)(2(n+1) + 1)
= --------------------------
6
Now notice that this is what we would get if we plugged n+1 in for n in the original formula. So the formula works for n+1, and we're done.
Mathematical induction is very powerful, but it's sometimes hard to get the hang of. If you didn't understand all of that or why it works, maybe you can get a math teacher to explain it in a different way.
If you have trouble following it, just go to the earlier post for details. Or wait a couple minutes, because we’ll see it again.
Confirmation by a limit
The other part is more intuitive: picture adding up your squares as building a pyramid out of blocks, each block 1 unit on a side. The tip of the pyramid has 1 block, the next level down has 4 blocks (a 2x2 square), the next level has 9 blocks (a 3x3 square), and so on. To find the total number of blocks, we could try to measure the volume of the pyramid, and that would give us a pretty good estimate. The taller we build our pyramid, the better this estimate will be (do you see why?). So we can use the volume of a pyramid: base*height/3. The base has area n^2, the height is n, so the volume is n^3/3.
What about our formula? As n gets bigger and bigger, n+1 starts to look a lot like n, and 2n+1 starts to look a lot like 2n. A difference of 1 in large numbers is a lot less important than a difference of 1 in small numbers. So our formula starts to look like this as n gets big:
n(n)(2n)
--------
6
And that simplifies to n^3/3.
Here is what those pyramids look like:
In fact, elsewhere we have used the sum of squares as part of a proof of the volume formula for a pyramid, reversing the thinking here. But this is not a proof, so it isn’t a circular argument.
Derivation from binomial cubed
The trouble with an inductive proof is that you have to know (or at least guess) the formula in order to prove it. Students often ask for a more natural proof that actually derives the formula, discovering it from known facts rather than pulling it out of the air. Some sort of special insight is often needed, but most of the remaining answers to such questions will at least end up with the formula rather than starting with it.
Here is a question from 1998:
Formula For the Sum Of the First N Squares
Can you show me how (1^2 + 2^2 + 3^2 + ... + N^2) becomes
(N * (N + 1) * (2N + 1)) / 6 Thanks.
Doctor Sam answered first, starting, surprisingly, with the expansion of a binomial cube:
Andres,
This is a lot easier to do with pictures, but I'll try to show you an algebra approach to this formula. It makes use of this cubing pattern:
(x + 1)^3 = x^3 + 3x^2 + 3x + 1
That is, to cube one more than a number x, first cube x, then triple x^2, then triple x, and then add these to 1. Okay?
The formula he starts with comes from the binomial theorem, but can be derived by just expanding the cube step by step:
$$(x+1)^3=(x+1)(x+1)(x+1)=(x^2+x+x+1)(x+1)=\\ (x^2+2x+1)(x+1)=x^3+x^2+2x^2+2x+x+1=\\ x^3+3x^2+3x+1$$
Now write this out for x varying from 0 through \(n+1\), and add them up:
1^3 = (0 + 1)^3 = 0^3 + 3 ( 0^2 ) + 3 (0) + 1
2^3 = (1 + 1)^3 = 1^3 + 3 ( 1^2 ) + 3 (1) + 1
3^3 = (2 + 1)^3 = 2^3 + 3 ( 2^2 ) + 3 (2) + 1
4^3 = (3 + 1)^3 = 3^3 + 3 ( 3^2 ) + 3 (3) + 1
etc.
n^3 = (n-1 + 1)^3 = (n-1)^3 + 3 (n-1)^2 + 3 (n-1) + 1
(n+1)^3 = (n + 1)^3 = n^3 + 3 n^2 + 3 n + 1
----------------------------------------------------------------------
Now add all these up in columns. The left side is the sum of the cubes from 1 to n+1:
1^3 + 2^3 + 3^3 + ... + n^3 + (n+1)^3
What? We don’t want the sum of cubes! But that will go away:
The first column on the right is also the sum of cubes but starting at 0 and ending at n: 0^3 + 1^3 + 2^3 + ... + (n-1)^3 + n^3 The next column on the right has 3 times the sum of the squares from 0^2 to n^2 The next column has 3 times the sum of the integers from 0 to n. The last column has n+1 ones. [not n ones...n+1 ones!] 1. All of the cubes cancel except for (n+1)^3 2. The sum of the squares is what we are looking for ... call this S 3. The sum of the integers 1+2+3+...+n = n(n+1)/2 4. The sum of n+1 ones is just n+1.
In symbols, when we add each column, the bottom line is $$\sum_{k=1}^{n+1}k^3 = \sum_{k=0}^{n}k^3 + 3 \sum_{k=0}^{n}k^2 + 3\sum_{k=0}^{n}k + \sum_{k=0}^{n}1$$ Subtracting the cubes that appear on both sides and using the formulas, this becomes $$(n+1)^3 = 3 \sum_{k=0}^{n}k^2 + 3\frac{n(n+1)}{2} + (n+1)$$
Now combine these:
(n+1)^3 = 3S + 3[ n(n+1)/2 ] + n + 1
Bring everything together:
n^3 + 3n^2 + 3n + 1 - 3n^2/2 - 3n/2 - n - 1 = 3S
Simplify:
n^3 + 3n^2/2 + n/2 = 3S
Multiply through by 2 to clear fractions:
2n^3 + 3n^2 + n = 6S
Factor:
n ( 2n^2 + 3n + 1) = 6S
Factor again:
n ( 2n+1) (n+1) = 6S
Rearrange and solve for S = 1^2 + 2^2 + ... + n^2:
S = n(n+1)(2n+1)/6 !
I hope that helps.
How might someone get the idea of working with the sum of cubes? One possible way will appear in a different proof involving cubes we’ll get to later.
Derivation by picture
He mentioned doing it easily with pictures. I suspect he may be thinking of this 1984 article giving a “proof without words” for the sum:
Three pyramids, each equal to the sum of squares, together form a cuboid with dimensions \(n\) by \(n+1\) by \(\frac{2n+1}{2}\), from which we get the formula.
Proof by telescoping sum
Doctor Rob joined in with an inductive proof, then offered a third approach, again a proof rather than a derivation because he starts with the formula:
Another way to see this is as follows. Let f(N) = N*(N+1)*(2N+1)/6. Then
f(N) - f(N-1) = N*(N+1)*(2N+1)/6 - (N-1)*[(N-1)+1]*[2*(N-1)+1]/6,
= N*(N+1)*(2N+1)/6 - (N-1)*N*(2*N-1)/6,
= N*[(2*N^2+3*N+1)-(2*N^2-3*N+1)]/6,
= N*(6*N)/6,
= N^2.
Now
1^2 = f(1) - f(0),
2^2 = f(2) - f(1),
3^2 = f(3) - f(2),
... ...
(N-1)^2 = f(N-1) - f(N-2),
N^2 = f(N) - f(N-1).
Add all these up, and see that on the right side, there is massive cancellation. The result is
1^2 + 2^2 + 3^2 + ... + N^2 = f(N) - f(0) = N*(N+1)*(2N+1)/6.
If this kind of cancellation occurs in a sum, it is called a "telescoping sum." This can be a very useful trick to know in some contexts.
The problem is to find the function f(N) for which f(N) - f(N-1) is a given function of N. In this case, it is given to you. In other situations, it may not be. But that's a different story!
Since the difference between successive values of the formula is a square, the value of the formula itself is a sum of squares. (This is rather similar to the Fundamental Theorem of Calculus, if you have seen that.)
It can help to write the sum this way:
1^2 = f(1) - f(0)
2^2 = f(2) - f(1)
3^2 = f(3) - f(2)
...
(N-1)^2 = f(N-1) - f(N-2)
N^2 = f(N) - f(N-1)
------- -------------------------------------------------
SUM = f(N) - f(0)
= N*(N+1)*(2N+1)/6.
Derivation by telescoping sum
Here is a question from 2001:
Sigma Notation
Trying to prove that sigma (i^2) from i = 1 to n i equal to (n(n+1)(2n+1))/6 we were told to start with (i+1)^3 - i^3... I tried expanding this but I don't understand where that comes from in relation to i^2 and how it works.
As in the derivation from the binomial cubed, with which this has a lot in common, it’s not obvious why we’d start this way, but we might as well do what we’re told, and then think about it!
I answered this time, following the hint to produce a different telescoping sum:
Hi, Steve.
Well, let's do it:
(i+1)^3 - i^3 = i^3 + 3i^2 + 3i + 1 - i^3
= 3i^2 + 3i + 1
The difference on the left makes me think of telescoping sums: if we add up
(2^3-1^3) + (3^3 - 2^3) + ... + ((n+1)^3-n^3),
the subtraction in one term cancels the addition in the previous term, making the sum
(n+1)^3 - 1^3
Again, it can help to see the telescoping sum this way:
2^3 - 1^3
3^3 - 2^3
4^3 - 3^3
...
n^3 - (n-1)^3
(n+1)^3 - n^3 ---------------------------------------------- (n+1)^3 - 1^3
Here we’re telescoping cubes rather than a known formula, but the formula we want will come out of it:
So let's sum both sides of our expansion; I'll use sigma notation, which is indeed handy here, and will assume all sums go from 1 to n to save writing:
SUM[(i+1)^3 - i^3) = SUM[3i^2 + 3i + 1]
(n+1)^3 - 1 = 3 SUM[i^2] + 3 SUM[i] + SUM[1]
As in the first derivation using cubes, the sum of cubes drops out, and we are left with sums whose formulas we know:
$$(n+1)^3-1=3\sum_{i=1}^{n}i^2+3\sum_{i=1}^{n}i+\sum_{i=1}^{n}1=3\sum_{i=1}^{n}i^2+3\frac{n(n+1)}{2}+n$$
Solving for the sum of squares, we find $$3\sum_{i=1}^{n}i^2=(n+1)^3-1-3\frac{n(n+1)}{2}-n$$ $$3 \sum_{i=1}^{n}i^2=n^3+3n^2+3n+1-1-\frac{3n^2}{2}-\frac{3n}{2}-n=n^3+\frac{3n^2}{2}+\frac{n}{2}$$ $$\sum_{i=1}^{n}i^2=\frac{2n^3+3n^2+3n-2n}{6}=\frac{n(2n^2+3n+1)}{6}=\frac{n(n+1)(2n+1)}{6}$$
After that, I gave a reference to the previous answer, and closed with this:
Every method I know of for proving this formula requires some leap of insight, whether it's just knowing the formula to begin with and proving it's right, or doing some weird thing like this with seemingly unrelated sums.
Derivation by finite differences
For a very different approach, consider this 2001 question asking about the second answer in this post:
Formula for Sum of First N squares
I found this question in your archives: Formula For the Sum Of the First N Squares http://mathforum.org/dr.math/problems/sandin2.20.98.html Can you show me how (1^2 + 2^2 + 3^2 + ... + N^2) becomes (N * (N + 1) * (2N + 1)) / 6 I was impressed by how Dr. Sam derived the formula, through the use of this cubing pattern: (x + 1)^3 = x^3 + 3x^2 + 3x + 1 However, I would like to know whether there are other methods to find the formula.
Doctor Greenie answered. First, he gave a reference to another of our answers, which I don’t have room for here:
Hi, Mark - I will show you a derivation of this formula in detail. But first, here is another page in the Dr. Math archives that presents the same problem a bit differently from either my solution or the one you read from Dr. Sam; it also references other pages where similar discussions are to be found: Sum of Consecutive Squares http://mathforum.org/dr.math/problems/robert.05.11.01.html
He then introduced the method of finite differences, which was mentioned also in the post Cutting Up a Circle II: Using n Points. This can be used whenever you suspect a formula might be a polynomial.
There is a general method by which you can derive the formula for the sum of the k-th powers of the first n positive integers. This is the method of finite differences. In fact, this method can be used to find the formula that generates any given sequence of numbers, as long as that formula is a polynomial function.
Practicing the method
Before applying it to our problem, he demonstrates it more generally:
Let me first demonstrate the method by starting with an arbitrary polynomial function, finding the sequence of values generated by that function, and then simulating the case where I am given that sequence of values and have to determine the polynomial function that generated it.
I will choose (arbitrarily) the polynomial function
n^2 - 3n + 4
For n = 1, 2, 3, 4, 5, ..., the sequence of values generated by this function is 2, 2, 4, 8, 14, ....
Here, we are using a known formula to generate a sequence, and will show that we can get back to this correct formula.
Now suppose I am given the sequence
2, 2, 4, 8, 14, ...
and I want to find the polynomial function that generates the sequence. (Clearly, my answer should be the polynomial I started with: n^2-3n+4.)
I use the numbers in the given sequence and the method of finite differences to determine the polynomial function.
I start the method of finite differences by writing down the sequence of numbers I am given, leaving some space between them....
2 2 4 8 14
Then, underneath this row of numbers, I write the differences between the successive terms; this is my row of "first differences" for the sequence:
2 2 4 8 14
0 2 4 6
These "first differences" are not all the same, so I next make another row consisting of the differences between the successive first differences (this is called the row of "second differences"):
2 2 4 8 14
0 2 4 6
2 2 2
In this row, all of the numbers are the same.
In general, we might need to continue the process in order to get a row of constant differences.
According to the method of finite differences, if the row of n-th differences is constant, then the generating function is a polynomial of degree n. So, with the numbers in this row of second differences being all the same, we know that the generating function is a polynomial of degree 2.
So our generating function is of the form
f(n) = an^2 + bn + c (1)
We need to determine the values of a, b, and c. (In this case, of course, since we started with the known function, we know what the answer should be: a=1, b=-3, c=4.)
There are a couple different ways to proceed from here, but the most common is to solve a system of \(n+1\) (in this case, 3) equations, one per unknown coefficient:
With the first 5 terms of the sequence being given as 2, 2, 4, 8, and 14, we know
f(1) = 2
f(2) = 2
f(3) = 4
f(4) = 8
f(5) = 14
But we also know from (1) that
f(1) = a + b + c = 2
f(2) = 4a + 2b + c = 2
f(3) = 9a + 3b + c = 4
f(4) = 16a + 4b + c = 8
f(5) = 25a + 5b + c = 14
We have 5 equations relating the values of a, b, and c; we can use any 3 of these equations to find the values of a, b, and c. To keep the arithmetic as simple as possible, we choose the first three of them, since the coefficients in the last two are larger...
a + b + c = 2
4a + 2b + c = 2
9a + 3b + c = 4
Eliminating the variable "c" between the first and second of these equations, and again between the second and third...
3a + b = 0
5a + b = 2
And eliminating the variable "b" between these two equations...
2a = 2
So we know
a = 1
Once we have one coefficient, we work backward, picking up each coefficient we had eliminated:
Then
3a + b = 0
3(1) + b = 0
3 + b = 0
b = -3
And finally
a + b + c = 2
1 - 3 + c = 2
c = 4
We have determined that a=1, b=-3, and c=4, so our polynomial function, which generates the given sequence, is (as we knew before we started, in this case)
f(n) = an^2 + bn + c
f(n) = n^2 - 3n + 4
So we found the correct formula. Can we do it for the sum of squares?
Deriving our formula
So much for our example to demonstrate the process. Now for finding the formula for the sum
1^2 + 2^2 + 3^2 + 4^2 + 5^2 + ...
For n=1, the sum is 1^2 = 1
For n=2, the sum is 1^2+2^2 = 1+4 = 5
For n=3, the sum is 1^2+2^2+3^2 = 1+4+9 = 14
For n=4, the sum is 1^2+2^2+3^2+4^2 = 1+4+9+16 = 30
For n=5, the sum is 1^2+2^2+3^2+4^2+5^2 = 1+4+9+16+25 = 55
For n=6, the sum is 1^2+2^2+3^2+4^2+5^2+6^2 = 1+4+9+16+25+36 = 91
So the sequence we are working with is
1, 5, 14, 30, 55, 91, ...
Let's try our method of finite differences on this sequence....
1 5 14 30 55 91
4 9 16 25 36
5 7 9 11
2 2 2
This time, we found the third row to be constant. There are ways to convince yourself that it will remain constant forever, but we’ll just trust that it is.
The third row of differences is a constant, so the function we are looking for is a polynomial of degree 3:
f(n) = an^3 + bn^2 + cn + d
And we know (using the first four terms of the sequence) that
f(1) = a + b + c + d = 1
f(2) = 8a + 4b + 2c + d = 5
f(3) = 27a + 9b + 3c + d = 14
f(4) = 64a + 16b + 4c + d = 30
We also know f(5)=55 and f(6)=91; however, we only need four equations to solve for the four unknowns a, b, c, and d.
As in our earlier example, we successively eliminate variables from this set of equations:
a + b + c + d = 1
8a + 4b + 2c + d = 5
27a + 9b + 3c + d = 14
64a + 16b + 4c + d = 30
7a + 3b + c = 4
19a + 5b + c = 9
37a + 7b + c = 16
12a + 2b = 5
18a + 2b = 7
6a = 2
Then we solve this equation for a and then substitute back in successive earlier equations to find the values of the other unknowns:
a = 1/3
12a + 2b = 5
12(1/3) + 2b = 5
4 + 2b = 5
2b = 1
b = 1/2
7a + 3b + c = 4
7(1/3) + 3(1/2) + c = 4
c = 4 - 7/3 - 3/2
c = 1/6
a + b + c + d = 1
1/3 + 1/2 + 1/6 + d = 1
d = 0
So we have a=1/3, b=1/2, c=1/6, and d=0; so our polynomial function is
f(n) = (1/3)n^3 + (1/2)n^2 + (1/6)n
2n^3 + 3n^2 + n
f(n) = -----------------
6
n*(2n^2 + 3n + 1)
f(n) = -------------------
6
n*(2n + 1)*(n+1)
f(n) = -------------------
6
That, of course, is the same formula we have either derived or proved several times already.
Hi there,
In your derivation using telescoping sum, I would like to point out that you have made the mistake of summing from 0 to n when it should in fact be from 1 to n. You have gotten the right answer as a result of the second last line of that subsection, in which you have removed a -1.
If there is a problem with this new solution please let me know 🙂
Thanks for reading carefully! I’ve corrected it now.