-1

$ \binom{n}{m}\binom{m}{m} + \binom{n}{m+1}\binom{m+1}{m} + \binom{n}{m+2}\binom{m+2}{m} + \cdots + \binom{n}{n}\binom{n}{m} = \binom{n}{m} 2^{n-m}$

I am completely lost on where to go. Any hints? Thank you very much!

Henry Huang
  • 11
  • 1
    It is easiest to prove this combinatorially. The term on the right represents the number of committees out of a group of $n$ people with $m$ distinguished members and some amount of other members. – Rushabh Mehta Dec 30 '20 at 00:30
  • 1
    Another way to compute this is by first picking the committee, and then picking the $m$ distinguished members. So, we iterate over all possible sizes of the committee ($m\to n$), and pick $m$ out of them. – Rushabh Mehta Dec 30 '20 at 00:31
  • Welcome to Math StackExchange. Usually, we ask for attempts by the asker at the questions. I do recognise that it's hard to have an attempt for such a question. So, what similar combinatorics questions have you tried before? Have you ever seen similar arguments before like https://math.stackexchange.com/questions/937446/show-by-committee-selection-argument – Benjamin Wang Dec 30 '20 at 00:31
  • Thanks @BenjaminWang, I have an idea of the Right Hand Side of the equation now. But the left hand side I am still stuck. The right hand side is(I think) just choosing m people from n total, then the 2^{n-m} since there are two choices , on the committee or not, and there are n-m peop.e left so 2^ n-m. Am I correct? – Henry Huang Dec 30 '20 at 00:45

1 Answers1

0

There are $n$ people. From these, some will go to a party. From people that go to the party, $m$ will be singers.

Now you can either choose who go to party first (at least $m$), then from the chosen, you choose who will sing.

Or you can choose who will go to party to sing first, and then the remaining $n-m$ people may or may not go to party

acat3
  • 11,897
  • 1
    Thank you! Got it now. I did what you did for the RHS then for the LHS it was basically cases of choosing m+k people from n total people for the committee where k is a real number. Then, from the m+k people, I chose m people from it, and the sum of all the cases led to my solution. Thank you very, very much! – Henry Huang Dec 30 '20 at 00:51