Prove a combinatorics statement

I’m reading a textbook about combinatorics and in the exercise section there is a question:

Prove that this statement is true . $$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+...+\binom{n+m}{m}=\binom{n+m+1}{m}$$

I tried to expand every part with pascal theory which states: $$\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$$ Or use a couple of other theories but they took me nowhere

I can really use a hint or an answer or even someone mentioning the theory I can use for solving this.

Thank you guys . you are amazing.

You just have to replace $$n\choose 0$$ by $$n+1\choose 0$$ because value of both the terms is 1.

The reason behind this is that, the moment we write $$n+1\choose 0$$, it will get added up in the next term as $${n+1\choose 0}+{n+1\choose 1}={n+2\choose 1}$$

Now $$n+2\choose 1$$ will get added in the next term and so on.

• OMG thank you :) May 17, 2020 at 13:55
• You're welcome. May 17, 2020 at 14:18

If I'm not mistaken induction on $$m$$ using $$\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$$ should work. But there is probably a very nice combinatoric proof involving a bijection between two sets of exactly thoses sizes.

You can also perform induction on $$m$$. For $$m=1$$ the property reads $$\binom{n}{0} + \binom{n+1}{1}=\binom{n+2}{1},$$

and this is obviously true (just compute each term). We just need to check that

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

Now, $$\sum_{k=0}^{m+1} \binom{n+k}{k} = \sum_{k=0}^{m} \binom{n+k}{k} + \binom{n+m+1}{m+1}= \binom{n+m+1}{m} + \binom{n+m+1}{m+1}=\binom{n+m+2}{m+1}.$$