
Following are excerpts from a bulletin board, called the mathboard on the algebraonline.com website.
In this thread, a student is asking why it's true that the sum of squares from 1 to n^2 is equal to n(n+1)(2n+1)/6. The first response was to show it inductively, but this left the student unsatisfied...
If I get your question, you're asking how a person would stumble over the formula in the first place; not how to prove it's correct once you know it. In answer to that question, I would like to introduce you to a general method of figuring out what polynomial fits a given series. This works if there is a polynomial that fits the series, but it doesn't require you to know the coefficients of that polynomial in advance.
First, make a table like the one below. The third column, sum of n², is the one that we're going to fit to a polynomial. The next column is the differences between successive entries of the third column. The column after that are the successive differences of the fourth column, etc. Eventually, if a polynomial fits the series, you'll get to a column of constant differences. In this case, the 3rd differences are constant, so a 3rd degree polynomial fits this series.
n  n²  sum of n²  1st diff  2nd diff  3rd diff 
0  0  0  
1  1  1  1  
2  4  5  4  3  
3  9  14  9  5  2 
4  16  30  16  7  2 
5  25  55  25  9  2 
6  36  91  36  11  2 
7  49  140  49  13  2 
8  64  204  64  15  2 
9  81  285  81  17  2 
10  100  385  100  19  2 
Divide the constant 3rd differences by 3! (3 factorial, which is 6) to get the 3rd degree coefficient for the polynomial. Now make a new table, subtracting this term (n³/3) from the series we're trying to fit, and find the differences all over again:
n  n²  (sum of n²)(n³/3)  1st diff  2nd diff  3rd diff 
0  0  0  
1  1  2/3  2/3  
2  4  2 1/3  1 2/3  1  
3  9  5  2 2/3  1  0 
4  16  8 2/3  3 2/3  1  0 
5  25  13 1/3  4 2/3  1  0 
6  36  19  5 2/3  1  0 
7  49  25 2/3  6 2/3  1  0 
8  64  33 1/3  7 2/3  1  0 
9  81  42  8 2/3  1  0 
10  100  51 2/3  9 2/3  1  0 
Now the 2nd differences are constant. Divide this number by 2! to get the 2nd degree coefficient. Then subtract this term from the series we're trying to fit, and find the differences all over again.
n  n²  (sum of n²)(n³/3+n²/2)  1st diff  2nd diff  3rd diff 
0  0  0  
1  1  1/6  1/6  
2  4  1/3  1/6  0  
3  9  1/2  1/6  0  0 
4  16  2/3  1/6  0  0 
5  25  5/6  1/6  0  0 
6  36  1  1/6  0  0 
7  49  1 1/6  1/6  0  0 
8  64  1 1/3  1/6  0  0 
9  81  1 1/2  1/6  0  0 
10  100  1 2/3  1/6  0  0 
Now the 1st differences are constant. Do the same thing to get the 1st degree coefficient, subtract it, and do the differences again:
n  n²  (sum of n²)(n³/3+n²/2+n/6)  1st diff  2nd diff  3rd diff 
0  0  0  
1  1  0  0  
2  4  0  0  0  
3  9  0  0  0  0 
4  16  0  0  0  0 
5  25  0  0  0  0 
6  36  0  0  0  0 
7  49  0  0  0  0 
8  64  0  0  0  0 
9  81  0  0  0  0 
10  100  0  0  0  0 
Now you can see that the sum of n² is equal to (n³/3+n²/2+n/6). You can factor this to get n(n+1)(2n+1)/6.
The great thing about this method is that it will help you find the sum of n³, or any higher power of n for that matter, as well as any other series that can be exactly fit by a polynomial of finite order.
Method of Successive Differences to find the coefficients of a polynomial f(k), given a few values of f(k) for successive integers, k.
Find the equation of an order n polynomial that passes through n points
Academic Decathlon State Competition Question 06  How many squares are on a checkerboard?
The webmaster and author of this Math Help site is Graeme McRae.