1
$\begingroup$

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!

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

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.

$\endgroup$
  • 1
    $\begingroup$ Great answer! thanks a lot. $\endgroup$ – Galc127 Feb 7 '14 at 13:07
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

$$\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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.