2
$\begingroup$

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.

$\endgroup$

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ OMG thank you :) $\endgroup$ May 17, 2020 at 13:55
  • $\begingroup$ You're welcome. $\endgroup$
    – SarGe
    May 17, 2020 at 14:18
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .