Prove that in a bit string the strings 01 happens at most on

Prove that in a bit string, the strings 01 happens at most one more time than the string 10

Solution

since we are concerned only with substrings 01 and 10 all we care about are the changes from 0 to 1 or 1 to 0 as we move from left to right through the string.

For example we view 0011110110100 as a block of 0\'s followed by a block of 1\'s,followed by a block of 0\'s, followed by a block of 1\'s,followed by a block of 0\'s,followed by a block of 1\'s,followed by a block of 0\'s.There is one occurence of 01 or 10 at the start of each block other than the first,and the occurences alternate between 01 and 10.If the string has a odd number of blocks(or the string is empty),then there will be an equal number of 01\'s and 10\'s.If the string has an even number of blocks then the string will have one more 01 than 10 if the first block is 0\'s and one more 10 than 01 if thefirst block is 1\'s.