A retrospective of induction techniques.

Now that I have learned simple induction, strong induction, and structural induction, I think it is time for me to review them and compare their similarities and differences.

All of the above induction techniques have recursions built in. Simple induction requires only the previous instance while strong induction needs the validity of all previous instances. Structural induction is slightly different in that the term “pervious” does not apply here; it needs the validity of multiple smaller segments to prove the correctness of the larger entity.

Here are some of their differences in terms of proof structures. Simple induction needs one or many base cases and we can and have to assume that the previous (n-1) instance is correct in the induction steps. Strong induction does not require base cases; in another word, its base cases can be merged into its induction steps. We have to assume that all the previous (0 to n) instances are correct. Structural induction has more or less the same structure as strong induction. The instances we have to assume correct in the induction steps depend on the definition of the structure.

Induction techniques are the cornerstone of computational logic and they come up a lot in this course. It is crucial that I understand their mechanisms and know when and how to apply them.