I am trying to solve this challenge question, but I cannot seem to figure out how to approach this:
Given $n, k,$ and $i$ positive integers with $1 \leq i \leq k \leq n$, $$\binom{n}{k} = \sum_{j=i}^{n-k+i}\binom{j-1}{i-1}\binom{n-j}{k-i}$$
I figured the LHS count the ways of creating a binary string with $k\ 0$'s and $n – k\ 1$'s, the RHS must partition that in some way, but I don't know how to go from there.
Best Answer
The identity (which was originally in the question) $${n \choose k} = \sum_{j = i}^{n - k + 1} {j - 1 \choose i - 1}{n - j \choose k - i}$$ is not true. You can basically take any values of $n, k,$ and $i$ with $1 \leq i \leq k \leq n$ and see this is not true.
Here is a combinatorial proof of the following identity, which is what I believe what you meant: $${n \choose k} = \sum_{j = i}^{n - k + i} {j - 1 \choose i - 1}{n - j \choose k - i}$$
We will use an argument counting the number of $n$-bit bitstrings with $k$ zeroes, which is clearly ${n \choose k}$. From here, we will number the bits of an $n$-bit bitstring from left to right as $1$ to $n$.
The right-hand side can be interpreted as follows. First choose some random number $1 \leq i \leq k$. Then, to choose a bitstring with $k$ zeroes and $n - k$ ones, choose some bit $j \geq i$ to be a dividing point, and set it to zero. Then, choose $i - 1$ bits of the $j - 1$ bits to the left of the dividing point to be zero, and choose $k - i$ bits to the right of the dividing point to be zero. Note that if we read the bitstring from left to right, the $i$th zero bit will be in the $j$th slot. This is the crucial observation that shows us we have counted every bitstring with $k$ zeroes exactly once. If you want to think in terms of partitioning the bitstrings, the terms of the summation have partitioned these bitstrings into classes where the $i$th zero bit is in the $j$th slot.
Note also that $j$ must be no more than $n - k + i$ (i.e. there must be at least $k - i$ bits to the right of the dividing point), since otherwise it will not be possible to choose $k - i$ bits from the right side of the dividing point to be zeroes. Similar logic shows why $j \geq i$ is also required (because otherwise it will not be possible to select $i - 1$ bits to the left of $j$). In other words, the $i$th zero bit in a bitstring of $k$ zeroes lies between bit $i$ and bit $n - k + i$.
Note also that the condition $i \leq k$ is crucial, because if $i \geq k + 1$, then our procedure will have chosen at least $k$ zero bits to the left of the dividing point, and will have tried to select a negative number of zero bits to the right of the dividing point, which is clearly impossible. We must select a positive number of bits on each side of the dividing point. In other words, there cannot exist an $i$th zero (reading from left to right) in a bitstring with $k$ zeroes unless $i \leq k$.
So this procedure will work for all $1 \leq i \leq k$ as given in the question, and summing over the allowed values of $j$ for any fixed $i$, we get that $${n \choose k} = \sum_{j = i}^{n - k + i} {j - 1 \choose i - 1}{n - j \choose k - i}$$ as desired. $\square$