Continuing the Problem:

To recap:
The strings are now broken into three sections:
The first bit, the inner bits, and the last bit.

Now in order to do this breakup, the length of the string must be at least 3. This gives us a general indication of what base cases we need (so far 0, 1 and 2).

Now given that the string is broken into three pieces, we can consider the relationship between the first bit and the inner bits, and the last bit and the inner bits. What's nice is we know that the first and last bits are the same. If the first bit is 0, so is the last bit, and if the first bit is 1, so is the last bit. Now consider the inner bits. These bits also form a string which we can apply our predicate to.

There are two cases:
a) The inner string has the same first and last bit.
b) The inner string has different first and last bits.

For a) we can apply our predicate. We know that the inner string has 0 or 1 as the first and last bit and also that the inner string has an even number of occurrences of substrings from {01, 10}. If we look at the inner string, we can represent it as follows. 0 - stuff - 0 or 1 - stuff - 1 In order to break it up like this, the length of the string must be at least 4. Therefore our base cases are now: 0, 1, 2 and 3.
Putting the inner string together with the outer bits we have:
(00 - stuff - 00) or (10 - stuff - 01) or (01 - stuff - 10) or (11 - stuff - 11)
Clearly, the number of occurrences of substrings from {01, 10} remains even. We either have even  number + 0 or even number + 2.

For b) we must look for a way to represent the string such that we can apply our predicate to the inner string. The inner string is now either 1 - stuff - 0 or 0 - stuff - 1. Appending the outer bits we have:
(01 - stuff - 00) or (11 - stuff 01) or (00 - stuff - 10) or (10 - stuff - 11)
The trick here is to consider the string as two parts:
ie. for the first string of (01 - stuff - 00)
Look at it like (01 - stuff - 0) + 0
From this representation, we see that there is an inner string with the same first and last bits (0) appended with a 0 to one end. From our predicate and the assumptions in Complete Induction, the inner bit has an even number of occurrences of substrings from {01, 10} and the appending of 0 to the end (which is also a 0) causes no change in the number of occurrences, thus the number remains even.

This representation can be applied to the four cases for part b).

From here you just have to write the proof out formally (including the base cases) and voila. you're done.