"Counting Tricks": using combination to derive a general formula for $1^2 + 2^2 + \cdots + n^2$ I was reading an online article which confused me with the following. To find out $S(n)$, where $S(n) = 1^2 + 2^2 + \cdots + n^2$, one can first write out the first few terms:  

0 1 5 14 30 55 91 140 204 285  

Then, get the differences between adjacent terms until they're all zeroes:  

0 1 5 14 30 55 91 140 204 285
  1 4 9 16 25 36 49 64 81
  3 5 7 9 11 13 15 17
  2 2 2 2 2 2 2
  all zeroes this row

Then it says that therefore we can use the following method to achieve $S(n)$:
$S(n) = 0 {n\choose 0} + 1 {n\choose 1} + 3 {n\choose 2} + 2 {n\choose 3}$.
I don't understand the underlying mechanism. Someone cares to explain?

On a desert island, for a low level student, we search for a pattern finding n, sq, sum and factors of sum. Do this up to n = 20. e.g
n=1; sq=1; sum=1
n=5; sq=25; sum=55=5x11
n=6; sq=36; sum=91=7x13
n=8; sq=64; sum=204=2x2x3x17
n=12 sq=144; sum=650=2x5x5x13
n=15 sq=225;sum=1240=2x2x2x5x31
n=17;sq=289;sum=1785=3x5x7x17 etc
Perhaps the formula is a product. When n is prime it always appears in the formula.
Similarly n=5 has factor 11. n=15 has factor 31. So 2n+1 is a factor.
Similarly n+1.
Now nx(n+1)x(2n+1) is six times too large.
So, formula is n(n+1)(2n+1)/6
