Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$

Question

Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-Reform} for $m\ge2$?

For non-negative integers $k,n\ge0$, I guess that \begin{equation}\label{combin-ID-Maclaurin}\tag{Q1} \sum_{\ell=0}^{n}\binom{2n+1}{2\ell+1} \binom{n-\ell}{n-k} =2^{2k}\frac{2n+1}{2k+1}\binom{n+k}{2k}. \end{equation}

The identity \eqref{combin-ID-Maclaurin} is equivalent to \begin{equation}\label{first-equiv-form}\tag{Q2} \sum_{\ell=0}^{k} \binom{2n+1}{2k-2\ell+1} \binom{\ell+n-k}{\ell} =2^{2k}\frac{2n+1}{2k+1}\binom{n+k}{2k}, \quad k,n\ge0 \end{equation} and is equivalent to \begin{equation}\label{combin-ID-Mac-Equiv}\tag{Q3} \sum_{\ell=0}^{n}\binom{2n+1}{2\ell+1} \binom{n-\ell}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}, \quad n\ge0,\quad n\ge m\in\mathbb{Z}. \end{equation} The identity \eqref{combin-ID-Mac-Equiv} can be further reformulated as \begin{equation}\label{combin-ID-Mac-Reform}\tag{Q4} \sum_{\ell=0}^{n}\binom{2n+1}{2\ell} \binom{\ell}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m},\quad n\ge0,\quad n\ge m\in\mathbb{Z}. \end{equation}

When $m<0$, it is trivial that both sides of \eqref{combin-ID-Mac-Reform} are equal to $0$.

When $m=0$, the identity \eqref{combin-ID-Mac-Equiv} or \eqref{combin-ID-Mac-Reform} becomes \begin{equation}\label{m=0-(1.93)Sprug}\tag{Q5} \sum_{\ell=0}^{n}\binom{2n+1}{2\ell} =\sum_{\ell=0}^{n}\binom{2n+1}{2\ell+1} =2^{2n}, \quad n\ge0. \end{equation} This is just the identity (1.93) on page 38 in the monograph [1] below.

When $m=1$, the identity \eqref{combin-ID-Mac-Equiv} or \eqref{combin-ID-Mac-Reform} reduces to \begin{equation}\tag{Q6} \sum_{\ell=0}^{n}(n-\ell)\binom{2n+1}{2\ell+1} =\sum_{\ell=0}^{n}\binom{2n+1}{2\ell}\ell =2^{2(n-1)}(2n+1), \quad n\ge1. \end{equation} This follows from combining \eqref{m=0-(1.93)Sprug} with the identity \begin{equation}\tag{Q7} \sum_{\ell=1}^{n}\binom{2n+1}{2\ell+1}\ell=(2n-1)4^{n-1}, \quad n\ge1, \end{equation} which can be found in (1.100) on page 40 of the monograph [1] below.

Could you please recommend a reference to or provide a proof of the above identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-Reform} for $m\ge2$?

References

1. R. Sprugnoli, Riordan Array Proofs of Identities in Gould’s Book, University of Florence, Italy, 2006.
2. F. Qi, Diagonal recurrence relations for the Stirling numbers of the first kind, Contrib. Discrete Math. 11 (2016), no. 1, 22--30; available online at https://doi.org/10.11575/cdm.v11i1.62389.
3. F. Qi, Diagonal recurrence relations, inequalities, and monotonicity related to the Stirling numbers of the second kind, Math. Inequal. Appl. 19 (2016), no. 1, 313--323; available online at https://doi.org/10.7153/mia-19-23.
4. F. Qi and B.-N. Guo, A diagonal recurrence relation for the Stirling numbers of the first kind, Appl. Anal. Discrete Math. 12 (2018), no. 1, 153--165; available online at https://doi.org/10.2298/AADM170405004Q.

Answer 1

