Discrete Math Bit String proof Prove that in a bit string, the string 0 1 occurs at most one more time than the string 1 0.
SO - I understand that if the string begins with a 0 and ends with a 0 or starts and ends with a 1, there will be an equal number of 01's and 10's. And that if it starts with a 0 but ends with a 1, there will be one more 01 than 10; if it starts with a 1 and ends with a 0, there will be one more 10 than 01.
However, I am not sure how to write up this proof correctly. It may appear on my test, and my professor is a notoriously harsh grader for proof questions, so I would greatly appreciate any help.
 A: The problem with your reasoning is that you haven't really shown why for the same start/end case there will be an equal number and why for the different start/end case there will be one more than the other and any professor would not give full mark for such proof.
You need to show something like, consider any appearance of $01$, find the closest $1$ before it, then there are two cases: 
(1) Such closest $1$ does not exist, this case can happen at most once, where a string of all $0$s are at the beginning of the sequence. 
(2) Such closest $1$ exists, then the next bit to such $1$ must be $0$ otherwise it will contradict the fact the $1$ is closest. Furthermore we can show two $01$s cannot share the same closest $1$ before it as if that is the case then that closest $1$ must appear after one of the $01$. So for any $01$ we can find a unique $10$ to it.
Any case (2) $01$ has a corresponding $10$ while case (1) can happen at most once, hence the result follows.
A: cr001 has given one approach. Another idea is to squash each substring of identical bits to a single bit, so that for instance $0010111001$ is reduced to $010101$. The result is always a string that alternates zeroes and ones and has the same number of $01$ pairs and the same number of $10$ pairs as the original string. It’s very easy to verify that if the bit string is alternating, the number of $01$ pairs and the number of $10$ pairs can differ by at most $1$. As it stands, this argument is a bit informal, though it certainly contains all of the essential ideas. I’ll outline a way to make it more formal.
Suppose that your bit string $\mathbf{b}$ is $b_1b_2\ldots b_n$. Let
$$D=\{k\in[n]:k=1\text{ or }b_k\ne b_{k-1}\}\;.$$
Suppose that $D=\{k_1,\ldots,k_m\}$, where $k_1<\ldots<k_m$.


*

*Show that if $k_i\le\ell<k_{i+1}$, then $b_\ell=b_k$.  

*Show that the bit string $b_{k_1}b_{k_2}\ldots b_{k_m}$ alternates zeroes and ones: it does not contain a substring $00$ or $11$.  

*Show that the bit string $b_{k_1}b_{k_2}\ldots b_{k_m}$ has the same number of $01$ substrings and the same number of $10$ substrings as $\mathbf{b}$.  

*Conclude that the number of $01$ substrings of $\mathbf{b}$ and the number of $10$ substrings of $\mathbf{b}$ differ by at most $1$.


Reducing $\mathbf{b}$ to $b_{k_1}b_{k_2}\ldots b_{k_m}$ is simply squashing each substring of identical bits down to a single bit, the first one in the substring.
Just for fun, here’s a fancier way to do the same thing, using an idea that proves fruitful in a surprising number of settings. Define a relation $\sim$ on $[n]=\{1,2,\ldots,n\}$ as follows: for $k,\ell\in[n]$, $k\sim\ell$ if and only if either 


*

*$k\le\ell$, and $b_i=b_k$ for all $i$ such that $k\le i\le\ell$, or  

*$\ell<k$, and $b_i=b_k$ for all $i$ such that $\ell\le i\le k$.


In other words, $k\sim\ell$ if and only if $b_k$, $b_\ell$, and any bits between them are all equal.


*

*Prove that $\sim$ is an equivalence relation on $[n]$. 


For $k\in[n]$ let $\bar k$ be the $\sim$-equivalence class of $k$.


*

*Show that if $\bar k$ and $\bar\ell$ are distinct equivalence classes, then $k<\ell$ if and only if $i<j$ whenever $i\in\bar k$ and $j\in\bar\ell$.


Suppose that there are $m$ equivalence classes, say $\bar{k}_1,\bar{k}_2,\ldots,\bar{k}_m$, where we may assume that $k_1<k_2<\ldots<k_m$.


*

*Show that the bit string $b_{k_1}b_{k_2}\ldots b_{k_m}$ alternates zeroes and ones: it does not contain a substring $00$ or $11$.  

*Show that the bit string $b_{k_1}b_{k_2}\ldots b_{k_m}$ has the same number of $01$ substrings and the same number of $10$ substrings as $\mathbf{b}$.  

*Conclude that the number of $01$ substrings of $\mathbf{b}$ and the number of $10$ substrings of $\mathbf{b}$ differ by at most $1$.


In this version each equivalence class is a maximal substring of identical bits.
