# 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$?

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$$?

• by induction on $\ell$?
– Nemo
Aug 30, 2021 at 7:42
• Yes (descending induction, to be precise). The sum for $\ell$ and the sum for $\ell+1$ differ by only one addend, so the induction proof is completely mechanical. Aug 30, 2021 at 8:03
• Good idea! I will have try. Thank mathoverflow.net/users/82588/nemo and mathoverflow.net/users/2530/darij-grinberg Aug 30, 2021 at 9:09
• The command of Mathematica Sum[Binomial[2 n - k - 1, n - 1]*k*2^k, {k, s, n}, Assumptions -> n >= s && s >= 0 && {s, n} \[Element] Integers] results in $-2^s (s-2 n) \binom{2 n-s-1}{n-1}$, confirming the identity. Aug 30, 2021 at 9:16
• @mathoverflow.net/users/35959/user64494 You are right. I need a proof for it. Motivated by good ideas from mathoverflow.net/users/82588/nemo and mathoverflow.net/users/2530/darij-grinberg, I have inductively proved it just now. Thank you all. Aug 30, 2021 at 9:50

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 $$$$\sum_{k=0}^{n}\binom{n+k}{k}\frac1{2^{k}}=2^n, \quad n\ge0,$$$$ 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 $$$$\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$$$$ is valid.

• It is much better to use descending induction on $\ell$ (that is, induction on $n-\ell$). It makes the induction base trivial, and further shows that the identity holds for negative $\ell$ as well. Sep 5, 2021 at 2:22
• Dear Dr. Darij Grinberg, you are right. I will carry out your idea. Thank you very much. Sep 6, 2021 at 1:17

The classical Euler's gamma function $$\Gamma(z)$$ can be defined by $$$$\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\}.$$$$ The extended binomial coefficient $$\binom{z}{w}$$ for $$z,w\in\mathbb{C}$$ is defined by $$$$\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}$$$$ 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 $$$$\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}2^kk =\binom{2n-\ell}{n}2^\ell n.$$$$ 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$$.

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 $$$$\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.$$$$ 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.
• A detailed proof of this answer is the proof of Lemma 2.1 in "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 arxiv.org/abs/2110.08576v1." Oct 19, 2021 at 3:24