week.two

note to self: problem set due this week =|.

on monday, we advanced on a more intermediate level of proving - complete induction =O. i don't recall doing this type of induction in 165, but i do remember it at one point in mat137, and i was late for that class - so i really don't get the steps on how to go about doing that, really hoping 236 would "open my eyes". one proof done in class was on prime factorization, and the proof involved proving by cases - rare to have two kinds of proofs in one, but evidently it is doable. we touched a little bit on trees - nodes, edges, zero tree, parent/child, siblings, etc.

on wednesday, we continued on with a claim that is easier proven by complete induction as opposed to simple induction - the full binary tree. The claim to be proven is: if a FBT has n >= 1, then n is odd. the problem that occurs with simple induction when proving FBT is: if a FBT has n nodes and n is odd => then there will be no FBT with n+1 nodes. inside the proof, P(1) was set to be true (by base case) and from P(1), we went on to proving P(n) for all n > 1 (i.e.: k \in {2, 3, ..., k-1}). in the end, we concluded for a FBT T with n nodes has: 1 + n_L + n_R (which yields an odd number). i've never been a big fan of trees in particular because of their recursive nature. i find that proving that a certain claim is true about, in this case, a full binary tree becomes a bit cumbersome after a while into the induction step. i'm hoping we won't be seeing too many of these in the tests/exam.

on friday, we proved another claim with complete induction - P(n): postage of n cents can be formed with 4- and 5-cent stamps. This predicate only holds true for all n > k, where k = 11. the proof is divided into two cases. the first case proves P(n) for 12 =<>= 16. in the end, \forall n in N-{0, ..., 11}, P(12) \and ... \and P(n - 1) \implies P(n). i found this proof to be reasonably challenging, yet doable. perhaps this proof is the one that got me thinking what complete induction really is.