How to prove this (seemingly elusive) double binomial identity?

Question

When manipulating polynomials, I came across a double binomial identity as follows,

$$ \sum_{i=0}^{n} \binom{2n+1}{2i+1} \binom{i}{k} = \binom{2n - k }{k} 2^{2 n-2 k} , $$

where $n$ and $k$ are given nonnegative integers such that $2n \geq k$.

I tried to prove it but failed. I worked on this problem for two days and tried mathematical induction, k-degree derivative at zero, algebra methods but they all didn't work for me.

Answer 1

I haven’t made all the calculations so I may be wrong. But here’s how a proof could work: let $c_{n,k}$ be the LHS. It’s easy to see that $c_{n,k}$ is the coefficient in front of $x^n$ of the series $\sum_l{\binom{2n+1}{2l}x^l}\sum_l{\binom{l}{k}x^l}$.

So $c_{n,k}$ is the coefficient in front of $x^{2n}$ of $\sum_l{\binom{2n+1}{2l}x^{2l}}\sum_l{\binom{l}{k}x^{2l}}$, which can be rewritten as $\frac{(1+x)^{2n+1}+(1-x)^{2n+1}}{2}\frac{x^{2k}}{(1-x)^{k+1}}$. Because of parity considerations, it means that $c_{n,k}$ is the coefficient in front of $x^{2n-2k}$ of $\frac{(1+x)^{2n-k}}{(1-x)^{k+1}}$.

When differentiating twice, this yields the equality $(2n-2k)(2n-2k-1)c_{n,k}=(2n-k)(2n-k-1)c_{n-1,k}+2(2n-k)(k+1)c_{n,k+1}+(k+1)(k+2)c_{n+1,k+2}$.

And then you can use induction on $n-k$, since $(n-1)-k <n-k,n-(k+1)<n-k,(n+1)-(k+2) < n-k$.

Answer 2

Nice identity! Let me generalize it a bit by replacing your $2n$ by an $m$:

Theorem 1. Let $m$ and $k$ be two nonnegative integers such that $m \geq k$. Then, \begin{align*} \sum_{i\in\mathbb{N}}\dbinom{m+1}{2i+1}\dbinom{i}{k}=\dbinom{m-k}{k}2^{m-2k}. \end{align*} Here (and in the following), $\mathbb{N}$ denotes the set $\left\{ 0,1,2,\ldots\right\} $.

Why is this a generalization of your identity? Because if we set $m=2n$ for some nonnegative integer $n$, then all addends in the sum $\sum_{i\in \mathbb{N}}\dbinom{m+1}{2i+1}\dbinom{i}{k}=\sum_{i\in\mathbb{N}}\dbinom {2n+1}{2i+1}\dbinom{i}{k}$ become $0$ except for the first $n+1$ addends (because each $i>n$ satisfies $2i+1>2n+1\geq0$ and therefore $\dbinom {2n+1}{2i+1}=0$), and thus this sum can be rewritten as $\sum_{i=0}^{n} \dbinom{2n+1}{2i+1}\dbinom{i}{k}$, which is precisely the left hand side of your identity.

Note that the condition $m \geq k$ in Theorem 1 is needed; if $m < k$, then the left hand side of Theorem 1 is $0$ (since all addends are zero) while the right is not.

