# Prove by counting in two different ways

I'm am not completely clear on what is means to count in two different ways.

Here is the question.

$m$ and $n$ are integers with $0 \le m \le n$. In a town in the USA there are $n+1$ townspeople. This town is run by one mayor and $m$ council-members (the mayor cannot be a councillor). Prove the following by counting in two different ways the number of ways to choose a town's elected officials.

$(n+1)$$n \choose m$$=(n+1-m)$${n+1}\choose m$

So if anyone can explain how to do these types of questions that would be great.

Thanks

These kinds of proofs are called combinatorial proofs. In order to choose a mayor and $m$ council-members, we can do it in two ways: we can choose a mayor and then the council-members, or we can choose the council-members and then choose the mayor.
In the first way, we have $n + 1$ choices for the mayor. To choose a council, we need to pick $m$ people from the remaining $n$ townspeople (as the mayor cannot be a councillor). Thus, there are $\binom{n}{m}$ ways to choose the council; multiplying the two together gives $(n + 1)\binom{n}{m}$ ways in total.
• I think so. So I guess that in the other formula there are $n+1$ choices for councillors and we need $m$ councillors. Once we have chosen the councillors we choose the mayor second. This is still out of the population of $n+1$ but we need to subtract the $m$ council-members. – Steph Sep 20 '15 at 22:34