Pascal’s rule (bit string proof)
We want to show that
To do so, we will show that both sides of the equation are counting the same set of bit strings.
The left-hand side counts the set of strings of bits with s. Suppose we take one of these strings and remove the first bit . There are two cases: either , or .
If , then the new string is bits with ones; there are bit strings of this nature.
If , then the new string is bits with ones, and there are strings of this nature.
Therefore every string counted on the left is covered by one, but not both, of these two cases. If we add the two cases, we find that
|Title||Pascal’s rule (bit string proof)|
|Date of creation||2013-03-22 12:23:03|
|Last modified on||2013-03-22 12:23:03|
|Last modified by||vampyr (22)|