Prove $\binom{n+2}{k+2} = \binom{n}{k+2} + 2\binom{n}{k+1} + \binom{n}{k}$ I have to prove the following statement 
$$\binom{n+2}{k+2} = \binom{n}{k+2} + 2\binom{n}{k+1} + \binom{n}{k}$$
I know, I have to use the following fact 
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$
but I can't seem to figure out how. Some hints would be appreciated
Thanks
 A: I kept in mind the recursive characteristics of the Pascal triangle to do this one, together with the relation you had to consider:
$$\binom{n+2}{k+2} = {\color{red}{\binom{n+1}{k+2}}} + {\color{blue}{\binom{n+1}{k+1}}} \\
= {\color{red}{\binom{n}{k+2} + \binom{n}{k+1}}}  + {\color{blue}{\binom{n}{k+1} + \binom{n}{k}}}\\
={\color{red}{\binom{n}{k+2}}} + {\color{purple}{2\binom{n}{k+1}}} + {\color{blue}{\binom{n}{k}}}$$
(The one in the middle is purple because red plus blue equals purple)
A: Note that you don't have to use that formula.
Consider a set of $n+2$ elements, where $a$, $b$ are two of those elements.
The number of all $k+2$ element subsets is $\binom{n+2}{k+2}$. But you can also compute it by considering the number of subsets not containing $a$ and $b$ which is $\binom n{k+2}$, subsets containing $a$, but not $b$ or $b$, but not $a$, each of which is $\binom n{k+1}$ and the number of subsets containing both $a$ and $b$ which is $\binom nk$.
So $\displaystyle\binom{n+2}{k+2}=\binom n{k+2}+2\binom n{k+1}+\binom nk$.
A: Note that this is just a special case of Vandermonde's identity, which says
$${m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k},\qquad m,n,r\in\mathbb{N}_0.$$
The result you're looking for occurs when $m=2$, and there are several proofs on the linked wiki page.