I shall prove Theorem 1 using some notations and some standard results. First the notations: The symbol "$\mathrel{\overset{0}{=}}$" (commonly used as an equality sign between two sums) will mean "equal because the two sides differ only in zeros". In other words, I will put the symbol "$\mathrel{\overset{0}{=}}$" between two sums (or between two expressions that contain sums) to signify that they are equal because they differ from each other only in the presence or absence of some addends that are zero. For example, \begin{align*} & 0+1+2\mathrel{\overset{0}{=}}1+2\qquad\text{and}\\ & \sum_{k=0}^{5}\dbinom{2}{k}\mathrel{\overset{0}{=}}\sum_{k=0}^{3}\dbinom{2} {k}\mathrel{\overset{0}{=}}\sum_{k=0}^{2}\dbinom{2}{k} \end{align*} (since $\dbinom{2}{k}=0$ for all $k>2$). More generally, each $n\in\mathbb{N}$ satisfies \begin{align*} \sum\limits_{k=0}^{n}\dbinom{n}{k}\mathrel{\overset{0}{=}}\sum\limits_{k=0}^{n+1} \dbinom{n}{k}\mathrel{\overset{0}{=}}\sum\limits_{k\in\mathbb{N}}\dbinom{n} {k}\mathrel{\overset{0}{=}}\sum\limits_{k\in\mathbb{Z}}\dbinom{n}{k} \end{align*} (since $\dbinom{n}{k}=0$ whenever $k\notin\left\{ 0,1,\ldots,n\right\} $).

Now to the standard results:

Theorem 2 (upside-down Vandermonde convolution). Let $n,x,y\in\mathbb{N}$. Then, \begin{align*} \dbinom{n+1}{x+y+1}=\sum_{j=0}^{n}\dbinom{j}{x}\dbinom{n-j}{y}. \end{align*}

Theorem 3 (Vandermonde convolution). Let $n\in\mathbb{N}$, $x\in \mathbb{R}$ and $y\in\mathbb{R}$. Then, \begin{align*} \dbinom{x+y}{n}=\sum_{i\in\mathbb{N}}\dbinom{x}{i}\dbinom{y}{n-i}. \end{align*}

Theorem 4 (trinomial revision). Let $n,a,b\in\mathbb{R}$. Then, \begin{align*} \dbinom{n}{a}\dbinom{a}{b}=\dbinom{n}{b}\dbinom{n-b}{a-b}. \end{align*}

Theorem 5 (symmetry of binomial coefficients). Let $n\in\mathbb{N}$ and $k\in\mathbb{R}$. Then, \begin{align*} \dbinom{n}{k}=\dbinom{n}{n-k}. \end{align*}

