0
$\begingroup$

I've already proved this statement algrebraically. I'm asked to prove it with combinatorics.

So far I came up with,

LHS= # ways to choose m apples from a total of m,m+1,...,n

RHS= # ways to choose m+1 apples from a total of n+1

I've just started combinatorics so I'm not really familiar with what a combinatorics proof looks like. I don't manage to link these two ways of counting without refering to my algebraic proof. A little help would be very appreciated.

Thanks in advance.

$\endgroup$
2
$\begingroup$

You want to prove that $$\sum_{k=m}^n \binom{k}{m} = \binom{n+1}{m+1}$$

The RHS counts the number of ways to choose $m+1$ apples from among $n+1$ apples (numbered $1$ to $n+1$, say).

Suppose the last of the $m+1$ apples we choose is numbered $k+1$. This means that the remaining $m$ apples must be chosen from the apples $1$ to $k$, and there are $\displaystyle \binom{k}{m}$ ways of doing so. Noting that $k$ can take on any value from $m$ to $n$, and summing over these possibilities, gives the LHS.

$\endgroup$
2
$\begingroup$

Here's one solution: $\binom{r}{m}$ denotes the number of bit-strings of length $r$ with $m$ $1$'s (and $r-m$ $0$'s). Now, the LHS counts the number of bit-strings with $m$ $1$'s of length $m,m+1,\ldots,n$. To bit-strings of length $m+i$ add $1,0,\ldots,0$, where there are $(n-m-i)$ zeroes, for $i=0,\ldots,n-m$. Then you have all bit-strings of length $m+i+1+n-m-i=n+1$ with $m+1$ $1$'s. This is the number $\binom{n+1}{m+1}$.

What I did was defining a bijection between the objects counted on the LHS and the objects counted on the RHS.

$\endgroup$
  • $\begingroup$ Thanks for your explanation. It was very clear. $\endgroup$ – Jacques Ung Mar 25 '14 at 21:45
  • 2
    $\begingroup$ If you feel that your question has been answered, you can accept an answer (or don't accept if you would like to receive alternative answers) - in any case, I see that you typically do not accept answers, which may make people less willing to answer your questions. $\endgroup$ – mathse Mar 25 '14 at 21:52

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.