Combinatoric interpretation of an equality between sums

Question

I was tasked with proving the following equality for any $n,m\in\Bbb{N}$.

$$\sum_{k=0}^{m}{m \choose k}{{n+k} \choose m}=\sum_{k=0}^{m}{m \choose k}{n \choose k}2^{k}$$

which i have managed to with some ugly double induction.

Many problems of this variety can be solved by calculating the power of some set in two ways and I'm sure there is a way of looking at this equality that yields a nice combinatoric solution. However, I was unable to find it.

Any thoughts? I'm actually curious what it might be since on the left side of the equation we have $2^k$ that looks like we get to choose some subset of $[k]$ but without its power being relevant, while on the right side we have none such terms.

Answer 1

We have $g$ green balls and $r$ red balls (all numbered), we wish to pick $r$ balls and, further, we are allowed to place a mark on the selected green balls. Let $C$ count the ways of doing this.

Letting $k$ be the number of picked green balls, we have $$ C=\sum_{k=0}^{g}{r \choose r-k}{g \choose k}2^{k}=\sum_{k=0}^{g}{g \choose k}{r \choose k}2^{k}$$ which is the RHS of the original eq ($g \leftrightarrow m$, $r \leftrightarrow n$).

Also, letting $j$ be the number of green balls that were not marked (picked or not):

$$C=\sum_{j=0}^{g}{g \choose g-j}{r + j \choose r-(g-j)}=\sum_{j=0}^{g}{g \choose j}{r + j \choose g}$$

where the first factor counts the marked green balls, and the other the rest.

Answer 2

Left hand side:

$$ \begin{aligned} \left(1+\left(1+x\right)\right)^{m}\left(1+x\right)^{n}&=\sum_{k=0}^{m}{\left(\binom{m}{k}(1+x)^{k}\right)}(1+x)^{n}\\ &=\sum_{k=0}^{m}{\left(\binom{m}{k}(1+x)^{n+k}\right)} \end{aligned} $$

coefficient of $x^{m}$ from above expression is $\sum_{k=0}^{m}{\left(\binom{m}{k}\binom{n+k}{m}\right)}$

Right hand side:

$$ \begin{aligned} \left(1+\left(1+x\right)\right)^{m}\left(1+x\right)^{n}&=\left(2+x\right)^{m}\left(1+x\right)^{n}\\ &=\sum_{k=0}^{m}{\left(\binom{m}{k}2^{k}x^{m-k}\right)}(1+x)^{n} \end{aligned} $$

coefficient of $x^{m}$ from the above expression is $\sum_{k=0}^{m}{\left(\binom{m}{k}\binom{n}{k}2^{k}\right)}$

Answer 3

Notice that the right hand side is telling you that you will take $n$ balls, $k$ from $[m]$ and $n-k$ from $[n]$ and you are going to color them gray. The $2^k$ tells you that some of the $k$ balls from $[m]$ that you took you are going to color them black.

On the left hand side you have $$\sum _{k=0}^m\binom{m}{k}\binom{n+k}{m},$$ using Vandermonde's you get (Notice that this is telling you exactly how many are you going to color black, you are coloring black exacly l) $$\sum _{k=0}^m\binom{m}{k}\left (\sum _{l=0}^m\binom{n}{m-l}\binom{k}{l}\right )=\sum _{l=0}^m\binom{n}{m-l}\sum _{k=0}^m\binom{m}{l}\binom{m-l}{k-l}$$ on that last sum you can take out the binomial and get $$\sum _{l=0}^m\binom{n}{m-l}\binom{m}{l}\sum _{k=0}^m\binom{m-l}{k}=\sum _{l=0}^m\binom{n}{l}\binom{m}{l}2^l.$$