# Number of possible intervals of consecutive binary values

In a string like "00110101010000111001111011111000" I'm reliably informed that the number of intervals containing consecutive zeros and consecutive ones can only differ by 1. It kind of makes sense, but I'm having trouble seeing why it is true.

Can anyone please provide a proof?

This is what I've got so far:

Suppose we start with 0. Then either the string ends before a 1 is reached and the conditions holds, or a new interval begins consisting of ones. Either this new interval consisting of ones is the final interval, so the condition holds, or there is a new interval consisting of zeros...

Is this just ridiculously simple or do I need to use some tool like proof by induction?

You are correct. An easier way to see this is by concatenating groups of $$0$$s as $$A$$ and concatenating groups of $$1$$ as $$B$$.

Now, all binary strings can be simplified and written like this

$$ABABAB...$$

Can you see why the condition holds?

• That certainly helps. It gave me this: Starts with A, ends with A: |A| = |B| + 1 Starts with A, ends with B: |A| = |B| Starts with B, ends with A: |A| = |B| Starts with B, ends with B: |A| = |B| - 1 Is that a proof though? I think almost but not quite. What else does it need? – Robin Andrews Apr 9 at 17:13
• That proof is correct – h-squared Apr 9 at 17:54