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.

The story of André can be continued: Bob was unhappy that he always had the least chairs to choose from. So Alice and Bob decided to choose their chair at the same time. If both choose the same chair they shared the chair. So if Lefty chose the second seat from right Alice and Bob had to select the first seat. Lefty could select the third seat leaving $2$ possibilities to Alice and $2$ possibilities to Bob. Lefty could select the leftmost chair (chair with number $n+1$) giving them both $n$ possibilities to choose. So the total number of arrangements was now $$\sum_{k=1}^n k^2$$ Again we can calculate the possibilities in another way: Select 3 chairs from $n+1$ chairs, the leftmost is for Lefty the remaining two can be assigned to Alice and Bob. This is the case when Alice and Bob choose different seats and the number is $$2\binom{n+1}{3}$$ When we select only 2 from the $n+1$ chairs, the leftmost is for Lefty and the second must be shared by Alice and Bob. This gives $$\binom{n+1}{2}$$ possibilities. The number of all possible selections is the sum of both numbers that is $$2\binom{n+1}{3}+\binom{n+1}{2} = n(n+1)(2n+1)/6$$

Concerning the first, there is also the elegant formula (that I found thanks to OEIS) $$ \sum\limits_{k = 1}^n {k^2 } = {n+2 \choose 3} + {n+1 \choose 3}. $$ For a proof, first note that it holds for $n=1,2$. Now, denote the expression on the right-hand side by $a_n$. Then, $$ a_n - a_{n-1} = {n+2 \choose 3} - {n \choose 3} = \frac{{n(n + 1)(n + 2)}}{6} - \frac{{n(n - 1)(n - 2)}}{6} = \frac{{n(6n)}}{6} = n^2 . $$ Thus we are done, since also $$ \sum\limits_{k = 1}^n {k^2 } - \sum\limits_{k = 1}^{n - 1} {k^2 } = n^2 . $$