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