$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$
For the first one, I was able to express $k^2$ in terms of the binomial coefficients by considering a set $X$ of cardinality $2k$ and partitioning it into two subsets $A$ and $B$, each with cardinality $k$. Then, the number of ways of choosing 2-element subsets of $X$ is $$\binom{2k}{2} = 2\binom{k}{2}+k^2$$ So sum $$\sum_{k=1}^n k^2 =\sum_{k=1}^n \binom{2k}{2} -2\sum_{k=2}^n \binom{k}{2} $$ $$ \qquad\qquad = \color{red}{\sum_{k=1}^n \binom{2k}{2}} – 2 \binom{n+1}{3} $$ I am stuck at this point to evaluate the first of the sums. How to evaluate it?
I need to find a similar expression for $k(k+1)$ for the second sum highlighted above. I have been unsuccessful this far. (If the previous problem is done then so is this, but it would be nice to know if there are better approaches or identities that can be used.)
Update: I got the second one. Consider $$\displaystyle \binom{n+1}{r+1} = \binom{n}{r}+\binom{n-1}{r}+\cdots + \binom{r}{r}$$ Can be shown using recursive definition. Now multiply by $r!$ and set $r=2$
Best Answer
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} $$