Theorem 6 (sum of a row of Pascal's triangle). Let $n\in\mathbb{N}$. Then, \begin{align*} \sum_{p=0}^{n}\dbinom{n}{p}=2^{n}. \end{align*}

I omit the proofs of these results, as they are well-known. (For the sake of completeness: Theorems 2, 3, 4, 5 and 6 appear as Proposition 2.6.13, Theorem 2.6.1, Proposition 1.3.35, Theorem 1.3.11 and Corollary 1.3.27 in my Enumerative Combinatorics, 4 May 2021, respectively. It should not be hard to find them in any other text on enumerative combinatorics as well, although possibly with more restrictions on some of the variables.)

We will use a minor variant of Theorem 6:

Lemma 7. Let $q, k \in \mathbb{N}$. Then, \begin{align*} \dbinom{q}{k} \sum_{p=0}^q \dbinom{q-k}{p} = \dbinom{q}{k} 2^{q-k}. \end{align*}

Proof of Lemma 7. If $q < k$, then $\dbinom{q}{k} = 0$ (since $q \in \mathbb{N}$), and therefore both sides of the equality in question equal $0$ (since they both contain a factor of $\dbinom{q}{k}$). Thus, for the rest of this proof, we WLOG assume that we don't have $q < k$. Hence, $q \geq k$ and therefore $q - k \in \mathbb{N}$. Therefore, we have $\dbinom{q-k}{p} = 0$ whenever $p > q-k$. Thus, $\sum_{p=0}^q \dbinom{q-k}{p} \mathrel{\overset{0}{=}} \sum_{p=0}^{q-k} \dbinom{q-k}{p} = 2^{q-k}$ (by Theorem 6, applied to $n = q-k$). Multiplying both sides of this equality by $\dbinom{q}{k}$, we obtain $\dbinom{q}{k} \sum_{p=0}^q \dbinom{q-k}{p} = \dbinom{q}{k} 2^{q-k}$. This proves Lemma 7. $\blacksquare$

Now, we can prove Theorem 1:

Proof of Theorem 1. We have $m \geq k$ and thus $m - k \in \mathbb{N}$.

For each $i\in\mathbb{N}$, we have $2i = i+i$ and therefore \begin{equation} \dbinom{m+1}{2i+1}=\dbinom{m+1}{i+i+1}=\sum_{j=0}^{m}\dbinom{j}{i}\dbinom {m-j}{i} \label{eq.darij1.pf.t1.1} \tag{1} \end{equation} (by Theorem 2, applied to $m$, $i$ and $i$ instead of $n$, $x$ and $y$). Now, \begin{align} & \sum_{i\in\mathbb{N}}\underbrace{\dbinom{m+1}{2i+1}}_{\substack{=\sum \limits_{j=0}^{m}\dbinom{j}{i}\dbinom{m-j}{i}\\\text{(by \eqref{eq.darij1.pf.t1.1})}}}\dbinom{i}{k}=\underbrace{\sum_{i\in\mathbb{N} }\ \ \sum\limits_{j=0}^{m}}_{=\sum\limits_{j=0}^{m}\ \ \sum\limits_{i\in \mathbb{N}}}\ \ \underbrace{\dbinom{j}{i}\dbinom{m-j}{i}}_{=\dbinom{m-j}{i} \dbinom{j}{i}}\dbinom{i}{k}\nonumber\\ & =\sum\limits_{j=0}^{m}\ \ \sum_{i\in\mathbb{N}}\dbinom{m-j}{i} \underbrace{\dbinom{j}{i}\dbinom{i}{k}}_{\substack{=\dbinom{j}{k}\dbinom {j-k}{i-k}\\\text{(by Theorem 4, applied to }j\text{, }i\text{ and }k\\\text{instead of }n\text{, }a\text{ and }b\text{)}}} \\ &=\sum\limits_{j=0} ^{m}\ \ \sum_{i\in\mathbb{N}}\dbinom{m-j}{i}\dbinom{j}{k}\dbinom{j-k} {i-k}\nonumber\\ & \mathrel{\overset{0}{=}} \sum\limits_{j=k}^{m} \ \ \sum_{i\in\mathbb{N}}\dbinom{m-j}{i}\dbinom{j}{k}\dbinom{j-k}{i-k} \label{eq.darij1.pf.t1.2} \tag{2} \end{align} (since each nonnegative integer $j<k$ satisfies $\dbinom{j}{k}=0$ and therefore $\sum_{i\in\mathbb{N}}\dbinom{m-j}{i}\dbinom{j}{k}\dbinom{j-k}{i-k} = \sum_{i\in\mathbb{N}}\dbinom{m-j}{i} 0 \dbinom{j-k}{i-k} = 0$).

However, let $j$ be an integer such that $j\geq k$. Then, $j-k \in \mathbb{N}$ (since $j \geq k$). Furthermore, we have $m-k = \left(m-j\right) + \left(j-k\right)$. Thus, \begin{align} \dbinom{m-k}{j} &= \dbinom{\left( m-j\right) +\left( j-k\right) }{j} \\ &= \sum_{i\in\mathbb{N}}\dbinom{m-j}{i} \underbrace{\dbinom{j-k}{j-i}}_{\substack{ =\dbinom{j-k}{\left( j-k\right) -\left( j-i\right) }\\\text{(by Theorem 5, applied to }j-k\text{ and }j-i\\\text{instead of }n\text{ and }k\\\text{(since }j-k\in\mathbb{N} \text{))}}} \nonumber\\ & \qquad \qquad\left( \text{by Theorem 3, applied to }m-j\text{, }j-k\text{ and }j \text{ instead of }x\text{, }y\text{ and }n \right) \nonumber\\ &= \sum_{i\in\mathbb{N}}\dbinom{m-j}{i} \underbrace{\dbinom{j-k}{\left(j-k\right) - \left(j-i\right)}}_{=\dbinom{j-k}{i-k}} \\ &= \sum_{i\in\mathbb{N}}\dbinom{m-j}{i} \dbinom{j-k}{i-k} . \end{align} Multiplying both sides of this equality by $\dbinom{j}{k}$, we obtain \begin{align} \dbinom{j}{k} \dbinom{m-k}{j} &= \dbinom{j}{k} \sum_{i\in\mathbb{N}}\dbinom{m-j}{i} \dbinom{j-k}{i-k} \\ &= \sum_{i\in\mathbb{N}}\dbinom{m-j}{i} \dbinom{j}{k} \dbinom{j-k}{i-k} . \label{eq.darij1.pf.t1.3} \tag{3} \end{align}

Now, forget that we fixed $j$. We thus have proved \eqref{eq.darij1.pf.t1.3} for each $j \geq k$. Thus, \eqref{eq.darij1.pf.t1.2} becomes \begin{align*} & \sum_{i\in\mathbb{N}}\dbinom{m+1}{2i+1}\dbinom{i}{k}\\ & =\sum\limits_{j=k}^{m}\ \ \underbrace{\sum_{i\in\mathbb{N}} \dbinom{m-j}{i} \dbinom{j}{k} \dbinom{j-k}{i-k}}_{\substack{= \dbinom{j}{k} \dbinom{m-k}{j} \\\text{(by \eqref{eq.darij1.pf.t1.3})}}}=\sum\limits_{j=k}^{m}\dbinom{j} {k}\dbinom{m-k}{j}\\ & =\sum\limits_{j=k}^{m}\underbrace{\dbinom{m-k}{j}\dbinom{j}{k} }_{\substack{=\dbinom{m-k}{k}\dbinom{\left(m-k\right)-k}{j-k}\\ \text{(by Theorem 4, applied to }m-k\text{, }j\text{ and }k\\\text{instead of }n\text{, }a\text{ and }b\text{)}}} = \sum\limits_{j=k}^{m}\dbinom{m-k}{k} \dbinom{\left(m-k\right)-k}{j-k}\\ & =\sum\limits_{p=0}^{m-k}\dbinom{m-k}{k}\dbinom{\left(m-k\right)-k}{p} \qquad\left( \text{here, we have substituted }p\text{ for }j-k\text{ in the sum}\right) \\ &= \dbinom{m-k}{k} \sum_{p=0}^{m-k} \dbinom{\left(m-k\right) - k}{p} \\ & = \dbinom{m-k}{k} 2^{\left(m-k\right)-k} \qquad \qquad \left(\text{by Lemma 7, applied to } q = m-k\right) \\ & = \dbinom{m-k}{k} 2^{m-2k} \qquad \left(\text{since } \left(m-k\right)-k = m-2k\right) . \end{align*} This proves Theorem 1. $\blacksquare$

Answer 3

Here is a different evaluation of the sum by way of enrichment. We seek to show that

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

For the initial analysis note that the first binomial coefficient requires $m\ge 2q$ so that when $k\gt m/2$ which would imply $2q \gt m$ the LHS evaluates to zero, even though the RHS is nonzero when $k\gt m.$ We will therefore restrict to $k\le m/2.$ We get for the LHS

$$\sum_{q\ge 0} {m+1\choose 2q+2k+1} {q+k\choose k} = \sum_{q\ge 0} {m+1\choose m-2k-2q} {q+k\choose k} \\ = [z^{m-2k}] (1+z)^{m+1} \sum_{q\ge 0} z^{2q} {q+k\choose k}.$$

Observe that this coefficient extractor produces a finite sum with no contribution from $2q\gt m-2k.$ Continuing,

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

This is

$$\underset{z}{\mathrm{res}} \; \frac{1}{z^{m-2k+1}} (1+z)^{m-k} \frac{1}{(1-z)^{k+1}} = \underset{z}{\mathrm{res}} \; \frac{z^{k-1}}{z^{m-k}} (1+z)^{m-k} \frac{1}{(1-z)^{k+1}}$$

See how the residue vanishes when $2k\gt m.$ Now put $z/(1+z) = w$ so that $z = w/(1-w)$ and $1/(1-z) = (1-w)/(1-2w)$ and $dz = 1/(1-w)^2 \; dw$ to obtain

$$\underset{w}{\mathrm{res}} \frac{1}{w^{m-k}} \frac{w^{k-1}}{(1-w)^{k-1}} \frac{(1-w)^{k+1}}{(1-2w)^{k+1}} \frac{1}{(1-w)^2} \\ = \underset{w}{\mathrm{res}} \; \frac{1}{w^{m-2k+1}} \frac{1}{(1-2w)^{k+1}}.$$

This is

$$\bbox[5px,border:2px solid #00A000]{ 2^{m-2k} {m-k\choose k}}$$

as claimed.

Answer 4

For a combinatorial proof of $$\sum_{r \ge k} \binom{m+1}{2r+1}\binom{r}{k} = \binom{m-k}{k}2^{m-2k},$$ consider tilings of a $1\times m$ rectangle with red monominoes, blue monominoes, and $k$ red dominoes.

The RHS selects the $k$ positions of the dominoes among the $k+(m-2k)=m-k$ tiles and colors the $m-2k$ monominoes red or blue arbitrarily.

For the LHS, I was thinking about conditioning on the number $r$ of red tiles, but that yields instead $$ \sum_{r\ge k} \binom{m-k}{r}\binom{r}{k}. $$

Does anybody see how to combinatorially obtain the desired LHS by conditioning on some other property of these colored tilings?

Answer 5

Compute the Generating Function $$ \begin{align} \hspace{-1cm}\sum_{i,m}\binom{m}{2i+1}\binom{i}{k}x^m &=\sum_{i,m}\binom{i}{k}\binom{-2i-2}{m-2i-1}(-1)^{m-2i-1}x^{m-2i-1}x^{2i+1}\tag{1a}\\ &=\sum_i\binom{i}{k}\frac{x^{2i+1}}{(1-x)^{2i+2}}\tag{1b}\\ &=\frac1x\left(\frac{x}{1-x}\right)^{2k+2}\sum_i\binom{-k-1}{i-k}(-1)^{i-k}\left(\frac{x}{1-x}\right)^{2(i-k)}\tag{1c}\\ &=\frac1x\left(\frac{x}{1-x}\right)^{2k+2}\left(1-\left(\frac{x}{1-x}\right)^2\right)^{-k-1}\tag{1d}\\ &=\frac{x^{2k+1}}{(1-2x)^{k+1}}\tag{1e} \end{align} $$ Explanation:
$\text{(1a)}$: $\binom{m}{2i+1}=(-1)^{m-2i-1}\binom{-2i-2}{m-2i-1}$ using negative binomial coefficients
$\text{(1b)}$: sum in $m$ (Binomial Theorem)
$\text{(1c)}$: $\binom{i}{k}=(-1)^{i-k}\binom{-k-1}{i-k}$
$\text{(1d)}$: sum in $i$ (Binomial Theorem)
$\text{(1e)}$: simplify

Extract the Coefficients $$ \begin{align} \sum_i\binom{m}{2i+1}\binom{i}{k} &=\left[x^m\right]\frac{x^{2k+1}}{(1-2x)^{k+1}}\tag{2a}\\ &=(-2)^{m-2k-1}\binom{-k-1}{m-2k-1}\tag{2b}\\ &=2^{m-2k-1}\binom{m-k-1}{k}\tag{2c} \end{align} $$ Explanation:
$\text{(2a)}$: the sum is the coefficient of $x^m$
$\text{(2b)}$: compute the coefficient: $\left[x^{m-2k-1}\right](1-2x)^{-k-1}$
$\text{(2c)}$: $(-1)^{m-2k-1}\binom{-k-1}{m-2k-1}=\binom{m-k-1}{m-2k-1}=\binom{m-k-1}{k}$

Apply to the Question

Thus, plugging $m=2n+1$ into $(2)$, we get $$ \sum_i\binom{2n+1}{2i+1}\binom{i}{k}=2^{2n-2k}\binom{2n-k}{k}\tag3 $$