Question

using any form of induction, that a binary string begins and ends with the same character iff contains an even number of occurences of substrings from (01,10).

Answer 1

According to induction, it should contain a base and a hypothesis. Here:

• Base: Start with length n=1. A one-digit string contains equal number of substrings 0101 and 1010 (that is, zero) and starts and ends with the same character.
• Induction hypothesis: ∀k<n, a string of length k has an equal number of substrings 1010 and 1010 if and only if it starts and ends with the same character.

• Induction steps: Say s is a string of length n. Now, take cases:

1. If each character of the string is different from the previous character (meaning, s=0101⋯1010 or s=1010⋯0101) then it is easy to show that it starts and ends with the same character if and only if it has the same number of 0101 and 1010.

2. The other case is when s has at least two consecutive 1s or 0s. Now, use Andre's hint to make a new substring s′, by replacing all consecutive 0s with a single 0 and all consecutive 1s 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 a 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 the 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.

(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.)*

*just for small reference.