PSI, PCI, PWO, Structural Induction.

The first segment of this course was about various flavors of induction.
PSI is the most familiar one, since I have learned this technique since high school. It is to prove the basis first, then prove that if case n is true, case n+1 is true as well. This technique is widely used not only in computer science.
PCI was first seen in MAT137 but not until this course that I extensively used this technique. Using PCI facilitated many proofs that was seen impossible, for you can assume all the case before n is true, so you can use the property of those.
This is my first course learning PWO. Intuitively it makes perfect sense, that every non-empty set of positive integers contains a smallest element. However, it is worth noticing that when applying this technique, I should not forget to prove that all the elements of the set are natural numbers, and they are in a non-increasing order. (I lost a few marks for this in test 2.) A good example is proving the loop invariant for looping correctness. For problems that seems not so comfortable with PSI or PCI, I should try to build such a set and see if it is better to apply PWO.
It can be proved that PWO, PCI, and PSI are equivalent.
Structural induction is best used when the predicate to prove is based on a inductive definition. The basis is the cases of the definition's basis. We then prove according to the inductive part of the definition.

A comparison between structural induction and PCI: Q3 in A3, every regex without * denotes a finite language. (only skeleton provided)

Structural induction: (based on the definition)
P(r): The language denoted by a regex r over a finite alphabet
without * is finite.
Claim: \forall finite alphabet, \forall r \in RE, P(r).
Basis: the basis of regex without * are \empty, \epsilon, a (\for every a \in \sigma). These all denotes finite languages.
Induction Steps: Assume P(r1), P(r2), then by definition, r1r2, r1+r2 \in RE. Then prove they both denotes finite languages.
Thus \forall r \in RE, P(r).

Complete induction: (based on the number of operations in the regex, n)
P(n): The language denoted by an n-operator regex R over a finite alphabet
without * is finite.
Claim: \forall finite alphabet, \forall n \in N, P(n).
Proof: Let \sigma be an arbitrary finite alphabet.
Base Case: if n = 0, that means R has no Alternation or Concatenation. In this case, P(0) holds.
Induction Step: Assume n is an arbitrary N. Assume P(m) is true for all 0 <= m <= n. Then any R of (n+1) Step is Concatenation or Alternation of R1, R2 with n-1, 1 operation respectively. By IH they both holds, then prove R1R2, R1+R2 both satisfy the predicate.
Therefore By PCI, \forall n \in N, P(n).
So \forall finite alphabet, \forall n \in N, P(n).