Seeking non-inductive, combinatorial proof of the identity $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

Question

How do you prove

$$1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}$$

without induction?

I'm looking for a combinatorial proof of this.

Answer 1

Here is a combinatorial proof:

You want to count the ordered triples $(a,b,c)$ with $a,b,c\in\{1,2,3\dots n\}$ with $a\geq b,c$

There are three types:

when all three numbers are different, there are clearly $2\times \binom{n}{3}$ of these (because there are two ways to arrange three distinct numbers).

When exactly two numbers are equal there are $3\times\binom{n}{2}$.(we know $a$ must be the big one, and there are $3$ options for $b,c$)

When all are equal there are $n$.

Adding all up we get $2\binom{n}{3}+3\binom{n}{2}+n= \frac{n(n + 1)(2n + 1)}{6}$

---

This can be nicely generalized to higher exponents with stirling coefficients, we get $\sum\limits_{i=1}^n i^k=\sum_{j=1}^{k}\limits{ k \brace j}\binom{n}{j}(j-1)!$

Answer 2

We can count the sum $$2^2 + 4^2 + \dots + (2n)^2 = {2n + 2 \choose 3}$$ as follows:

Choose three numbers from $\{1, 2, \dots, 2n+2\}$. If the largest number chosen is odd, notate it $2m+1$ - the other two smaller numbers can be chosen in ${2m \choose 2}$ ways. If the largest number chosen is $2m+2$, the other two numbers can be chosen in ${2m+1 \choose 2}$ ways. From the identity

$${2m \choose 2} + {2m+1 \choose 2} = (2m)^2$$

and summing this for $m = 0, 1, 2, \dots, n$, the even result follows and the general result follows from dividing by two.