How to prove the combinatorial identity $\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}k2^k=2^\ell n\binom{2n-\ell}{n}$ for $n\ge\ell\ge0$?

Question

With the aid of the simple identity \begin{equation*} \sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{k}}=2^n \end{equation*} in Item (1.79) on page 35 of the monograph

R. Sprugnoli, Riordan Array Proofs of Identities in Gould’s Book, University of Florence, Italy, 2006. (Has this monograph been formally published somewhere?)

I proved the combinatorial identity $$ \sum_{k=1}^{n}\binom{2n-k-1}{n-1}k2^k=n\binom{2n}{n}, \quad n\in\mathbb{N}. $$

My question is: how to prove the more general combinatorial identity $$ \sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}k2^k=2^\ell n\binom{2n-\ell}{n} $$ for $n\ge\ell\ge0$?

Answer 1

For $n\ge\ell=0$, it follows that \begin{align*} \sum_{k=0}^{n}\binom{2n-k-1}{n-1}2^kk &=\sum_{k=0}^{n-1}\binom{n+k-1}{n-1}(n-k)2^{n-k}\\ &=n2^n\sum_{k=0}^{n-1}\binom{n+k-1}{n-1}\frac{1}{2^{k}} -2^{n}\sum_{k=1}^{n-1}\binom{n+k-1}{n-1}\frac{k}{2^{k}}\\ &=n2^n\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac{1}{2^{k}} -2^{n}n\sum_{k=0}^{n-2}\binom{n+k}{k}\frac{1}{2^{k}}\\ &=n\binom{2n}{n}, \end{align*} where we used the identity \begin{equation} \sum_{k=0}^{n}\binom{n+k}{k}\frac1{2^{k}}=2^n, \quad n\ge0, \end{equation} which has been mentioned in the question.

Assume that the claimed identity in the question is valid for some $n>\ell>0$. Then it is easy to see that \begin{align*} \sum_{k=\ell+1}^{n}\binom{2n-k-1}{n-1}2^kk &=\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}2^kk-\binom{2n-\ell-1}{n-1}\ell2^\ell\\ &=2^\ell n\binom{2n-\ell}{n}-\binom{2n-\ell-1}{n-1}\ell2^\ell\\ &=2^{\ell+1}n\binom{2n-\ell-1}{n}. \end{align*} Inductively, we conclude that the claimed identity in the question is valid for all $n\ge\ell\ge0$. That is, the identity \begin{equation}\label{sum-central-binom-ell-eq} \sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}2^kk =\binom{2n-\ell}{n}2^\ell n, \quad n\ge\ell\ge0 \end{equation} is valid.

Answer 2

The classical Euler's gamma function $\Gamma(z)$ can be defined by \begin{equation} \Gamma(z)=\lim_{n\to\infty}\frac{n!n^z}{\prod_{k=0}^n(z+k)}, \quad z\in\mathbb{C}\setminus\{0,-1,-2,\dotsc\}. \end{equation} The extended binomial coefficient $\binom{z}{w}$ for $z,w\in\mathbb{C}$ is defined by \begin{equation} \binom{z}{w}= \begin{cases} \dfrac{\Gamma(z+1)}{\Gamma(w+1)\Gamma(z-w+1)}, & z\not\in\mathbb{N}_-,\quad w,z-w\not\in\mathbb{N}_-;\\ 0, & z\not\in\mathbb{N}_-,\quad w\in\mathbb{N}_- \text{ or } z-w\in\mathbb{N}_-;\\ \dfrac{\langle z\rangle_w}{w!},& z\in\mathbb{N}_-, \quad w\in\mathbb{N}_0;\\ \dfrac{\langle z\rangle_{z-w}}{(z-w)!}, & z,w\in\mathbb{N}_-, \quad z-w\in\mathbb{N}_0;\\ 0, & z,w\in\mathbb{N}_-, \quad z-w\in\mathbb{N}_-;\\ \infty, & z\in\mathbb{N}_-, \quad w\not\in\mathbb{Z}, \end{cases} \end{equation} where \begin{align} \mathbb{Z}&=\{0,\pm1,\pm2,\dotsc\}, & \mathbb{N}&=\{1,2,\dotsc\},\\ \mathbb{N}_0&=\{0,1,2,\dotsc\}, & \mathbb{N}_-&=\{-1,-2,\dotsc\} \end{align} and \begin{align} \langle\alpha\rangle_n&=\prod_{k=0}^{n-1}(\alpha-k)\\ &= \begin{cases} \alpha(\alpha-1)\dotsm(\alpha-n+1), & n\ge1\\ 1, & n=0 \end{cases} \end{align} is called the falling factorial.

By the idea of descending induction from Darij Grinberg, we can obtain the following more general identity.

Let $\ell,n\in\mathbb{Z}$ such that $\ell\le n$. Then \begin{equation} \sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}2^kk =\binom{2n-\ell}{n}2^\ell n. \end{equation} If an empty sum is understood to be $0$, then this identity holds for all integers $\ell,n\in\mathbb{Z}$, without the restriction $\ell\le n$.

Answer 3

For $k\in\mathbb{N}$, let $s_k$ and $S_k$ be two sequences independent of $n$ such that $n\ge k\in\mathbb{N}$. The inversion theorem, Theorem 4.4 on page 528 in the freely downloading paper [1] below, reads that \begin{equation}\label{Qi-Zou-Guo-Inversion-thm}\tag{1} s_n=\sum_{k=1}^{n}\binom{k}{n-k}S_k \quad\text{if and only if}\quad (-1)^nnS_n=\sum_{k=1}^{n}\binom{2n-k-1}{n-1}(-1)^kks_k. \end{equation} Applying the inversion theorem in \eqref{Qi-Zou-Guo-Inversion-thm} and considering the identity \begin{equation*} \sum_{k=1}^{n}\binom{2n-k-1}{n-1}2^kk =2n\binom{2n-1}{n}, \end{equation*} which can be deduced from letting $\ell=1$ in the resulted identity of the above answers, we conclude \begin{equation*} \sum_{k=1}^{n}(-1)^k\binom{k}{n-k}\binom{2k-1}{k}=(-1)^n2^{n-1}, \quad n\in\mathbb{N}. \end{equation*} See Remark 3.4 on page 11 in the paper [2] below.

References

1. Feng Qi, Qing Zou, and Bai-Ni Guo, The inverse of a triangular matrix and several identities of the Catalan numbers, Applicable Analysis and Discrete Mathematics 13 (2019), no. 2, 518--541; available online at https://doi.org/10.2298/AADM190118018Q.
2. Feng Qi and Mark Daniel Ward, Closed-form formulas and properties of coefficients in Maclaurin's series expansion of Wilf's function, arXiv (2021), available online at https://arxiv.org/abs/2110.08576v1.