I've tried to prove that $\binom{n}{2k+1}=\sum_{i=k+1}^{n-k}\binom{i-1}{k}\binom{n-i}{k}$ by using combinatorial proof.
The LHS is the number of binary vectors of size $n$ with $2k+1$ zeros. I can't find an explanation regarding the RHS.

up vote 2 down vote accepted

The righthand side arises by considering the "middle zero" in your vector, and then counting the number of ways the k zeros on the left and k zeros on the right could be distributed.

In particular, the index i is the position of the (k+1)th zero in your vector. Obviously, the soonest this can occur is the (k+1)th position of the vector overall. The latest it can occur is in position n-k, because there must be k zeros to the right of it. This explains the bounds on the sum.

The summand is the number of ways the first k zeros can occur in the vector, given that the (k+1)th is in the ith position, times the number of ways the last k zeros can occur.

Consider a binary vector of size $n$ with $2k+1$ zeroes. The $(k+1)$'th zero can happen anywhere between the $k+1$ and $n-k$ positions, hence the summation.

Let the $k$'th zero be on the $i$'th position. The two factors $\binom{i-1}k$ and $\binom{n-i}k$ respectively denotes how many ways to assign $k$ zeroes before and after the $k$'th zero. The $k$ zeroes before and after the centre zero can be arranged independently, hence the product.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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