# “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?

-
Dear @Covi please have a look at the answers to this question –  kuch nahi Jun 25 '11 at 4:29
I do not agree that this is a duplicate. It asks about a particular method. –  Phira Jan 10 at 17:28

The underlying mechanism is known as the calculus of finite differences. Just like one can reconstruct a $n$th degree polynomial $f$ from $f(a),f'(a),\ldots,f^{(n)}(a)$, at any point $a$, we can also reconstruct it from $f(a),\Delta_h^1[f](a),\ldots,\Delta_h^n[f](a)$, where $$\Delta^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f(x + (n - i) h)$$ is the $n$th forward difference of $f$ at $x$ (we usually take $h=1$).

It is a common math parlor trick to ask someone to choose a low degree polynomial, ask them its values at $0,1,\ldots,\text{degree}$, and to their amazement tell them their polynomial. We only need to ask them about $\text{degree}+1$ points because we know that the the $\text{degree}+1$'th and higher forward difference of a polynomial will vanish (just like with normal derivatives).

If one suspects that a function is a polynomial, but is unsure of the degree, one can ask for more and more values, and the method of finite differences will return polynomials of higher and higher degree that will approximate the function about $a$ (just like with Taylor series).

-
Maybe it's worth noting that the formula for $\Delta^n$ comes from actually computing the $n^{\textrm{th}}$ power of the $\Delta^1$ operator. –  Joel Cohen Jun 25 '11 at 19:56

Given a sequence $a = \langle a_n \rangle_n$, define the difference sequence $\Delta a = \langle \Delta a_n \rangle$, where $\Delta a_n = a_{n+1} - a_n$. Define $\Delta^2 a = \Delta(\Delta a)$, $\Delta^3 a = \Delta(\Delta^2 a)$, and so on. Your example shows $a$, $\Delta a$, $\Delta^2 a$, $\Delta^3 a$, and $\Delta^4 a$, for instance. It's not too hard to prove that if each $a_n = p(n)$ for some a polynomial $p$ of degree $d$, then there is a polynomial $p_1$ of degree $d-1$ such that each $\Delta a_n = p_1(n)$. By induction it follows that for $k = 1,\dots,d$ there is a polynomial $p_k$ of degree $d-k$ such that each $\Delta^k a_n = p_k(n)$. In particular, $q_d$ is of degree $0$ and is therefore constant, and $\Delta^{d+1} a_n = 0$ for all $n$.

It turns out that the converse is also true: if there is a non-negative integer $d$ such that $\Delta^{d+1} a_n = 0$ for all $n$, then there is a polynomial $p$ of degree $d$ such that each $a_n = p(n)$. This is proved by actually constructing such a polynomial: it turns out that $p(n) = \sum \limits_{k=0}^d (\Delta^k a_0) {n \choose k}$ (where $\Delta^0 a = a$). This is the result that was used to get the formula for $S(n)$ in your example (except that the coefficient of ${n \choose 3}$ should be $2$). (It may not be immediately obvious that this is actually a polynomial in $n$. To see this, just note that ${n \choose k} = \frac{1}{k!} n(n-1)\dots(n-k+1)$, which is clearly a polynomial in $n$ of degree $k$.)

The proof of this result is a bit long, but it's not particularly difficult. There's a very clear treatment in Edward Scheinerman, Mathematics: A Discrete Introduction, 2nd edition, Section 22.

-

The key word here is finite differences. See Newton series.

-

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

-