How to prove this (seemingly elusive) double binomial identity? 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.
 A: 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$
A: 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$.
A: 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
$$
A: 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.
A: 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?
