# Prove a property about a bit string

Printable View

• Mar 29th 2011, 07:56 PM
posix_memalign
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 $1 \leq j \leq k$

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?
• Mar 30th 2011, 12:07 AM
emakarov
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.

$\begin{array}{c|c}
\mbox{If s has the shape} & \mbox{then \#(01,s)-\#(10,s) is}\\
\hline
0\dots0 & 0\\
0\dots1 & 1\\
1\dots0 & \llap{-}1\\
1\dots1 & 0
\end{array}$