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

Now this should help you...

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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