Seeking non-inductive, combinatorial proof of the identity $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ 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. 
 A: 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.
A: 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)!$
