1. ## A binomial identity

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

$\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, $\binom{2n+1}{n}$ is the number of $n$-element subsets of a $(2n+1)$-element set, or the number of ways we can select $n$ different balls from a box containing $(2n+1)$ balls...

The left side doesn't seem so straightforward. Let's say we have an $n$-element set, and we wish to find the number of ways we can form a $k$-element subset, where $k=0,1,...n$, and the number of ways we can pick a subset of that newly-formed $k$-element set.
As a $k$-element set has $2^k$ subsets, we can do this procedure in $2^k \cdot \binom{n}{k}$ ways, for some $k$.
But the next factor, $\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 $\binom{2n+1}{n}$.

Start by selecting k pairs to choose one element from. There are $\textstyle2^k\binom nk$ ways of doing this ( $\textstyle\binom nk$ ways of choosing which pairs, and 2 ways of choosing which element in each pair). To bring the total number of selected elements up to n, we then need to select both elements from exactly half of the remaining n-k pairs, if n-k is even. If n-k is odd then we have to select both elements from $\lfloor \tfrac{n-k}{2} \rfloor$ of them, together with the single element of S. In either case, there are $\binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}$ ways of doing this.
That shows that $\sum_{k=0}^{n} 2^k \binom{n}{k} \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}=\binom{2n+1}{n}$.