A Combinatorial/Algebraic Solution to Combinatorics Identities Exercise

Question

The exercise:

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

I have tried everything. Combinatorial proof, differentiating a function to reach both sides, finding patterns of combinatorial identities, binomial coefficient identity and mixtures of all the above. Nothing. One idea which I thought was promising is summing both sides with $\sum_{r=0}^n$ so the right-hand side becomes $5^{n}$ by binomial identity but (a) I'm not sure that is even valid and (b) I couldn't make anything of the left-hand side.

Thanks.

Answer 1

Hint: Show that $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c}.$ Then multiply and divide by $2^r.$

Answer 2

Here is a combinatorial proof. Suppose there are $n$ people, and I want to give them jobs. There are $3$ jobs, let's give them numbers $1,2,3$. Jobs number $1$ and $2$ can be done either at day time or night time, while job number $3$ can only be done at night. I don't care how many people will be at each job, but I want exactly $r$ people to work at day time. So how many options do I have to make such choice? First, I need to choose $r$ people who will work at day. Then for each one of them I need to give either job $1$ or job $2$, so it is $2$ options for each. Finally, for each of the $n-r$ people who will work at night I have three options: to give him either job $1$, job $2$ or job $3$. So the number of options is $\binom{n}{r}2^r3^{n-r}$.

Now let's compute the number of options in a different way. Suppose I want $k$ to be the number of people who will work at either job $1$ or job $2$. Note that $k\geq r$, because all $r$ people who will work at day are counted here. So I have to choose $k$ people out of $n$, the ones who will work either at job $1$ or $2$. Then from these $k$ people I have to choose the $r$ who will work at day time, the others will work at night. Finally, for each of these $k$ people I have two options: to give him job $1$ or to give him job $2$. Note that I don't have to choose anything else-the remaining $n-k$ people are exactly the ones who will do job $3$, and they will obviously do it at night time. And now we sum over the possible values of $k$, and get $\sum_{k=r}^n\binom{n}{k}\binom{k}{r}2^k$.

Answer 3

Let $ n\in\mathbb{N} $, if $r\leq n $, then what is the $ r^{\textrm{th}}$ derivative of $ x\overset{f}{\mapsto}\sum\limits_{k=0}^{n}{\binom{n}{k}x^{k}} $ ?

Well $ \left(\forall x\in\mathbb{R}\right) $ : $$ f^{\left(r\right)}\left(x\right)=\sum_{k=r}^{n}{\binom{n}{k}\frac{k!}{\left(k-r\right)!}x^{k-r}} $$

On the other hand, since $ \left(\forall x\in\mathbb{R}\right),\ f\left(x\right)=\left(1+x\right)^{n} $, then : $$ f^{\left(r\right)}\left(x\right)=\frac{n!}{\left(n-r\right)!}\left(1+x\right)^{n-r} $$

Thus, for all $ x\in\mathbb{R} $, we have : $$ \fbox{$\begin{array}{rcl}\displaystyle\sum_{k=r}^{n}{\binom{n}{k}\binom{k}{r}x^{k}}=\binom{n}{r}x^{r}\left(1+x\right)^{n-r} \end{array}$}$$

Answer 4

Considering the Binomial Expansion,

$$ (1+x)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{k} $$

Differentiating both sides w.r.t. $x$ by r times yields

$$ n(n-1) \cdots(n-r+1)(1+x)^{n-r}=\sum_{k=r}^{n}\left(\begin{array}{c} n \\ k \end{array}\right) k(k-1) \cdots(k-r+1) x^{k-r} $$ $$ \frac{n !}{(n-r) !}(1+x)^{n-r}=\sum_{k=r}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) \frac{k !}{(k-r) !} x^{k-t} $$

Dividing both sides by $r!$ yields $$ \left(\begin{array}{l} n \\ r \end{array}\right)(1+x)^{n-r}=\sum_{k=r}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{l} k \\ r \end{array}\right) x^{k-r} $$ Multiplying both sides by $x^r$, we get a beautiful identity $$ \left(\begin{array}{l} n \\ r \end{array}\right)(1+x)^{n-r} x^{r}=\sum_{k=r}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{l} k \\ r \end{array}\right) x^{k} $$ Putting $x=2$ yields $$ \sum_{k=r}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{l} k \\ r \end{array}\right) 2^{k}=\left(\begin{array}{l} n \\ r \end{array}\right) 2^{r} 3^{n-r} $$