Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Good morning. This is my first question in a StackExchange forum. Let me know if I'm doing anything incorrectly (posting in the wrong forum, etc.).

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

I wish to use structural induction for this proof.

Let Σ* be the set of all strings over the alphabet Σ. Let P(w) be the proposition "in the bit string w, the string 01 occurs at most one more time than the string 10".

Basis step: P(λ), where λ is the empty string, is true, because there are 0 strings 01 and 0 strings 10.

Recursive step: Here, I have to show that, if P(w) is true for some arbitrary w belonging to Σ*, then P(wx) is true, where x belongs to Σ. In other words, wx (the bit string w with one more bit x added to it) also has at most one 01 more than 10.

Suppose that P(w) is true. Then, in the bit string w, the string 01 occurs at most one more time than the string 10.

The bit string w can only end in 0 or in 1. When the bit x (which can be 0 or 1) is added, four possibilities occur:

1) w ends in 1 and x ends in 0. In this case, P(wx) is true, because wx has no extra 01's.

2) w ends in 0 and x ends in 0. In this case, P(wx) is also true.

3) w ends in 1 and x ends in 1. In this case, P(wx) is also true.

4) w ends in 0 and x ends in 1.

We have a problem in the last case, because there is one "01" added. By the inductive hypothesis, if w has at most one extra 01, then the proof would fail.

To complete the proof, I have to show that, if w ends in 0, it cannot have more 01's than 10's.

Here is an informal attempt. I will try to build w adding bits to it, and show that, if it ends with 0, for every 01 there will be a 10:

Suppose w is initially one or more 0's. If I add one or more 1's, then there would be one 01. If I add one 0, there will be one 10 to balance with that 01. If I keep adding 0's, the situation won't change. The only way to add one extra 01 would be to add one or more 1's. If I add one or more 0's to the end, one more 10 will be added and the number of 10's and 01's will be equal again.

By the above reasoning, if w ends in 0 and begins in 0, the number of 10's will always equal the number of 01's.

If w begins in one or more 1's, I can add 0 and apply the same reasoning as above, only that there will be one extra 10.

Is this reasoning consistent? How can I show this formally?

Thank you in advance.

share|improve this question
1  
If w ends in 0 then you must have an equal number of 01s and 10s. You can show this by looking at possibilities 1 and 2. This makes case 4 true, too. (Also, I don't think you deal with going from the empty string to a single-letter string. It is obvious, but your 4 cases assume w is non-empty.) –  mange Jan 5 '12 at 12:06
    
Sorry, not "equal number" but rather "no extra 01s". –  mange Jan 5 '12 at 12:19
1  
Might I suggest an alternate strategy? Show by induction that a bit string beginning in b and ending in b' must contain the sequence bb'. Then use that to show between any two 01 sequences, there must exist a 10 sequence. –  Mike Jan 5 '12 at 13:11
1  
Assuming that the result to be proved is true, it would seem that symmetry would imply that the number of occurrences $N_{01}$ of $01$ and the number of occurrences $N_{10}$ of $10$ must differ by at most $1$: $|N_{01}-N_{10}| \leq 1$. –  Dilip Sarwate Jan 5 '12 at 15:05
    
I have the same question for my homework –  user46253 Oct 27 '12 at 22:32

1 Answer 1

up vote 4 down vote accepted

Lemma 1 $P(w11w) \iff P(w1w)$

Lemma 2 $P(w00w) \iff P(w0w)$

By iterating lemma 1 and 2 it suffices to prove this theorem only for the strings like 01010101, 10101, etc. (where no digit occurs twice in a row). The result is obviously true for these strings.

share|improve this answer
    
Good suggestion. For the strings 0, 1, 01, 10, 010 and 101, 1010, 0101, etc., where no digit occurs twice in a row, if there is 01 more than 10, 1) extra 01 will be in the end of the string, because any 01 inside the string will be followed by 0, and 2) adding one more 01 would produce the sequence 0101, thus adding one more 10. This shows that the number of 01's is at most one more than the number of 10's. Using the 2 lemmas that you suggested, any other combination of bits can be generated, which will also display the same property. Is this enough? Or should I detail it further? –  anonymous Jan 5 '12 at 23:23
    
@user1131904, You can use what Dilip Sarwate said to WLOG assume that w starts with 1. (i.e. P(w) iff P(w*) where w* inverts the bits of w). Then you just have two cases $(10)^r$ and $(10)^r1$ –  user16697 Jan 6 '12 at 10:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.