A combinatorial identity with binomial coefficients and floor function. Show that $$ \sum_{m=0}^{2k+1}{2^{m}\binom{n}{m}\binom{n-m}{\bigl\lfloor \frac{2k+1-m}{2} \bigr\rfloor}}=\binom{2n+1}{2k+1} $$
I tried expending the sum and using induction, but could not complete the induction step; I tried using Pascal's identity to obtain $$ \binom{n-m}{\bigl\lfloor \frac{2k+3-m}{2} \bigr\rfloor}=\binom{n-m+1}{\bigl\lfloor \frac{2k+3-m}{2} \bigr\rfloor}-\binom{n-m}{\bigl\lfloor \frac{2k+1-m}{2} \bigr\rfloor} $$ but couldn't find other identities to complete the induction step. Searching Gould's Combinatorial Identities brought up nothing, though I could easily had missed something useful there.
I'm looking to complete the induction step, but would also like to find an algebraic or a combinatorial proof. I would like to avoid using trigonometric and root functions, but would like to use complex numbers in cartesian form. 
 A: Note: This answer is the result of an analysis of the highly instructive and elegant answer by Marko Riedel. One highlight is  the  useful representation of $\binom{n}{\left\lfloor \frac{q}{2}\right\rfloor}$ which is the introductory part  of   this answer.
We  use the coefficient of  operator  $[z^q]$ to  denote  the coefficient  of   $z^q$ in a series. This way we can write e.g.
\begin{align*}
\binom{n}{q}=[z^q](1+z)^n\tag{1}
\end{align*}
and to ease comparison with Markos answer I will use his notation. 

Preliminary:
The following is valid
  \begin{align*}
\binom{n}{\left\lfloor \frac{q}{2}\right\rfloor}=[z^qw^n]\frac{(1+z)(1+w)^n}{1-wz^2}\tag{2}
\end{align*}
With  $q$ even, $q\rightarrow 2q$  we obtain
  \begin{align*}
[z^{2q}w^n]\frac{(1+z)(1+w)^n}{1-wz^2}&=[w^n](1+w)^n[z^{2q}](1+z)\sum_{j=0}^\infty w^j z^{2j}\tag{3}\\
&=[w^n](1+w)^nw^q\tag{4}\\
&=[w^{n-q}](1+w)^n\tag{5}\\
&=\binom{n}{n-q}=\binom{n}{q}
\end{align*}
  With  $q$ odd, $q\rightarrow 2q+1$  we obtain
  \begin{align*}
[z^{2q+1}w^n]\frac{(1+z)(1+w)^n}{1-wz^2}&=[w^n](1+w)^n[z^{2q+1}](1+z)\sum_{j=0}^\infty w^j z^{2j}\\
&=[w^n](1+w)^nw^q\\
&=[w^{n-q}](1+w)^n\\
&=\binom{n}{n-q}=\binom{n}{q}
\end{align*}

Comment:


*

*Additionally to (1) we use a second variable $z$ which is used as marker to select via $1+z$ even and odd exponent of $w^j$.

*In  (3) we use  the geometric series expansion and the linearity of the coefficient of operator.

*In (4) we select the coefficient of $z^{2q}$ which is $w^q$.

*In (5) we apply the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$.

We now apply (2) to OPs formula and obtain
  \begin{align*}
\sum_{k=0}^{2m+1}&\binom{n}{k}2^k\binom{n-k}{\left\lfloor\frac{2m+1-k}{2}\right\rfloor}\\
&=\sum_{k=0}^n\binom{n}{k}2^k[z^{2m+1-k}w^{n-k}]\frac{(1+z)(1+w)^{n-k}}{1-wz^2}\tag{6}\\
&=[z^{2m+1}](1+z)[w^n]\frac{(1+w)^n}{1-wz^2}\sum_{k=0}^n\binom{n}{k}\left(\frac{2wz}{1+w}\right)^k\tag{7}\\
&=[z^{2m+1}](1+z)[w^n]\frac{(1+w)^n}{1-wz^2}\left(1+\frac{2wz}{1+w}\right)^n\\
&=[z^{2m+1}](1+z)[w^n]\frac{(1+w(1+2z))^n}{1-wz^2}\tag{8}\\
&=[z^{2m+1}](1+z)[w^n]\sum_{q=0}^n\binom{n}{q}w^q(1+2z)^q\sum_{j=0}^\infty w^jz^{2j}\\
&=[z^{2m+1}](1+z)\sum_{q=0}^n\binom{n}{q}[w^{n-q}](1+2z)^q\sum_{j=0}^\infty w^jz^{2j}\\
&=[z^{2m+1}](1+z)\sum_{q=0}^n\binom{n}{q}(1+2z)^q\left(z^2\right)^{n-q}\\
&=[z^{2m+1}](1+z)(1+2z+z^2)^n\\
&=[z^{2m+1}](1+z)^{2n+1}\\
&=\binom{2n+1}{2m+1}
\end{align*}
and the claim follows.

