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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.