We will prove the identity (A8) that qifeng618 alluded to. The method is called the Wilf-Zeilberger methodology. To this end, define the two functions (suppressing $x$) $$F(n,k):=\frac{\binom{2x+1}{2k+1}\binom{x-k}{n-k}(2n+1)}{(2x+1)\binom{x+n}{2n}4^n} \qquad \text{and} \qquad G(n,k):=-\frac{F(n,k)\,2k\,(2k+1)}{2(x+n+1)(n+1-k)}.$$ Next, verify (preferably using a math software) that $$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k).$$ Now, sum both sides of this equation over all integers $k$. The right-hand side then vanishes, showing that $f(n+1)-f(n)=0$ where $f(n):=\sum_kF(n,k)$. Since $f(0)=1$, it follows that $f(n)=1$ for all $n$. That is, $$\sum_{k=0}^n\frac{\binom{2x+1}{2k+1}\binom{x-k}{n-k}(2n+1)}{(2x+1)\binom{x+n}{2n}4^n}=1 \qquad \text{or} \qquad \sum_{k=0}^n\binom{2x+1}{2k+1}\binom{x-k}{n-k}=\frac{2x+1}{2n+1}\binom{x+n}{2n}4^n,$$ as desired. $\,\,\,\,\square$

Answer 2

The formula (3.27) on pages 59--60 in the monograph [1] below reads that \begin{equation}\label{Sprugnoli-Gould-2006-(3.27)}\tag{A8} \sum_{k=0}^n\binom{2x+1}{2k+1}\binom{x-k}{n-k} =\frac{2x+1}{2n+1}\binom{x+n}{2n}4^n. \end{equation} All the identities (Q1) to (Q7) in the question are variants or special cases of the identity \eqref{Sprugnoli-Gould-2006-(3.27)}.

The identity \eqref{Sprugnoli-Gould-2006-(3.27)} can be reformulated as \begin{equation}\label{combin-ID-Maclauri}\tag{V1} \sum_{k=0}^{n}\binom{2n+1}{2k+1} \binom{n-k}{n-m} =2^{2m}\frac{2n+1}{2m+1}\binom{n+m}{2m} \end{equation} for $m\ge0$ and $n\ge0$. The identity \eqref{combin-ID-Maclauri} is equivalent to \begin{equation}\label{combin-ID-Mac-Equi}\tag{V2} \sum_{k=0}^{n}\binom{2n+1}{2k+1} \binom{n-k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m} \end{equation} for $n\ge0$ and $n\ge m\in\mathbb{Z}$. The identity \eqref{combin-ID-Mac-Equi} can be further reformulated as \begin{equation}\label{combin-ID-Mac-Refor}\tag{V3} \sum_{k=0}^{n}\binom{2n+1}{2k} \binom{k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m} \end{equation} for $n\ge0$ and $n\ge m\in\mathbb{Z}$.

When $m=0$, the identity \eqref{combin-ID-Mac-Equi} or \eqref{combin-ID-Mac-Refor} becomes \begin{equation}\label{m=0-(1.93)Spru}\tag{V4} \sum_{\ell=0}^{n}\binom{2n+1}{2\ell} =\sum_{\ell=0}^{n}\binom{2n+1}{2\ell+1} =2^{2n}, \quad n\ge0. \end{equation} This is just the identity (1.93) on page 38 of the monograph [1] below.

When $m=1$, the identity \eqref{combin-ID-Mac-Equi} or \eqref{combin-ID-Mac-Refor} reduces to \begin{equation*} \sum_{\ell=0}^{n}(n-\ell)\binom{2n+1}{2\ell+1} =\sum_{\ell=0}^{n}\binom{2n+1}{2\ell}\ell =2^{2(n-1)}(2n+1), \quad n\ge1. \end{equation*} This follows from combining \eqref{m=0-(1.93)Spru} with the identity \begin{equation*} \sum_{\ell=1}^{n}\binom{2n+1}{2\ell+1}\ell=(2n-1)4^{n-1}, \quad n\ge1, \end{equation*} which can be found in Equation (1.100) on page 40 of the monograph [1] below.

Sometimes we have been discovering a variant or a special case of a known result in mathematics.

Reference

1. R. Sprugnoli, Riordan Array Proofs of Identities in Gould’s Book, University of Florence, Italy, 2006.