"Counting Tricks": using combination to derive a general formula for $1^2 + 2^2 + \cdots + n^2$

Solution 1:

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).

Solution 2:

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.