Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially

For the first one, $\displaystyle \sum_{k=1}^{n} k^2$, you can probably try this way. $$k^2 = \binom{k}{1} + 2 \binom{k}{2}$$ This can be proved using combinatorial argument by looking at drawing $2$ balls from $k$ balls with replacement.

The total number of ways to do this is $k^2$.

The other way to count it is as follows. There are two possible options either you draw the same ball on both trials or you draw different balls on both trials. The number of ways for the first option is $\binom{k}{1}$ and the number of ways for the second option is $\binom{k}{2} \times \left( 2! \right)$

Hence, we have that $$k^2 = \binom{k}{1} + 2 \binom{k}{2}$$ $$\displaystyle\sum_{k=1}^{n} k^2 = \sum_{k=1}^{n} \binom{k}{1} + 2 \sum_{k=1}^{n} \binom{k}{2} $$

The standard combinatorial arguments for $\displaystyle\sum_{k=1}^{n} \binom{k}{1}$ and $\displaystyle\sum_{k=1}^{n} \binom{k}{2}$ gives us $\displaystyle \binom{n+1}{2}$ and $\displaystyle \binom{n+1}{3}$ respectively.

Hence, $$ \sum_{k=1}^{n} k^2 = \binom{n+1}{2} + 2 \binom{n+1}{3}$$

For the second case, it is much easier than the first case and in fact this suggests another method for the first case.

$k(k+1)$ is the total number of ways of drawing 2 balls from $k+1$ balls without replacement where the order is important. This is same as $\binom{k+1}{2} \times \left(2! \right)$

Hence, $$\sum_{k=1}^{n} k(k+1) = 2 \sum_{k=1}^{n} \binom{k+1}{2} = 2 \times \binom{n+2}{3}$$

This suggests a method for the previous problem since $k^2 = \binom{k+1}{2} \times \left(2! \right) - \binom{k}{1}$

(It is easy to give a combinatorial argument for this by looking at drawing two balls from $k+1$ balls without replacement but hide one of the balls during the first draw and add the ball during the second draw)

and hence $$\sum_{k=1}^{n} k^2 = 2 \times \binom{n+2}{3} - \binom{n+1}{2} $$

For $$\sum_{k=1}^n (k+1)(k),$$ let me tell a story.

There are $n+2$ chairs in a row, and three people, Lefty, Alice, and Bob.

They want to sit down. Lefty does not like to have anyone to his left. In how many ways can they sit?

Lefty could be in the third seat from the right, leaving $2$ choices for Alice and then $1$ for Bob. Or else Lefty could be in the fourth seat from the right, leaving $3$ choices for Alice and then $2$ for Bob. And so on. Finally Lefty could be in the leftmost seat, giving Alice $n+1$ choices and Bob $n$. So the total number of seating arrangements is our sum.

Or else choose $3$ seats from $n+2$, reserve the leftmost for Lefty. For each choice of $3$ seats there are then $2$ places for Alice to sit, for a total of $$2\binom{n+2}{3}.$$

We show bijectively that

$$2^2+4^2+6^2+\cdots +(2n)^2=\binom{2n+2}{3}.$$

That does not quite give a purely combinatorial expression for $1^2+2^2+ \cdots +n^2$, since we still need to divide by $4$, which is "algebra." But the sin of multiplying or dividing by a constant seems to be a small one in this game. And the result is interesting.

Imagine choosing $3$ numbers from the numbers $1, 2, \dots, 2n+2$. This can be done in $\binom{2n+2}{3}$ ways.
We will show that the number of choices is also $$2^2+4^2+6^2+\cdots +(2n)^2.$$

Maybe the largest number chosen is $2k+1$ or $2k+2$. If it is $2k+1$, the other two can be chosen in $\binom{2k}{2}$ ways, and if it is $2k+2$, then the other two can be chosen in $\binom{2k+1}{2}$ ways. Using "algebra", we find that

$$\binom{2k}{2}+\binom{2k+1}{2}= (2k)^2.$$

Take $k=1, 2, 3, \dots, n$. We conclude that the number of ways of choosing $3$ numbers from $1, 2, \dots, 2n+2$ is

$$2^2+4^2+6^2+\cdots +(2n)^2.$$

Since the number of choices is clearly $\binom{2n+1}{3}$, this almost completes the argument. (In a note at the end of this post, we deal with the minor task of eliminating the use of algebra.)

Comment: If we allow division by $4$, we can conclude that $$1^2+2^2+\cdots +n^2=\frac{1}{4}\binom{2n+2}{3}.$$

I used to think that in the usual expression $\frac{(n)(n+1)(2n+1)}{6}$ for the sum of the first $n$ squares, the $2n+1$ somehow is the weird term, it does not fit in. But it does! Actually, it is $n$ and $n+1$ that are strange. We can think of $(n)(n+1)(2n+1)$ as ``really'' being $(1/4)[(2n)(2n+1)(2n+2)]$.

Cleaning up: There is a standard way to avoid the ``calculation'' $$\binom{2k}{2}+\binom{2k+1}{2}= (2k)^2.$$

For completeness we show bijectively that for any $m$, in particular $m=2k$, we have
$$\binom{m}{2} +\binom{m+1}{2}=m^2.$$

For let $M$ be the collection $\left\{1,2,3,\dots,m\right\}$. Then the number of ordered pairs $(a,b)$ with $a$ and $b$ in $M$ is $m^2$. These ordered pairs are of two types: (i) the ones with $a<b$ and (ii) the ones with $a \ge b$. The number of ordered pairs $(a,b)$ with $a<b$ is just $\binom{m}{2}$. The ordered pairs $(a,b)$ with $a \ge b$ are in a natural bijection with the ordered pairs $(b,a+1)$ with $b<a+1$, and there are $\binom{m+1}{2}$ of these.