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$
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}.}$$