Proof of Equations using Combinatorics

[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)

 

[ircdan]

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

 

[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?

hint1: read the sum backward
\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...

 

[Dragonfall]

Shouldn't it be multiplied instead of summed?