# How to prove that $\binom{n}{2k+1}=\sum_{i=k+1}^{n-k}\binom{i-1}{k}\binom{n-i}{k}$?

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.

## 2 Answers

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.