Prove using combinatorics $\sum\limits_{k=0}^n 2^k \binom{n}{k} \binom{n-k}{\lfloor{\frac{n-k}{2}}\rfloor}=\binom{2n+1}{n}$ Prove using combinatorics 
$$\sum\limits_{k=0}^n 2^k \binom{n}{k} \binom{n-k}{\lfloor{\frac{n-k}{2}}\rfloor}=\binom{2n+1}{n}$$
The right side seems easy for the right side we have floor function it seems we have to count the number of subsets that $A_i \notin A_j$ but when I try to prove I can't show the right side.Any hints?
 A: Here is a combinatorially based approach.

RHS: The right hand side $$\binom{2n+1}{n}$$ is the number of $n$-element subsets of a set with $2n+1$ elements.
LHS: We partition the $2n+1$ elements in $n$ pairs and one singleton and count the number of ways to select $n$ elements from the total of $2n+1$ elements by classifying the pairs in two categories.
  
  
*
  
*pairs from which we take one element only
  
*pairs from which we take both elements
Let $0\leq k\leq n$. If we select $k$ pairs from which take one element only, there are $\binom{n}{k}$ different possibilities to do so and since for each pair of this category there are two choices to select an element, we get
  \begin{align*}
2^k\binom{n}{k}
\end{align*}
  different possibilities to select $k$ elements from pairs of the first category.
We now have to select $n-k$ elements from pairs of the second category and according to the classification of this category, we have to choose both elements of each pair. So, we have $\lfloor (n-k)/2\rfloor$ pairs of this category to select which can be done in
  \begin{align*}
\binom{n-k}{\lfloor (n-k)/2\rfloor}
\end{align*}
  ways. Observe that if $n-k$ is even, we won't take the singleton and if $n-k$ is odd we have to take the singleton in order to get $n$ elements.

Note: This proof is a special case of this answer.
