# Combinatorial Proof

1. Apr 8, 2007

### Dragonfall

I have a bunch of equations that I must prove 'using combinatorics', which means double counting or some sort of bijective mapping. I haven't done this before, and I'd like to know, as an example, how the following can be proved 'combinatorially':

$$\left(\begin{array}{cc}{n+1}\\{m+1}\end{array}\right)=\sum_{i=0}^{n-m}\left(\begin{array}{cc}{m+i}\\m\end{array}\right)$$

2. Apr 9, 2007

### ircdan

Notice the left hand side counts the number of bitstrings of length n + 1 containing m + 1 ones.

3. Apr 9, 2007

### tim_lou

look at ways of choosing m+1 elements from n+1 objects.

the series tells you that you sum up the ways of choosing m objects from m+i objects. but you want to choose m+1 objects; so what happens to the m+1th element?

$$\sum_{i=n-m}^{0}\binom{m+i}{m}$$
(i keeps decreasing, not increasing)
hint2: choose 1 element first, then choose the other m elements.

if that isn't enough,
hint3: look at the position of the first element when choosing...

Last edited: Apr 9, 2007
4. Apr 9, 2007

### Dragonfall

Shouldn't it be multiplied instead of summed?