A Combinatorial/Algebraic Solution to Combinatorics Identities Exercise

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

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