Pascal triangle, getting to the sum of it: $\binom{n}n+\binom{n+1}n+\ldots+\binom{n+m}n$

Question

So we know that

$$\binom{n}0+\binom{n}1+\ldots+\binom{n}n=2^n\;.$$

What about the following sum?

$$\binom{n}n+\binom{n+1}n+\ldots+\binom{n+m}n\;?$$

(a) Identify several examples of this sum on the Pascal triangle and try to discover what it is equal to.

(b) Guided by your work above (hopefully), prove it algebraically by using a property of the binomial coefficient in the Pascal triangle

Answer 1

$\sum_{j=n}^m\binom{j}{n}=\binom{m+1}{n+1}$

What you want to count is the binary sequences of length $m$ or less with exactly $n$ ones. You can obtain each of these exactly once by considering the sequences of length $m+1$ with exactly $n+1$ ones and deleting the right-most one along with all the digits to the right.

For example:

$01001100\mapsto 01001$

Answer 2

Hint: While you are trying the examples suggested, think about the relation from Pascal's Triangle: $$ \binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}\implies\binom{n}{k}=\binom{n+1}{k+1}-\binom{n}{k+1} $$ Sum the equation on the right of the arrow in $n$ and think about Telescoping Series.