Finally! My first SLOG update!

After a long and busy week, finally, my SLOG is here live! Assignment #1 of CSC236 was extremely hard, which is mainly because I was trying to "prove" or "explain" everything instead of writing down a clear and easy understanding idea. Already, jump right into the topic: such as question 4 on the assignment, " use complete or mathematical induction  to prove that any binary string that begin and ends with the same bit has an even number of occurrences of substring from {01, 10}."

Prof Heap has mentioned that he prefer mathematical induction in class, so I tried to think in that direction, and then came up with the following:

P(n): any binary string n, if its first digit n[0] is same as the last digit n[-1], then it has even number of occurrence of {01, 10}. (IH)

Proof (by Complete Induction)

Special Case (Base case): When len(n) = 0, then length of the binary string n is 1, which implies that n is a single-digit string {0, 1}. Since a single-digit string can never include {01, 10}, so that the occurrence of {01, 10} is 0, which is even.

E.g. S = 1 or S = 0.

Induction Step: Assume len(n) > 0, and that for every natural number 0 < j < len(n) then (n[:j]) is true.

Case 1: n[0] = 1 and n > 0: then n[0] and n(1) both {0, 1}.

Subcase 1.1: n[0] = n[1] then since n[0]= 1 (mentioned in Case 1), then n[1] = n[0] = 1, which gives the first 2 digits of n is “11” that ∉ {01, 10}, so the first two digits of the binary string n contains 0 of {01, 10}. And we slice n = n[1:] , then move onto the next digit

Subcase 1.2: n[0] ≠ n[1] then since n[0]= 1 (mentioned in Case 1), then n[0] ≠ n[1] = 0, which gives the first 2 digits of n is “10” that {01, 10}. so the first two digits of the binary string n contains 1 of {01, 10}. And we slice n again so that n = n[1:] , then move onto the next digit

Case 2: n[0] = 0 and n > 0: then n[0] and n(1) both {0, 1}.

Subcase 2.1: n[0] = n[1] then since n[0]= 0 (mentioned in Case 1), then n[1] = n[0] = 0, which gives the first 2 digits of n is “00” that ∉ {01, 10}, so the first two digits of the binary string n contains 0 of {01, 10}. And we slice n = n[1:], then move onto the next digit

Subcase 2.2: n[0] ≠ n[1] then since n[0]= 1 (mentioned in Case 1), then n[0] ≠ n[1] = 1, which gives the first 2 digits of n is “01” that {01, 10}. So the first two digits of the binary string n contains 1 of {01, 10}. And we slice n again so that n = n[1:] , then move onto the next digit

    Since binary string n contains 1 of {01, 10} every time there is a different digit in the string, and I assume P(n), which means n[0] = n[-1], and it has to have ∃x ℕ, there are 2x times of occurrence of digit that is not the same as n[0]. In addition, if n[0] = n[1] = n[2] = ··· = n[-1], there will be 0x times of occurrence of digit that is not the same as n[0]. Which 2x and 0x are both even numbers. I conclude that for all non-empty binary string n, P(n).

And as you can see, I used the complete induction instead, which result in having a loop case in the proof! I wish I can find out where it went wrong.