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$
    – Negar
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.