I was trying to count how many bit sequences with exactly n zeroes and k+1 ones are there.
One obvious reasoning is just by doing $ \binom {k+n+1}{k+1}$, by doing choose.
However, I was told that you could also do it by doing the following summation:
$$\sum^{n}_{i=0}\binom {k+i}{k}$$
If that is true then:
$$\sum^{n}_{i=0}\binom {k+i}{k} = \binom {k+n+1}{k+1}$$
Which after a lot of algebra that I will omit, can be verified by induction! Incredible. However, I am unsure what is the combinatorial reasoning is. Does someone know how to reason it combinatorially to establish the equality? Can you also justify the correctness of your argument?
In fact, I was told that the following is the "correct" reasoning, though I can't make sense of why its correct:
On the other hand, the number of zeroes i to the left of the rightmost one ranges from 0 to n. For a fixed value of i, there are $\binom {k+i}{k}$ possible choices for the sequence of bits before the rightmost one. If we sum over all possible i, we find that the number we want is $\sum^{n}_{i=0} \binom {k+i}{k}$
My main concern is with the summation. I can't understand the interpretation of the summation. Is it summing over disjoint subsets? Or why is it summing things? The only time I have seen sums in counting is when there are disjoint subsets (or with the inclusion-exclusion principle).
Even if you explain me what the interpretation means, I feel it might not be too helpful unless it has an explanation of its correctness.
Please provide as much detail on the combinatoric interpretation of the summation, the part of the question that I am having trouble understanding. Thats I guess what is giving me trouble. I fail to see why that description gives the desired equality.
For example, one aspect that I would liked addressed is, how come is that sum NOT double counting? As i increases, combinations from previous steps are "reconsidered"...or not? It seems to me they are. Then if they are, why is that summation NOT double counting?
BOUNTY
I am not able to put a bounty yet, but the answer that justifies the correctness well enough and convinces me to accept their answer, I will gladly reward you when the times comes.
Take it that if there is no accepted answer, I have not yet had my confusion/doubt clarified.