# A Combinatorial/Algebraic Solution to Combinatorics Identities Exercise

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.

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$$.

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

• First of all, thanks I'll get right to it. Secondly, how come the fact that the sum starts at r doesn't mess things up? Hard to wrap my head around it. Commented Jan 4, 2021 at 13:05
• @Friedman You are welcome. Notice that if you use the identity I hinted you with, then you end up having $k-r$ so you are going to shift the sum to start at $0$ all the way up to $n-r.$ That is why you have $n-r$ in the exponent of $3$ in the RHS. Commented Jan 4, 2021 at 13:06

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

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