Recap: Strong Induction

The proof for n>1. P(n): "n has prime factorisation" was unnecessarily (i.e. I could work on it) tough.

- Prime nums (and binary) are the two things that I struggle with the most. I'm going to look over ch1(or 0?) of the textbook for the prime factor def'n and I will work with binary more often in CSC258 (I noticed we will work with 2 complements in this class, too. It's getting better for me).

The proof for n>0 P(n): "Every full binary tree with n nodes has n odd"
- At first I didn't understand why we needed a base case, but this is a strong reminder that I can only use  the IH when the IH prereqs are fulfilled.

The proof for postages (3 stamp, 5 stamp to make everything after 8)
- Once again here I practiced expressing my intuition mathematically when we separate the proof into cases of 8 <= n <= 10 and n > 10. In the second case, I followed the book, creating a variable i = n-3 to show the "loop" that can be formed with induction.
- In class Danny mentioned a MI method for the proof, but I'm thinking it is very similar.

A1Q1: (I liked my sol'n)
- Let n be the height of the ternary tree T.
- I separated the cases into when T's root had one, two, xor three children. The three children's case was analogous to the two children's case. I noted that n = 1 + max(height(left child tree), height(right child tree)). I also noted that 0<height(left child tree)<n since max(height(left child tree)<n and height(left child tree) is each at least 1 so I could do IH. Etc. This was beautiful to me.
- In a more time sensitive environment, however, I would not do a proof by cases and I would just do (assuming we got n = 1 as base case proven):

Label the children/potential children of tree T with TsubL, TsubM, TsubR.
Let Ssube = {t \in {TsubL, TsubM, TsubR}: t exists}.
Then for all (#0) s in Ssube, number of nodes of s <= 3^height(s) - 2 by IH.
Let S' = {t not in S}.
Then for all s' in S', number of nodes of s' = 0
Then the sum of nodes TsubL + sum of nodes TsubM + sum of nodes TsubR + 1 <= 3^height(T) - 2
Etc.

#0: I have come to the conclusion that using words instead of LyX commands will be much clearer... I will use them from now on.