<s>[INST] 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. 
 [/INST] 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.
</s>