Comment:


*

*In (6) we apply the formula (2) and we change the upper limit of the sum to $n$ without changing anything, since the formula (2) selects the proper range.

*In (7) we collect all factors with exponent $k$.

*In (8) observe the factor $(1+w)^n$ cancels nicely.
A: Here is a combinatorial proof. The right hand side counts the number of ways to choose $2k+1$ elements from a set with $2n+1$ elements. Fix a partition of the latter set into $n+1$ disjoint subsets, namely a singleton and $n$ two-element subsets.
In order to choose such $2k+1$ elements, first we choose the number $m$ of two-element subsets from which we will select exactly one element. Now we choose such subsets, which can be made in $\binom nm$ ways. Finally, from each one of these $m$ subsets we choose exactly one element; this can be made in $2^m$ ways.
It remains to choose the remaining $2k+1-m$ elements among the elements of the singleton and the remaining $n-m$ two-element members of the partition. Because of the previous step, picking an element of one of these two-element subsets forces us to pick the other element as well. Thus, by choosing $\ell$ of these $n-m$ two-element subsets (which can be made in $\binom{n-m}\ell$ ways) we are adding $2\ell$ elements to our $m$ already chosen elements. In other words, at this point we already chose $2\ell+m$ elements.
The important thing to note is that at this point the value of $\ell$ is determined, that is, we cannot "choose" such value. In fact: if $m$ is even, then we necessarily must pick up the element from the singleton subset, and equality $2\ell+m+1=2k+1$ implies $\ell=\frac{2k-m}2=\bigl\lfloor\frac{2k+1-m}2\bigr\rfloor$; if $m$ is odd then we cannot choose the element from the singleton, and in this case $2\ell+m=2k+1$ implies $\ell=\frac{2k+1-m}2=\bigl\lfloor\frac{2k+1-m}2\bigr\rfloor$.
A: Suppose we seek to prove that
$$\sum_{k=0}^{2m+1} {n\choose k} 2^k 
{n-k\choose \lfloor (2m+1-k)/2 \rfloor}
= {2n+1\choose 2m+1}.$$
Observe that from first principles we have that
$${n\choose \lfloor q/2 \rfloor} = {n\choose n-\lfloor q/2 \rfloor} =
\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}}
\\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}}
\left(1+z
+wz^2+wz^3
+w^2z^4+w^2z^5+\cdots\right)
\; dw \; dz.$$
This simplifies to
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}}
\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}}
\left(\frac{1}{1-wz^2}+z\frac{1}{1-wz^2}\right)
\; dw \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{q+1}}
\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}}
\frac{1}{1-wz^2}
\; dw \; dz.$$
This correctly enforces  the range as the reader  is invited to verify
and we may extend $k$ beyond $2m+1,$ getting for the sum
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}}
\\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}}
\frac{1}{1-wz^2}
\sum_{k\ge 0} {n\choose k} 2^k z^k \frac{w^k}{(1+w)^k}
\; dw \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}}
\\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}}
\frac{1}{1-wz^2}
\left(1+\frac{2wz}{1+w}\right)^n
\; dw \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}}
\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w+2wz)^n}{w^{n+1}}
\frac{1}{1-wz^2}
\; dw \; dz.$$
Extracting the inner coefficient now yields
$$\sum_{q=0}^n {n\choose q} (1+2z)^q z^{2n-2q}
= z^{2n} \sum_{q=0}^n {n\choose q} (1+2z)^q z^{-2q}
\\= z^{2n} \left(1+\frac{1+2z}{z^2}\right)^n
= (1+z)^{2n}.$$
We thus get from the outer coefficient
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} 
\frac{(1+z)^{2n+1}}{z^{2m+2}} \; dz$$
which is
$$\bbox[5px,border:2px solid #00A000]{
{2n+1\choose 2m+1}}$$
as claimed. I do believe this is an instructive exercise.
