I'm trying to give a combinatorial proof of the following identity:

$\displaystyle \sum_{k=0}^{n} 2^k \binom{n}{k} \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}=\binom{2n+1}{n}$

***

On the right side, $\displaystyle \binom{2n+1}{n}$ is the number of $\displaystyle n$-element subsets of a $\displaystyle (2n+1)$-element set, or the number of ways we can select $\displaystyle n$ different balls from a box containing $\displaystyle (2n+1)$ balls...

The left side doesn't seem so straightforward. Let's say we have an $\displaystyle n$-element set, and we wish to find the number of ways we can form a $\displaystyle k$-element subset, where $\displaystyle k=0,1,...n$, and the number of ways we can pick a subset of that newly-formed $\displaystyle k$-element set.

As a $\displaystyle k$-element set has $\displaystyle 2^k$ subsets, we can do this procedure in $\displaystyle 2^k \cdot \binom{n}{k}$ ways, for some $\displaystyle k$.

But the next factor, $\displaystyle \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}$ is totally baffling. I'm not even sure that the above interpretation is correct. And the next problem would be to show that the whole left side of the problem, in fact, equals $\displaystyle \binom{2n+1}{n}$.

Many thanks in advance!