Proving a binomial identity

Question

Prove that ($k\le m$)

$$\sum_{j=k}^m(_{2m+1}^{2j+1})(_k^j)=\frac{2^{2(m-k)}(2m-k)!}{(2m-2k)!k!} , (k\le m)$$

Please help me with this identity, I've spent a lot of time on it but didn't solve the problem.

Answer 1

According to OPs expression we show:

The following is valid

\begin{align*} \sum_{j=k}^{m}\binom{2m+1}{2j+1}\binom{j}{k}=4^{m-k}\binom{2m-k}{k}\qquad\qquad 0\leq k \leq m \end{align*}

In the following we use the coefficient of operator $[x^k]$ to denote the coefficient of $x^{k}$ in a series $\sum_{j=0}^{\infty}a_jx^j$.

We start with the left hand side and transform the sum into a coefficient of $x^k$ of a polynomial in $x$.

\begin{align*} \sum_{j=k}^{m}\binom{2m+1}{2j+1}\binom{j}{k}&=\sum_{j=0}^{m}\binom{2m+1}{2j+1}\binom{j}{k}\tag{1}\\ &=[x^k]\sum_{j=0}^{m}\binom{2m+1}{2j+1}(1+x)^j\tag{2} \end{align*}

Comment:

• In (1) we start the index $j$ from $0$. Note that $\binom{j}{k}=0$ if $j<k$. We also write $\binom{j}{k}=[x^k](1+x)^j$.

• In (2) we use the linearity of the coefficient of operator.

Note, that (2) contains binomial coefficients with odd $2j+1$. We consider $(1\pm y)^{2m+1}$ and split it into odd and even parts. \begin{align*} (1\pm y)^{2m+1}&=\sum_{j=0}^{m}\binom{2m+1}{2j}y^{2j}\pm \sum_{j=0}^{m}\binom{2m+1}{2j+1}y^{2j+1}\\ \end{align*}

We get \begin{align*} \sum_{j=0}^{m}\binom{2m+1}{2j+1}y^{2j}=\frac{(1+y)^{2m+1}-(1-y)^{2m+1}}{2y} \end{align*}

Substituting: $y\rightarrow\sqrt{1+x}$ we obtain from (2)

\begin{align*} \sum_{j=k}^{m}\binom{2m+1}{2j+1}\binom{j}{k} =[x^k]\frac{(1+\sqrt{1+x})^{2m+1}-(1-\sqrt{1+x})^{2m+1}}{2\sqrt{1+x}}\tag{3} \end{align*}

Note, the expression on the RHS is a polynomial, since the factor $\sqrt{1+x}$ cancels out.

Next we transform the RHS of OPs expression. We consider it as coefficient of the polynomial

\begin{align*} 4^{m-k}\binom{2m-k}{k}&=4^{m-k}[x^k]\sum_{j=0}^{m}\binom{2m-k}{k}x^{j}\\ &=4^m[x^k]\sum_{j=0}^{m}\binom{2m-k}{k}\left(\frac{x}{4}\right)^{j}\tag{4} \end{align*}

In order to prove (4) we refer to a useful identity stated as formula (2.1) in H.W.Goulds Combinatorial Identities, Vol. 4. With $n=2m+1$ we get the following expression

\begin{align*} \sum_{j=0}^{m}(-1)^j\binom{2m-j}{j}(t_1t_2)^j(t_1+t_2)^{2m-2j}=\frac{t_1^{2m+1}-t_2^{2m+1}}{t_1-t_2} \end{align*}

Setting $t_1=1+\sqrt{1+x}$ and $t_2=1-\sqrt{1+x}$ we get

\begin{align*} t_1t_2&=-x\\ t_1+t_2&=2\\ t_1-t_2&=2\sqrt{1+x} \end{align*}

It follows \begin{align*} \sum_{j=0}^{m}\binom{2m-j}{j}x^j2^{2m-2j} =\frac{(1+\sqrt{1+x})^{2m+1}-(1-\sqrt{1+x})^{2m+1}}{2\sqrt{1+x}} \end{align*} and we obtain \begin{align*} 4^{m-k}\binom{2m-k}{k}=[x^k]\frac{(1+\sqrt{1+x})^{2m+1}-(1-\sqrt{1+x})^{2m+1}}{2\sqrt{1+x}}\tag{5} \end{align*}

The RHS of (3) and (5) coincide and OPs identity follows.

Answer 2

Suppose we seek to show that $$\sum_{q=k}^m {2m+1\choose 2q+1} {q\choose k} = 4^{m-k} {2m-k\choose k}.$$

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

This has the property that it is zero when $q\gt m$ so it controls the range and we may extend the sum to infinity to obtain

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

Extracting the coefficient we get

$$\sum_{q=0}^{2m-2k} {2m-k\choose q} {2m-2k-q+k\choose k} = \sum_{q=0}^{2m-2k} {2m-k\choose q} {2m-k-q\choose k} \\ = \sum_{q=0}^{2m-2k} {2m-k\choose 2m-k-q} {2m-k-q\choose k}.$$

This is $$\sum_{q=0}^{2m-2k} {2m-k\choose k} {2m-2k\choose q} \\ = {2m-k\choose k} \sum_{q=0}^{2m-2k} {2m-2k\choose q} \\ = 2^{2m-2k} {2m-k\choose k}$$

as claimed.