Prove $\binom{n+2}{k+2} = \binom{n}{k+2} + 2\binom{n}{k+1} + \binom{n}{k}$

Question

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

Answer 1

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)

Answer 2

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$.

Answer 3

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.