How can I prove, that this formula is related to the binomial series? I am trying to solve the following formula:
$$\sum^{\lfloor (n-1)/2\rfloor}_{m=k}\binom{m}{k}\binom{n}{2m+1} = \binom{n-k-1}{k}2^{n-2k-1}$$
However, I haven't got a clue. Can anybody shed some light on this?
 A: We seek to verify for $n-k-1\ge k$ the identity
$$\sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\choose k} {n\choose 2m+1}
= {n-k-1\choose k} 2^{n-2k-1}.$$
The LHS is
$$\sum_{m=k}^{\lfloor (n-1)/2 \rfloor}
{m\choose k} {n\choose n-2m-1}
= \sum_{m=k}^{\lfloor (n-1)/2 \rfloor}
{m\choose k} [z^{n-2m-1}] (1+z)^n
\\ = \sum_{m=k}^{\lfloor (n-1)/2 \rfloor}
{m\choose k} [z^{n}] z^{2m+1} (1+z)^n.$$
Now observe  that when $2m+1\gt  n$ we  get zero from  the coefficient
extractor so  in fact  it encodes  the upper  limit of  the summation,
which we  may extend to infinity  since there is no  contribution from
those values of $m$. We obtain
$$[z^n] (1+z)^n \sum_{m\ge k}
{m\choose k}  z^{2m+1}
= [z^{n-1}] (1+z)^n \sum_{m\ge k}
{m\choose k}  z^{2m}
\\ = [z^{n-1}] (1+z)^n \sum_{m\ge 0}
{m+k\choose k}  z^{2m+2k}
= [z^{n-2k-1}] (1+z)^n \sum_{m\ge 0}
{m+k\choose k}  z^{2m}
\\ = [z^{n-2k-1}] (1+z)^n \frac{1}{(1-z^2)^{k+1}}
= [z^{n-2k-1}] (1+z)^{n-k-1} \frac{1}{(1-z)^{k+1}}.$$
Extracting the coefficient we find
$$\sum_{q=0}^{n-2k-1} {n-k-1\choose q}
{n-2k-1-q+k\choose k}
\\ = \sum_{q=0}^{n-2k-1} {n-k-1\choose q}
{n-k-1-q\choose k}.$$
The product of binomials is
$$\frac{(n-k-1)!}{q! \times k! \times (n-2k-1-q)!}
= {n-k-1\choose k} {n-2k-1\choose q}$$
and we get
$${n-k-1\choose k} \sum_{q=0}^{n-2k-1} {n-2k-1\choose q}
= {n-k-1\choose k} 2^{n-2k-1}$$
as claimed.
A: Here is variation of the theme. It is convenient  to use the coefficient of operator  $[z^n]$ to  denote the coefficient of  $z^n$  in  a series. This way we can write for instance
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}

We obtain for $n\geq 2k+1$:
  \begin{align*}
\color{blue}{\sum_{m=k}^{\left\lfloor\frac{n-1}{2}\right\rfloor}}&\color{blue}{\binom{m}{k}\binom{n}{2m+1}}\\
&=\sum_{m=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{m+k}{m}\binom{n}{2m+2k+1}\tag{1}\\
&=\sum_{m=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{-k-1}{m}(-1)^m\binom{n}{n-2m-2k-1}\tag{2}\\
&=\sum_{m=0}^\infty[z^m](1-z)^{-k-1}[u^{n-2m-2k-1}](1+u)^n\tag{3}\\
&=[u^{n-2k-1}](1+u)^n\sum_{m=0}^\infty u^{2m}[z^m](1-z)^{-k-1}\tag{4}\\
&=[u^{n-2k-1}](1+u)^n\left(1-u^2\right)^{-k-1}\tag{5}\\
&=[u^{n-2k-1}](1+u)^{n-k-1}(1-u)^{-k-1}\tag{6}\\
&=\sum_{j=0}^{n-2k-1}\binom{n-k-1}{j}\binom{-k-1}{n-2k-1-j}(-1)^{n-2k-1-j}\tag{7}\\
&\color{blue}{=\sum_{j=0}^{n-2k-1}\binom{n-k-1}{j}\binom{n-k-j-1}{k}}\tag{8}\\
&=\sum_{j=0}^{\infty}[u^j](1+u)^{n-k-1}[z^k](1+z)^{n-k-j-1}\tag{9}\\
&=[z^k](1+z)^{n-k-1}\sum_{j=0}^\infty (1+z)^{-j}[u^j](1+u)^{n-k-1}\tag{10}\\
&=[z^k](1+z)^{n-k-1}\left(1+\frac{1}{1+z}\right)^{n-k-1}\tag{11}\\
&=[z^k](2+z)^{n-k-1}\tag{12}\\
&\color{blue}{=\binom{n-k-1}{k}2^{n-2k-1}}\tag{13}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we shift the index $j$ to start from $j=0$.

*In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ and $\binom{p}{q}=\binom{p}{p-q}$.

*In (3) we apply the coefficient of operator twice and also set the upper bound to $\infty$ without changing anything since we are adding zeros only.

*In (4) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (5) we apply the substitution rule of the coefficient of operator with $z=u^2$
\begin{align*}
A(u)=\sum_{m=0}^\infty a_m u^m=\sum_{m=0}^\infty u^m [z^m]A(z)
\end{align*}

*In (6) we rearrange the terms in order to derive another binomial identity from (1) in the next step.

*In (7) we extract the coefficient of $[u^{n-2k-1}]$.

*In (8) we apply the same identity as in (2).

*In (9) we apply the coeffcient of operator twice again.

*In (10) we do a rearrangement similarly as in (4).

*In (11) we apply the substitution rule as we did in (5).

*In (12) we do some simplifications.

*In (13) we select the coefficient of $[z^k]$.

Notes: Two steps might be of special interest.
  
  
*
  
*(5) to (6): This is the essential twist to derive another binomial identity (8) from (1) which also enables us to finally derive the RHS of OP's claim.
  
*(11): The transformation
  \begin{align*}
(2+z)^N=\left(1+\frac{1}{1+z}\right)^N(1+z)^N
\end{align*}
  may be helpful sometimes to get rid of the summand $2$.

