Calculate the sum $\sum_{k=0}^d\binom{n+k}{m}$

Question

Any way to calculate this sum combinatorially/analytically, pls?

I known the answer is $\binom{n+1+d}{m+1}$. However I couldn't prove it.

Answer 1

You want to calculate the sum: $$\sum_{k=0}^{d} {n+k \choose m} $$

I claim it is equal to: $$ {n + d + 1 \choose m+1} - {n \choose m+1} $$

Now, why: Looking at the sum, one can notice, that you are considering subsets P of $\{1,2,...,n+k\}$ such that |P|= m. However, it is the same as considering subsets P' of $ \{1,2,...,n+k+1\}$ such that |P'| = m+1 and $ n+k+1 \in P' $.

Now, take a look at the second "sum". It counts all subsets S of $ \{1,2,...,n+d+1\} $ such that |S|=m+1 and the largest element of subset S is greater than n (so we have to substract $ {n \choose m+1} $ (subsets with largest element less or equal n) from all subsets of $\{1,2,...,n+d+1\}$ that is from ${n+d+1 \choose m+1}$.

So here: $$ \sum_{k=0}^d {n+k \choose m} $$ we're counting with respect to the largest element ( for fixed k, it is n+k+1) all the way from k=0 to k=d ( so all the way from the largest element being n+1, to being n+d+1) and that is exactly what we've counted in different manner : $ { n+d+1 \choose m+1 } - { n \choose m+1} $

Hope it's clear.

Answer 2

Try to answer on this question:

A box contains $n$ identical balls numbered $1$ through $n$. Suppose $m+1$ balls are drawn in succession. In how many ways can be this done if the largest number drawn is less than or equal to $l$?

$\underline{\rm 1.st\; answer:}$

Largest choosen number must be between $m+1$ and $l$ so:

$\bullet$ If the largest number is $m+1$ then we choose all other $m$ numbers between $m$ numbers, so that is ${m\choose m}$ ways.

$\bullet$ If the largest number is $m+2$ then we choose all other $m$ numbers between $m+1$ numbers, so that is ${m+1\choose m}$ ways.

$\bullet$ If the largest number is $m+3$ then we choose all other $m$ numbers between $m+2$ numbers, so that is ${m+2\choose m}$ ways.

...

$\bullet$ If the largest number is $l$ then we choose all other $m$ numbers between $l-1$ numbers, so that is ${l-1\choose m}$ ways.

Owerall we can do this on
$$\sum _{k=m}^l{k-1\choose m}$$ ways.

$\underline{\rm 2.nd\; answer:}$ On the othe hand if we take any $m+1$ element subset in $\{1,2,...,l\}$ the biggest number will be smaller than $l$, so we can do this on $${l\choose m+1}$$

So we get a formula $$\boxed{\sum _{k=m}^l{k-1\choose m}= {l\choose m+1}}$$

Now this should help you...