Week Three

Monday,
-----------Sept,. 22, 2008
In today's lecture we compared the three methods of proof we learned so far. Namely: simple induction, strong induction, and well ordering. We talked about the difference in their definitions as sets and the general ways to use them. Then we proved that if we believe in well ordering then we must believe in simple induction, and if we believe in simple induction then we must believe in complete induction. These two proofs were easy though weird. We will be doing the proof of complete induction to well ordering on Wednesday using the contrapositive.
Nothing else happened, probably because many students were absent, I do not know why; there were no rain or snow storms today :)

Wednesday,
-----------Sept,. 24, 2008
We talked about inductive proofs with bases cases other than zero. I cannot exactly say that today's lecture was about a different flavor of induction; but more of a special case. An important thing to notice is that because base cases can be greater than zero, we need to double check when a predicate holds if the question does not specify a domain. For example, in proving 2^n > 10n, zero does work, but {1, 2,.....,5} do not work. So we need to be careful. Other than that, base cases are fairly straight forward (at least this is what I think and I hope I will not have to change my opinion after a test or assignment).

Friday,
-----------Sept,. 26, 2008
Today, we concluded our long, though interesting discussion about induction by presenting examples where wrong things were done but the overall proof seemed perfectly true. I specifically liked the first example of \segma 2^i = 2^(n+1) -2 because it reminded me with Wednesday's lecture. In this type of questions, it turns out that mistakes do not only happen in determining the base cases, but also in the structure of the statement itself; \segma 2^i = 2^(n+1) -1 rather than \ 2^(n+1) -2.

Here is a summary of what I learned so far in the previous lectures:

• Induction is a powerful tool and it is well suited for us, lazy computer scientists. That is because you only need to establish a predicate, (a) base case(s), and a logical transition from p(n) to p(n+1), and induction will do the rest for you.

• In strong induction, it is not necessary to have base cases.
• In strong induction, base cases can be inside or outside the induction step.

• The principle of well ordering is usually used to set proofs by contradiction on sets of natural numbers.
• Always check if the given statement makes sense of not. Moreover, testing a couple of base cases is very useful.
• Be careful when setting lists that contain the first n items, and the lists containing from, say second to n+1 item. Sometimes, these lists do not overlap at certain values of n.
• Induction may not work quite smoothly with full binary trees because if a FBT has n nodes, then a tree with n + 1 nodes is not full.