Prove that $\sum^n_{k=1} k^2 = \binom{n+1}{2} + 2\binom{n+1}{3}$ for $n\geq 2$ Prove, for all $n\geq 2$ that 
$$\sum^n_{k=1} k^2 = \binom{n+1}{2} + 2\binom{n+1}{3}$$
Let us prove the inductive base for $n = 2$
$$\rm{LHS} = 1^2  + 2^2= 1 + 4 = 5$$
$$\rm{RHS} = \binom{3}{2} + 2\binom{3}{3} = 3 + 2\cdot 1 = 5$$
$$\rm{LHS} = \rm{RHS}$$
as desired.
Now, assume for some $k$, 
$$1^2 + 2^2 + \dots + k^2 = \binom{k+1}{2} + 2\binom{k+1}{3}$$
To prove the inductive step, it is sufficient to prove that, 
$$\binom{k+2}{2} + 2\binom{k+2}{3} - \binom{k+1}{2} - 2\binom{k+1}{3} = (k+1)^2$$
The LHS can be simplified as:
$$\frac{(k+2)!}{2!k!} + 2\left[\frac{(k+2)!}{3!(k-1)!}\right] - \frac{(k+1)!}{2!(k-1)!} - 2\left[\frac{(k+1)!}{3!(k-2)!}\right]$$
$$=\frac{3(k+2)! + 2k(k+2)! -3k(k-1)! - 2k(k-1)(k+1)!}{6k!}$$
$$=\frac{(k+1)!(3k + 6 - 2k^2 - 2k) + (k-1)!(2k^3 + 2k^2 - 3k)}{6k!}$$
$$=\frac{(k+1)!(-2k^2+k+6) + k!(2k^2+2k - 3)}{6k!}$$
$$=\frac{(k+1)(-2k^2 + k + 6) + 2k^2 +2k - 3}{6}$$
$$=\frac{-2k^3 + k^2 + 9k + 3}{6}$$
I'm pretty sure I'm making a mistake somewhere, but I can't figure it out. If someone could complete this inductive proof for me, I will be grateful.
Also, I don't feel satisfied with this ugly proof. Please add a combinatorial proof for this in your answer if possible. 
 A: If you want a short proof, there are few shorter than using difference calculus:
$$\sum_{k=1}^nk^2=\sum_1^{n+1}(k^{\underline{2}}+k^{\underline 1})\delta k=\frac{1}{3}k^{\underline{3}}+\frac{1}{2}k^{\underline{2}}\big|_1^{n+1}=\left(\frac{1}{3}(n+1)^{\underline{3}}+\frac{1}{2}(n+1)^{\underline{2}}\right)-(0+0)={n+1\choose 3}+{n+1\choose 2}$$
For an introduction, see the excellent book Concrete Mathematics.
However, if your homework is to prove this by induction, then you should proceed as you have laid out, which is a good approach.
A: There is a typo in one of your steps, it should be as follows  (look at the red ${\color{red} + }$) :
$$\frac{3(k+2)! + 2k(k+2)! -3k(k{\color{red}+}1)! - 2k(k-1)(k+1)!}{6k!} \,\,(*)$$
And then, I do not see how you got from there to
$$\frac{(k+1)!(3k + 6 - 2k^2 - 2k) + (k-1)!(2k^3 + 2k^2 - 3k)}{6k!}$$
which in fact is not equal to the first expression above. 
I would recommend you try taking out the factor $(k+1)!$ in the former expression $(*)$ above.
Another proof
Now I am going to present a more combinatorial proof (not strictly combinatorial though) :
Observation 1: We have $$ k^2 = \binom{k}{2} + \binom{k+1}{2} $$
Observation 2:  To compute $ S_n = \sum_{k=0}^n k^2 = \sum_{k=0}^n\left\{\binom{k}{2} + \binom{k+1}{2} \right\} $ it is enough to compute the sum  $A_n = \sum_{k=0}^n \binom{k}{2}$, because we then have $S_n = A_n  + A_{n+1}$.
Observation 3: We have $ A_n = \binom{n+1}{3} $. Here comes the combinatorial part:
Note that $A_n$ is actually the number of unordered "trios" you can make out of $\{1,\ldots,n+1\}$. Indeed, $\binom{n}{2}$ is the number of trios of the form $\{i,j,n+1\}$ with $1\leq i<j\leq n$, then $\binom{n-1}{2}$ is the number of trios of the form $\{i,j,n\}$ with $1\leq i < j \leq n-1$ and so on. That is, $k$ corresponds to the choice of the maximum element in the unordered trio. Since there are $\binom{n+1}{3}$ unordered trios, we get 
$$ A_n = \binom{n+1}{3} $$
Conclusion: We have $$ S_n =  \binom{n+1}{3} + \binom{n+2}{3}$$ but remember that  $\binom{n+2}{3} = \binom{n+1}{3} + \binom{n+1}{2}$ (this has a well-known combinatorial intepretation), and so
$$ S_n =  \binom{n+1}{2} + 2\binom{n+1}{3}$$
as desired. $\square$
Remark By the same argument above, we actually prove that $$\sum_{k=0}^n \binom{k}{r} = \binom{n+1}{r+1}$$
A: Perhaps this Wikipedia link might prove itself useful. The sums are computed through telescoping, each relying  on the result of the previous one, which, in this case, is $\sum_1^n k=\frac{n(n+1)}2$, for instance like this.
