Thread: Prove a property about a bit string

How can I prove that in a bit string, the string 01 occurs at most one more time than the string 10?

I have tried as follows:

Let P(n): 01 occurs at most once more than 10 in an n-bit string.

P(1): 0, 1
P(2): 00, 01, 10, 11
P(3): 000, 001, 010, 011, 100, 101, 110, 111

Assume P(j) for

Consider P(k + 1):

Here I have to somehow show that in the 'worst case' where there already exists one 01 sequence more than 10 that regardless of where this extra bit is added, it will either create a 10 sequence, 00, 11 or 010 where the latter obviously adds both a 10 and 01 sequence to the count and allows the premise to hold true.
How can I show this for an arbitrary k length bit string?

What if there is a string of k bits like this: xxxxx00, which already has one 01 more than 10, and I add the extra bit as such: xxxxx00 -> xxxxx001, i.e. at the end, where the xxxxx part of the bit-string already contains one 01 more than 10. I don't think that it is possible to have this configuration, but how can I prove this?

You need a stronger induction statement. Let #(01, s) denote the number of occurrences of 01 in a string s, and similarly for #(10, s). Then you could use the following.