Combinatorics proof of "sum of (k choose m) with k from m up to n is equal to n+1 choose m+1"

Question

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.

Answer 1

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.

Answer 2

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.