Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially 
$$\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$

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.  
