Prove that $\sum_{k=0}^{n} 2^{k} {n \choose k}{n-k \choose \lfloor{\frac{n-k}{2}}\rfloor} = {2n+1 \choose n}$ The problem is the following: prove that $\sum_{k=0}^{n} 2^{k} {n \choose k}{n-k \choose \lfloor{\frac{n-k}{2}}\rfloor} = {2n+1 \choose n}$
I was trying to prove some concrete combinatorial examples to make the LHS equivalent to $2n+1 \choose n$. 
We choose $k$ in the first $n$ items, but I am not sure how to map $2^{k} {n-k \choose \lfloor{\frac{n-k}{2}}\rfloor}$ to choosing $n-k$ elements from $n+1$ items 
[EDIT] This might help. Combinatorial proof $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$
 A: We start with
$$\sum_{k=0}^n 2^k {n\choose k}
{n-k\choose \lfloor \frac{n-k}{2} \rfloor}
= \sum_{k=0}^n 2^{n-k} {n\choose k}
{k\choose \lfloor k/2 \rfloor}
\\ =
\sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k} {n\choose 2k}
{2k\choose k}
+ \sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1} {n\choose 2k+1}
{2k+1\choose k}.$$
Now for the first sum we write
$${n\choose 2k} {2k\choose k} =
\frac{n!}{(n-2k)! \times k! \times k!} =
{n\choose k} {n-k\choose n-2k}.$$
We obtain
$$\sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k}
{n\choose k} {n-k\choose n-2k}
\\ = \sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k}
{n\choose k} [z^{n-2k}] (1+z)^{n-k}
\\ = [z^n] (1+z)^n \sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k}
{n\choose k} z^{2k} (1+z)^{-k}.$$
Now  the coefficient  extractor enforces  the  sum limits  and we  may
continue with
$$2^n [z^n] (1+z)^n \sum_{k\ge 0} 2^{-2k}
{n\choose k} z^{2k} (1+z)^{-k}
\\ = 2^n [z^n] (1+z)^n \left(1+\frac{z^2}{4(1+z)}\right)^n
\\ = \frac{1}{2^n} [z^n] (z+2)^{2n}
= \frac{1}{2^n} {2n\choose n} 2^n = {2n\choose n}.$$
For the second sum we write
$${n\choose 2k+1} {2k+1\choose k} =
\frac{n!}{(n-2k-1)! \times k! \times (k+1)!} =
{n\choose k} {n-k\choose n-2k-1}.$$
We obtain
$$\sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1}
{n\choose k} {n-k\choose n-2k-1}
\\ = \sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1}
{n\choose k} [z^{n-2k-1}] (1+z)^{n-k}
\\ = [z^{n-1}] (1+z)^n \sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1}
{n\choose k} z^{2k} (1+z)^{-k}.$$
Once more the coefficient extractor enforces the sum limits and we may
continue with
$$2^{n-1} [z^{n-1}] (1+z)^n \sum_{k\ge 0} 2^{-2k}
{n\choose k} z^{2k} (1+z)^{-k}
\\ = 2^{n-1} [z^{n-1}] (1+z)^n \left(1+\frac{z^2}{4(1+z)}\right)^n
\\ = \frac{1}{2^{n+1}} [z^{n-1}] (z+2)^{2n}
= \frac{1}{2^{n+1}} {2n\choose n-1} 2^{n+1} = {2n\choose n-1}.$$
Collecting everything we find
$$\bbox[5px,border:2px solid #00A000]{
{2n\choose n} + {2n\choose n-1} = {2n+1\choose n}.}$$
