How to prove $\sum_{k=0}^{n} \binom{k+1}{k} = \binom{n+2}{n}$

Question

I was given this problem to solve/prove the following identity

$$\sum_{k=0}^{n} \binom{k+1}{k} = \binom{n+2}{n}$$

The only thing I can think of on how to prove this is to repeatedly apply pascal's Identity on the right hand side of the equation.

$$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$

However, this doesn't work as this process ceases after applying the identity twice and you're left with $\binom{n}{n}$, which you cannot further decompose into two. Any help on how to go about this proof?

Answer 1

$$\binom{k+1}{k}=k+1$$

So:

$$\sum_{k=0}^{k=n}\binom{k+1}{k}=\sum_{k=0}^{k=n}k+1={{(n+1)(n+2)}\over 2}$$

$$\binom{n+2}{n}={{(n+2)!}\over{n!(n+2-n)}}={{(n+2)(n+1)}\over 2}$$

Answer 2

You have $$ {k+1 \choose k}=k+1,\ \ \ {n+2\choose n}=\frac{(n+2)(n+1)}2.$$

Answer 3

As you stated, you can also use pascals identity as follows:

$$\binom{n+2}{n} = \binom{n+1}{n} + \binom{n+1}{n-1}$$ $$\binom{n+1}{n-1} = \binom{n}{n-1} + \binom{n}{n-2}$$ ... $$\binom{3}{1} = \binom{2}{1} + \binom{2}{0}$$ $$\binom{2}{0} = \binom{1}{0} $$

Adding you get the desired result.