Assignment 1 has been handed in, containing material from mathematical and complete induction. I was of course hesitant about this assignment, seeing as my track record with proofs hasn't been great, but spending time with the material well in advance of the due date allowed me to put together the pieces, and hopefully do well on the assignment. Question 1 wasn't that difficult, and after looking over the example involving binary trees in class, I thought of some ideas on how come up with the proof for ternary trees involving height and number of nodes as opposed to whether the number of nodes was odd. Question 2 was relatively pain-free, Question 3 is where I hit my biggest obstacle. I knew my formula for the number of 3-subsets in a set of size n+3 was correct, and I was sure I'd have to incorporate the given formula for the number of 2-subsets in a set of size n+2, but it took a bit of trial and error for me to realize what needed to be done (which was adding the equation for number of 3-subsets in set of size n+3 and equation for number of 2-subsets in set of size n+3 together). Once I figured that out, I had to come up with a reason why those equations added together should equal the number of 3-subsets in a set of size (n+1)+3. This is what took the longest. After staring at my scribbled notes for an embarrassing amount of time and drawing several diagrams, the reason finally came to me (the 2-subsets in the set of size n+3, when added to the new element introduced in the set of size (n+1)+3, would become the new 3-subsets, while the 3-subsets in the original set of size n+3 would still remain in the new set). Does that explanation make sense? I sure hope so, otherwise I won't be doing so well. Anyways, with that off my chest, Question 4 was up next. This one took some thinking. After writing down a few random binary strings that began and ended with the same bit, it seemed true that they did contain an even number of occurrences of subsets from {01, 10}. Upon further inspection of the strings I wrote down, I discovered why. How to make a proof that made sense was another story. I remembered the stamp example from class and saw how this proof might have some similarities to that one. The string added to a smaller string to get to the current string had to follow a formula, otherwise there would be another, bigger string that could be used to get to the current string. Using this formula, proving that either 0 or 2 new occurrences of subsets from {01, 10) were added to an already even number of occurrences, resulting in an even number of occurrences, came naturally.
Overall, I think I did a pretty good job with Assignment 1, and it definitely helped reinforce the material involved.
