Prove that, $${n \choose m}+2{n-1 \choose m}+\ldots+(n-m+1){m \choose m}={n+2 \choose m+2}$$
My work:
I thought it would be better to use combinatorial argument than trying to provide a rigorous proof.
So, I find a combinatorial argument that apparently satisfies the left hand side of the equality. I thought it as there are $n+1$ people and the number of ways in which I can choose $m$ members of a committee and the number of ways we can choose the president of the committee. That is, I choose $m$ people from the available pool of $n$ people and leave out a member a there is one way to choose the president. Again, I choose $m$ people from the available pool of $n-1$ people and leave out $2$, and there are $2$ ways to choose the president, and I continue these steps which yields $n+1 \choose m+1$ which is obviously not correct. Where am I going wrong in this approach?
Again, to match the right side of the equality(though this should not be the proper way,and I sho) I try to find out another combinatorial argument. I think of it as, there are $n+2$ people. I start by choosing $m$ members from an available pool of $n$ people and leave out $2$ people. Now,these $2$ people can be chosen for the post of Jt. Secretary so that the order of choice does not matter. Again, I choose $m$ members from an available pool of $n-1$ people and leave out $3$ people. Now, If I choose 2 people, this can be done in $3$ ways and not the required $2$ ways. Where should I rectify this argument to correct this thing?
Please help.
Suppose we have $n+2$ books in a row numbered from $1$ to $n+2$ and we want to choose $m+2$ of them. Obviously, we can do that in $\binom {n+2}{m+2}$ ways, i.e. the right hand side of your equality. We can also first choose the index (number) of the second book we want to choose. Suppose that we choose index $i$ for the second book. When $i=1$ or $(n+2)-i<m$, the number of possibilities to choose the other books is $0$, because we can't choose one book if the second book is at position $1$ and we can't choose $m$ books after position $i=(n+2)-m+1$. Now, the number of possibilities to choose the first book before position $i$ is $i-1$. The number of possibilities to choose $m$ books after position $i$ is $\binom{n+2-i}{m}$. If we put this together, we get $$ \sum_{i=2}^{n+2-m}(i-1)\binom{n+2-i}{m} $$ If we now set $j=i-1$ ($i=j+1$) we get $$ \sum_{j=1}^{n+1-m}j\binom{n+1-j}{m}=\binom nm+2\binom{n-1}m+\cdots +(n+1-m)\binom mm $$