reminder: a1 is due on monday!
on monday, i came in a bit late...haha. i think i'm picking up my first-year habits all over again. i wasn't too sure about the predicate to be proven, in particular what the game round-robin is. but, in a nutshell: p_1 > p_2 > p_3 > p_1 (back to p_1; 3 cycles). another valuable info about the three types induction is that each implies the next in a circular pattern of implication - i.e.: principle of well-ordering => principle of simple induction => principle of complete induction => principle of well-ordering. consequently, is the converse true? yes. i.e.: PWO <=> PSI <=> PCI <=> PWO. this chain of iff equality was a little unclear to me, and is still blurry to me. i hope by reading the text on this topic more than once will somehow explain itself to me.
on wednesday, we discussed the topic "bases larger than zero". in particular, we proved the predicate P(n): 2^n > 10^n. after working through some possible base cases, we concluded that this predicate holds for all n greater than k (that is 5). hence, the base case for the claim, \forall n \in N, 2^n > 10^n, is P(6): 2^6 = 64 > 60 = 10.6, which holds true. within the induction step, we utilized a chain of inequalities to prove that the claim is, in fact, true for all n > 5. this proof, like the stamps proof, was easy to comprehend for me and i find that the structure of the proof in the general case is simple enough to deliver for similar conjecture.
on friday, the problem set #2 was due. i think i did pretty well as far as proof presentation goes. i'm hoping to get a good mark on it. in this class, we considered three different claims about three different topics - equality of a sum, hexagons, and trees. for each, we were given the proof from the beginning and we had to determine whether we dis/agree with each proof. the first two took a little bit of digressing to understand, but the one about the tree threw me off (like always) a little. i'm gonna try to research a bit on different types of trees so i can better understand what each claim about a particular tree means.
Thursday, September 25, 2008
Thursday, September 18, 2008
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.
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.
week.one
i finally got this slog thing sorted out...i almost missed out the part about sending the url to prof heap to get the mark, but skimming does work apparently =D.
anywhoo, first day was okay. my first impression of the class is packed...hot...and just unfriendly to claustrophobic people (not i). i thought it was great that we have this course in a bahen classroom, as opposed to ramsay wright last year (didn't like the classroom there all that much). it'd be better if we had gotten room 1180 or 1190, though - space is key when having to deal with proofs and deep focus. most of the class was merely introduction to the course and a refresher on principle of simple induction (not my forte since the beginning of time).
on the wednesday lecture we did one proof on 12^n - 11 is a multiple of 11. i thought it was pretty straightforward - took me a while to think about it, though, because i was still in my summer state of mind. that's another thing, best summer of my life so far - didn't want it to end =(.
on friday, we did s'more proving on some basic claims such as units digit of 3^n is in {1, 3, 7, 9} and how many subsets of odd size does a set with n elements have?. i found it kind of interesting that prof heap started using shapes that resemble playstation's buttons as elements of a set. hehe.
i am not particularly looking forward to the assignments - never did so well with them last year in 165, but i did quite well in that course overall. perhaps i will push myself into utilizing office hours and ta consultation. i have nothing but moderately high hopes for this course - i am especialy glad to have prof heap as the instructor again.
anywhoo, first day was okay. my first impression of the class is packed...hot...and just unfriendly to claustrophobic people (not i). i thought it was great that we have this course in a bahen classroom, as opposed to ramsay wright last year (didn't like the classroom there all that much). it'd be better if we had gotten room 1180 or 1190, though - space is key when having to deal with proofs and deep focus. most of the class was merely introduction to the course and a refresher on principle of simple induction (not my forte since the beginning of time).
on the wednesday lecture we did one proof on 12^n - 11 is a multiple of 11. i thought it was pretty straightforward - took me a while to think about it, though, because i was still in my summer state of mind. that's another thing, best summer of my life so far - didn't want it to end =(.
on friday, we did s'more proving on some basic claims such as units digit of 3^n is in {1, 3, 7, 9} and how many subsets of odd size does a set with n elements have?. i found it kind of interesting that prof heap started using shapes that resemble playstation's buttons as elements of a set. hehe.
i am not particularly looking forward to the assignments - never did so well with them last year in 165, but i did quite well in that course overall. perhaps i will push myself into utilizing office hours and ta consultation. i have nothing but moderately high hopes for this course - i am especialy glad to have prof heap as the instructor again.
Subscribe to:
Comments (Atom)