I have to use induction to prove that for any finite bitstring $s$, if $s$ ends in a $1$, then $01$ occurs at most one more time than $10$. Induct on the length of $s$.
I really can't solve this problem and I'm even having problems starting it. I don't really know what the basis/inductive steps would be for the length of $s$.
On
HINT
Given as in a bit string you can never get two successive $01$'s without there being some $10$ in between, the claim should indeed hold ... and we really don't need induction to see this. But, you have to use induction, so be it.
Still, if you set up an inductive proof, and just focus on how many more $01$'s there are than $10$'s, you could quickly get into trouble ... the key is really that the $01$ and the $10$'s have to alternate.
So, one idea is to prove a somewhat stronger claim, namely that for any string that ends in a $1$ and starts with a $1$ the number of $01$'s should exactly equal the number of $10$'s while if it ends in a $1$ but starts with a $0$, you have exactly one more $01$.
That claim is easily proven by induction:
Base: $s=1$. We have an equal number (namely $0$) of $01$'s as $10$'s. Check!
Step: Suppose the claims is true ofor strings of length $k$.
Now take a string of length $k+1$. There are two cases:
Now, if $S'$ also start with a $1$, then by inductive hypothesis there are just as many $01$'s as $10$ in $s'$, and clearly that means the same is true for $s$. Check!
If $s'$ starts with a $0$, then by inductive hypothesis $s'$ contains one more $01$'s than $10$'s, but $s$ now has an extra $10$, so the number of $10$'s and $01$'s for $s$ are the same. Check!
Now, if $s'$ starts with a $1$, then by inductive hypothesis there are just as many $01$'s as $10$ in $s'$, but $s$ now has an extra $10$, and so $s$ contains one more of $01$'s than $10$'s. Check!
If $s'$ starts with a $0$, then by inductive hypothesis $s'$ contains one more $01$'s than $10$'s, and so the same is true for $s$. Check!
Finally, all we have to do is that the claim you were asked to prove immediately follows from the stronger claim just proven.
Base step:
The only string of length $1$ ending in a $1$ is precisely $1$ which has exactly zero occurrences of both $01$ and $10$.
Inductive step:
Assume that there exists $n \in \mathbb{N}$ such that for all strings of length $\le n$ holds that they have at most one $01$ more than $10$.
Let $s = \underbrace{\cdots\cdots}_{n}1$ be a string of length $n+1$ ending in a $1$.
If the second-to-last digit is $1$, then it looks like this:
$$\underbrace{\cdots\cdots}_{n-1}11$$
Using the inductive assumption for $n-1$, the first $n-1$ bits in $s$ have at most one $01$ more than $10$. The last two bits also have no $01$ or $10$ substrings, so the statement holds for $s$.
If the $1$ at the end is preceded by $k < n$ zeroes, then $s$ looks like this:
$$\underbrace{\cdots\cdots}_{n-k-1}1\,\underbrace{00\cdots00}_{k}\,1$$
Using the inductive assumption for the first $n-k-1$ bits of $s$, there is at most one more $01$ than $10$ in the first $n-k-1$ bits of $s$. There is exactly one more $10$ and $01$ in the remaining $k+2$ bits of $s$, so the statement holds for $s$.
Finally, if $s$ contains only zeroes except the $1$ at the end, then it contains exactly one $01$ and no $10$ substrings, so the statement again holds.
This completes the proof.