Want to use Herbert Wilf's snake oil method to show $\sum_k \binom{2n+1}{2k}\binom{m+k}{2n} = \binom{2m+1}{2n}$

Question

I was trying to use the snake oil method to show that $$\sum_k \binom{2n+1}{2k}\binom{m+k}{2n} = \binom{2m+1}{2n}$$

tl;dr I wasn't able to and desperately need help

My approach was to try to establish a more general identity regarding $$\sum_k \binom{2n+1}{2k}\binom{m+k}{s}$$ So I let $$F(x) = \sum_s \sum_k \binom{2n+1}{2k}\binom{m+k}{s} x^s$$ By changing the order of summation, I obtained $$F(x) = \sum_k \sum_s \binom{2n+1}{2k}\binom{m+k}{s} x^s = \sum_k \binom{2n+1}{2k}(1+x)^{m+k}$$ After this, I noted that $$\sum_{k \geq 0} \binom{n}{2k}x^{2k} = \frac{(1+x)^n + (1-x)^n}{2}$$ Now, $$F(x) = \frac{(1+x)^m}{2}((1+\sqrt{1+x})^{2n+1} + (1-\sqrt{1+x})^{2n+1})$$ I'm having trouble finding the coefficient of $x^{2n}$ in this generating function.

Alternate approach: I could have created a generating function where the summation was on $m$ but that proved to be fruitless.

Answer 1

Following request by OP for snake oil method we evaluate

$$\sum_{0\le 2k\le q+1} {q+1\choose 2k} {m+k\choose q}$$

and introduce

$$F(z, u) = \sum_{q\ge 0} \sum_{m\ge 0} z^q u^m \sum_{0\le k, 2k\le q+1} {q+1\choose 2k} {m+k\choose q} \\ = \sum_{q\ge 0} \sum_{m\ge 0} {m\choose q} z^q u^m + \sum_{q\ge 0} \sum_{m\ge 0} z^q u^m \sum_{1\le k, 2k\le q+1} {q+1\choose 2k} {m+k\choose q} \\ = \sum_{m\ge 0} u^m (1+z)^m + \sum_{m\ge 0} u^m \sum_{k\ge 1} \sum_{q\ge 2k-1} z^q {q+1\choose 2k} {m+k\choose q} \\ = \frac{1}{1-u(1+z)} + \sum_{m\ge 0} u^m \sum_{k\ge 1} z^{2k-1} \sum_{q\ge 0} z^q {q+2k\choose 2k} {m+k\choose q+2k-1} \\ = \frac{1}{1-u(1+z)} + \sum_{k\ge 1} z^{2k-1} \sum_{q\ge 0} z^q {q+2k\choose 2k} \sum_{m\ge 0} u^m {m+k\choose q+2k-1}$$

Continuing with the sum we find

$$\sum_{k\ge 1} z^{2k-1} \sum_{q\ge 0} z^q {q+2k\choose 2k} \sum_{m\ge q+k-1} u^m {m+k\choose q+2k-1} \\ = \sum_{k\ge 1} z^{2k-1} u^{k-1} \sum_{q\ge 0} z^q u^q {q+2k\choose 2k} \sum_{m\ge 0} u^m {m+q+2k-1\choose q+2k-1} \\ = \sum_{k\ge 1} z^{2k-1} u^{k-1} \sum_{q\ge 0} {q+2k\choose 2k} z^q u^q \frac{1}{(1-u)^{q+2k}} \\ = \sum_{k\ge 1} z^{2k-1} u^{k-1} \frac{1}{(1-u)^{2k}} \sum_{q\ge 0} {q+2k\choose 2k} z^q u^q \frac{1}{(1-u)^{q}} \\ = \sum_{k\ge 1} z^{2k-1} u^{k-1} \frac{1}{(1-u)^{2k}} \frac{1}{(1-uz/(1-u))^{2k+1}} \\ = \sum_{k\ge 1} z^{2k-1} u^{k-1} \frac{1-u}{(1-u(1+z))^{2k+1}} \\ = (1-u) \sum_{k\ge 0} z^{2k+1} u^{k} \frac{1}{(1-u(1+z))^{2k+3}} \\ = \frac{(1-u)z}{(1-u(1+z))^3} \sum_{k\ge 0} z^{2k} u^{k} \frac{1}{(1-u(1+z))^{2k}} \\ = \frac{(1-u)z}{(1-u(1+z))^3} \frac{1}{1-uz^2/(1-u(1+z))^2} \\ = \frac{(1-u)z}{1-u(1+z)} \frac{1}{(1-u(1+z))^2-uz^2}$$

Restoring the term in front now yields

$$\frac{1}{1-u(1+z)} + \frac{z}{1-u(1+z)} \frac{1}{1-u(1+z)^2} \\ = \frac{1}{1-u(1+z)} \left(1+ \frac{z}{1-u(1+z)^2}\right) \\ = \frac{1+z}{1-u(1+z)^2}.$$

Extracting coefficients we get

$$[z^q] [u^m] \frac{1+z}{1-u(1+z)^2} = [z^q] (1+z) (1+z)^{2m} = [z^q] (1+z)^{2m+1} = {2m+1\choose q}.$$

Now put $q=2n$ to obtain

$$\bbox[5px,border:2px solid #00A000]{ {2m+1\choose 2n}.}$$

Answer 2

Here is different technique based upon generating functions which might also be convenient. We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k}}&\color{blue}{\binom{2n+1}{2k}\binom{m+k}{2n}}\\ &=\sum_{k}\binom{2n+1}{2k}\binom{m+k}{m+k-2n}\tag{1}\\ &=\sum_{k}\binom{2n+1}{2n+1-2k}\binom{-2n-1}{m+k-2n}(-1)^{m+k}\tag{2}\\ &=\sum_{k\geq 0}[z^{2n+1-2k}](1+z)^{2n+1}[u^{m+k-2n}](1+u)^{-2n-1}(-1)^{m+k}\tag{3}\\ &=(-1)^m[z^{2n+1}](1+z)^{2n+1}\sum_{k\geq 0}(-z^2)^k[u^k]u^{2n-m}(1+u)^{-2n-1}\tag{4}\\ &=(-1)^m[z^{2n+1}](1+z)^{2n+1}(-z^2)^{2n-m}(1-z^2)^{-2n-1}\tag{5}\\ &=[z^{2m-2n+1}](1-z)^{-2n-1}\tag{6}\\ &=-\binom{-2n-1}{2m-2n+1}\tag{7}\\ &=\binom{2m+1}{2m-2n+1}\tag{8}\\ &=\color{blue}{\binom{2m+1}{2n}} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $\infty$ without changing anything since we are adding zeros only.

• In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (5) we apply the substitution rule of the coefficient of operator with $u=-z^2$
  \begin{align*} A(z)=\sum_{k\geq0} a_k z^k=\sum_{k\geq 0} z^k [u^k]A(u) \end{align*}

• In (6) we do some simplifications and apply the same rule as we did in (4).

• In (7) we select the coefficient of $z^{2m-2n+1}$.

• In (8) we apply the same rule as we did in (2).