Question

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

Short answer

The string 01 occurs at most one time than the string 10.

Step-by-step solution

The mathematical induction:

Proof by Induction:

Let P(n) be the statement “The string 01 occurs at most one time than the string 10 in a string with n bits and ending in 0 while the string 10 occurs at most the same number of times than the string 10 and ending in 1.

To prove that the string 01 occurs at most one more time than the string 10.

Inductive step:

Let P(k) be true.

We need to prove that P(k+1) is true.

Let a be string with k+1 bits.

If the last digit is a 0 and the remaining string is ${\mathrm{a}}_1$, then ${\mathrm{a}}_1$contains 01 at most one more time than 10.

Since, the last digit is a 0, it is not possible to add an additional 01 but it is possible to add an additional 10 in .Thus a contains 01 at most one more time than 10.

If the string ends with 1 and the remaining string is ${\mathrm{a}}_2$, then ${\mathrm{a}}_2$contains 01 at most the same number of time than 10.

Since, the string end with a 1, at most one block 01 can be added. Thus a contains 01 at most one more time than 10.

Hence, P(k+1) is true.

Thus, P(n) is true for all positive integers n by the method of principal induction.