How to prove the following equation or how to prove when k increases L.H.S also increases for fixed integer r.

Question

How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r-\frac{k}{2}}{i}\big(\sum\limits_{l=0}^{r-2i}\binom{r-\frac{k}{2}-i}{l}2^l\binom{k}{r-2i-l}\big)=\binom{2r}{r}$ or help me to show when k increases L.H.S also increases for fixed r. I checked in computer search L.H.S is equal to $\binom{2r}{r}$. I tried to prove in the way of markus-scheuer's answer to the question How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$ by using generating function. What I got is $[v^r](1+v)^k(1+\frac{2}{v})^{r-\frac{k}{2}}(1+\frac{1}{v^2+2v})^{r-\frac{k}{2}}.$ I don't know how to solve after this. Please help me to solve.

Answer 1

We show that

$$\sum_{q=0}^{\lfloor r/2\rfloor} {r-k\choose q} \sum_{l=0}^{r-2q} {r-k-q\choose l} 2^l {2k\choose r-2q-l} = {2r\choose r}.$$

For the inner sum we introduce

$${2k\choose r-2q-l} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-2q-l+1}} (1+z)^{2k} \; dz.$$

This has the property that it vanishes when $l\gt r-2q$ and hence we may extend the range of $l$ to infinity. We get for the inner sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-2q+1}} (1+z)^{2k} \sum_{l\ge 0} {r-k-q\choose l} 2^l z^l \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-2q+1}} (1+z)^{2k} (1+2z)^{r-k-q} \; dz.$$

This too has the convenient property that the pole disappears when $2q\gt r$ and hence we may extend the range of $q$ to infinity as well, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} (1+z)^{2k} (1+2z)^{r-k} \sum_{q\ge 0} {r-k\choose q} \frac{z^{2q}}{(1+2z)^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} (1+z)^{2k} (1+2z)^{r-k} \left(1+\frac{z^2}{1+2z}\right)^{r-k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} (1+z)^{2k} (1+z)^{2r-2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} (1+z)^{2r} \; dz \\ = {2r\choose r}.$$

This concludes the argument.

Answer 2

It seems there were small typos or a misunderstanding when applying the substitution rule. It should be $2v$ instead of $\frac{2}{v}$ and $\frac{v^2}{1+2v}$ instead of $\frac{1}{v^2+2v}$.

We obtain \begin{align*} \color{blue}{\sum_{i=0}^{\lfloor\frac{r}{2}\rfloor}}&\color{blue}{\binom{r-\frac{k}{2}}{i}\sum_{l=0}^{r-2i}\binom{r-\frac{k}{2}-i}{l}2^l\binom{k}{r-2i-l}}\\ &=\sum_{i=0}^\infty [z^i](1+z)^{r-\frac{k}{2}}\sum_{l=0}^\infty [u^l](1+2u)^{r-\frac{k}{2}-i}[v^{r-2i-l}](1+v)^k\tag{1}\\ &=[v^r](1+v)^k\sum_{i=0}^\infty v^{2i}[z^i](1+z)^{r-\frac{k}{2}}\sum_{l=0}^\infty v^l[u^l](1+2u)^{r-\frac{k}{2}-i}\tag{2}\\ &=[v^r](1+v)^k\sum_{i=0}^\infty v^{2i}[z^i](1+z)^{r-\frac{k}{2}}(1+2v)^{r-\frac{k}{2}-i}\tag{3}\\ &=[v^r](1+v)^k(1+2v)^{r-\frac{k}{2}}\sum_{i=0}^\infty \left(\frac{v^2}{1+2v}\right)^i[z^i](1+z)^{r-\frac{k}{2}}\tag{4}\\ &=[v^r](1+v)^k(1+2v)^{r-\frac{k}{2}} \left(1+\frac{v^2}{1+2v}\right)^{r-\frac{k}{2}}\tag{5}\\ &=[v^r](1+v)^{2r}\tag{6}\\ &\color{blue}{=\binom{2r}{r}}\tag{7} \end{align*}

Comment:

• In (1) we apply the coefficient of operator three times and set the upper limit of the sums to $\infty$ without changing anything, since we are adding zeros only.

• In (2) we use the linearity of the coefficient of operator, do some rearrangements and use the rule \begin{align*} [u^{p-q}]A(u)=[u^p]u^qA(u) \end{align*}

• In (3) we apply the substitution rule of the coefficient of operator with $u:=v$ to the inner sum \begin{align*} A(v)=\sum_{i=0}^\infty a_i v^i=\sum_{i=0}^\infty v^i [u^i]A(u) \end{align*}

• In (4) we do some rearrangements as preparation for the next substitution.

• In (5) we apply the substitution rule of the coefficient of operator with $z:=\frac{v^2}{1+2v}$.

• In (6) we do some simplifications.

• In (7) we select the coefficient of $v^{r}$.