# Show that ${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$

Show that $${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$$

Please help me showing the above identity. I tried to solve it in algebraic way and in combinatoric way, but didn't manage.

Thanks!

• $(2t+3)^n=(2t+2+1)^n$. – Grigory M Feb 7 '14 at 9:57
• I didn't understand how to continue... – Galc127 Feb 7 '14 at 13:06

We are going to show that both sides count the same number of possibilities and therefore have to be equal for the equation: $$\binom nr 2^r3^{n-r}=\sum_{k=r}^n \binom nk\binom kr2^k$$ Suppose there are $n$ people and we want to choose $r$ people from them who form team $1$. The other $n-r$ people form team $2$. Every one in team $1$ can choose a black or a white shirt, everybody in team $2$ can choose a red, green or blue shirt.
We can calculate the number of possibilities by just choosing $r$ people from the $n$ people in $\binom nr$ ways. The number of ways they can pick a color is just $2^r3^{n-r}$, so we get $$\binom nr 2^r3^{n-3}$$ which is the left hand side of the equation.

On the right hand side, we first choose all people without a red shirt ($k$ people). Then, from those people we pick the $r$ persons for team $1$. Lastly, we choose a color for those $k$ people. We sum over $k$, to get all possibilities. This results in $$\sum_{k=r}^n \binom nk\binom kr2^k$$ so we now have proven that the identity is true indeed.

• Great answer! thanks a lot. – Galc127 Feb 7 '14 at 13:07

Or, if you wanted to consider a combinatorial approach to this problem: We have a set of $n$ people, of which we want to select $r$ officers for a committee of size at least $r$, and in the committee choose any amount of people to have some certain quality (say they are "special").

On the LHS, we first select the officers [ $\binom{n}{r}$ ], decide if they are special [ $2^r$ ], then, of the remaining $n-r$ people, decide if they're on the committee, special, or neither [ $3^{n-r}$ ].

On the RHS, we select a committee of size $k$ (of size at least $r$). Then we select $r$ officers, and decide which committee members are special. Summing over $k$ gives the total possibilities we want, i.e., the LHS.

$$\sum_{k=r}^{n}\binom{n}{k}\binom{k}{r}2^{k}=\binom{n}{r}2^{r}\sum_{k=r}^{n}\binom{n-r}{k-r}2^{k-r}=\binom{n}{r}2^{r}\sum_{k=0}^{n-r}\binom{n-r}{k}2^{k}1^{n-r-k}=\binom{n}{r}2^{r}3^{n-r}$$