Another combinatorial identity involving product of binomial coefficients While answering a question I came in a side calculation across the following identity valid by numerical evidence for integer $m$ and $n$:
$$
\sum_{k=m}^{\left\lfloor\frac n2\right\rfloor} \binom km\binom n{2k}=\frac{n(n-m-1)!}{m!(n-2m)!}2^{n-2m-1}.
$$
I would appreciate any hints and suggestions on combinatorial as well as algebraic proofs of the identity.
 A: Here is an algebraic proof. With $n\ge 2m$ we claim that
$$\sum_{k=m}^{\lfloor n/2 \rfloor}
{n\choose 2k} {k\choose m} =
\frac{n}{m} {n-m-1\choose m-1} 2^{n-2m-1}.$$
The LHS is
$$\sum_{k=m}^{\lfloor n/2 \rfloor}
{k\choose m} {n\choose n-2k}
= [z^n] (1+z)^n \sum_{k=m}^{\lfloor n/2 \rfloor}
{k\choose m} z^{2k}.$$
The coefficient extractor enforces the upper limit and we get
$$[z^n] (1+z)^n \sum_{k\ge m}
{k\choose m} z^{2k}
= [z^n] (1+z)^n z^{2m} \sum_{k\ge 0}
{k+m\choose m} z^{2k}
\\ = [z^{n-2m}] (1+z)^n \frac{1}{(1-z^2)^{m+1}}
= [z^{n-2m}] (1+z)^{n-m-1} \frac{1}{(1-z)^{m+1}}
\\ = \sum_{q=0}^{n-2m} {n-m-1\choose q}
{n-m-q\choose m}.$$
Now we have
$${n-m-1\choose q} {n-m-q\choose m}
= \frac{n-m-q}{m}  {n-m-1\choose q} {n-m-1-q\choose m-1}
\\ = \frac{n-m-q}{m}
\frac{(n-m-1)!}{q! \times (m-1)! \times (n-2m-q)!}
\\ = \frac{n-m-q}{m}
{n-m-1\choose m-1} {n-2m\choose q}.$$
We get for our sum
$$\frac{1}{m} {n-m-1\choose m-1}
\sum_{q=0}^{n-2m}
(n-m-q) {n-2m\choose q}
\\ = \frac{1}{m} {n-m-1\choose m-1}
\sum_{q=0}^{n-2m}
(m+q) {n-2m\choose q}.$$
For the sum without the scalar we obtain
$$m 2^{n-2m} + \sum_{q=1}^{n-2m}
q {n-2m\choose q}
= m 2^{n-2m} + (n-2m) \sum_{q=1}^{n-2m}
{n-2m-1\choose q-1}
\\ =  m 2^{n-2m} + (n-2m) 2^{n-2m-1}
= n 2^{n-2m-1}.$$
Collecting everything we find
$$\bbox[5px,border:2px solid #00A000]{
\frac{n}{m} {n-m-1\choose m-1} 2^{n-2m-1}.}$$
as claimed.
