Continuing the Problem:

For complete induction.

P(n) : Binary string of length n beginning and ending with the same bit has an even number of occurrences of substrings from {01, 10}

If P(a), P(a+1), ... , P(n-1) implies P(n) then for all n in N greater than or equal to a, P(n).

a is a natural number and represents the step after the base case or cases. As of now, a is unknown but when we continue the solution, we will figure it out.

So, next is to reconsider the question in terms of the type of proof. We are allowed to assume P(x) for x less than n, which lends itself to the idea of building the string from the concatenation of smaller strings. This is because adding bits to a string will only increase or leave the same, the number of occurrences of {01, 10}. It will never decrease the number of occurrences. So in an attempt to search for the method of building the string, I listed out the set of strings that satisfy P(n) for n in {0-4}.

0 : {}

1 : {0, 1}

2 : {00. 11}

3 : {000, 010, 111, 101}

4 : {0000, 0100, 0010, 0110, 1001, 1101, 1011, 1111}

So the general idea is to split the string into sections. As a hint, we were told to combine this claim with a similar claim about binary strings that begin and end with different bits. Intuitively, it would seem that a binary string beginning and ending with different bits would have an odd number of occurrences.

Following the hint, I decided to break the string into three sections.

Eg. for 0000 : n = 4

0 - 00 - 0

Section 1 : First bit

Section 2 : Inner bits

Section 3 : Last bit

Now using complete induction, I know that since the inner bits is of length less than n, the inner bits will satisfy P(x); which is nice, but not explicitly useful until we consider the construction of the inner bit as well.