# 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?

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.

• What a about a combinatorial proof? – Taha Akbari Apr 10 '17 at 16:37
• @TahaAkbari: Proof transformed into a combinatorial one. – Markus Scheuer Apr 12 '17 at 20:53