Prove by induction on a string

Question

I want to practice proving the following:

Given a binary string s, I want to prove $s$ has the same number of substrings 01 and 10 $\iff$ the first and last character of $s$ is the same.

For example: let$s= 010$, number of substring 01 is 1, the same as number of substring 0. And $s$ starts and ends with the same character $0$.

Another example: let $s=1001010$, number of substring 10 is : 3, number of substring 01 is: 2. Yet notice that s start with different characters.

I want to prove it using induction but I get stuck. I have the two base cases:

$1$ contains no substring 10 or 01. So the number of 01's and 10's are the same.

Also, $0$ contains no substring 10 or 01. So the number of 01's and 10's are the same.

I am not sure about the induction hypothesis and how to proceed in this case. I would appreciate if you can help!

Answer 1

You could use induction on the length of the string.

Base: Start with length $n=1$. A one-digit string contains equal number of substrings $01$ and $10$ (that is, zero) and starts and ends with the same character.

Induction hypothesis: $\forall k< n$, a sting of length $k$ has equal number of substrings $10$ and $10$ if and only if it starts and ends with the same character.

Induction step: Say $s$ is a string of length $n$. Now, take cases:

• If each character of the string is different from the previous character (meaning, $s=0101\cdots1010$ or $s=1010\cdots0101$) then it is easy to show that it starts and ends with the same character if and only if it has same number of $01$ and $10$.

• The other case is when $s$ has at least two consecutive $1$s or $0$s. Now, use Andre's hint to make a new substring $s'$, by replacing all consecutive $0$s with a single $0$ and all consecutive $1$s with a single $1$.

  Notice that the number of substrings $01$ in $s'$ is the same as in $s$ and the number of $10$ in $s'$ is the same as in $s$. So, $s$ and $s'$ have the same number of substrings $01$ and $10$. Also, notice that the first character of $s$ is the same as of $s'$ and also the last character of $s$ is the same as of $s'$.

  But $s'$ has length less than $n$, so you can use the induction hypothesis and say that $s'$ starts and ends with the same character if and only if it has same number of substrings $01$ and $10$. But because of the similarities you have noticed between $s$ and $s'$, you can prove that the same holds for $s$, too.

Answer 2

Hint: Replace any string of consecutive $0$'s with a single $0$, and any string of consecutive $1$'s with a single $1$. That does not affect the number of substrings of type $01$ or $10$.