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

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.

• It doesn't seem to be right when $d=0$ – Richard Martin Nov 8 '18 at 17:36
• if $m \geq n$ the sum is equal to ${n+d+1 \choose m+1}$ however, if $m < n$ that isn't true. – Dominik Kutek Nov 8 '18 at 17:42

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.

• Thank you! I appreciate your answer. – Christophe Nov 8 '18 at 19:40

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