Prove that in a bit string the string 01 accurs at most one

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

Note: This question is not ansewred in chegg for Discrete Mathematics and its application book. Q:5.3.30

Solution

this is the complete proof to structual indution informatin

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.