It always puzzled me why strong induction is named strong while it uses more assumptions than simple induction. Anyhow, strong induction, the second flavour of the family of inductions was discussed during the lectures in week 2.
How do you prove that every natural number greater than 1 has a prime factorization? This seemingly straightforward question cannot be solved using simple induction as multiple previous instances are needed. It is then natural to apply strong induction to this problem. Since I have some prior knowledge on strong induction, I thought it would be just as easy as simple question. Various intriguing problems illustrated in the class proved me wrong.
Not only is strong induction used to prove mathematic-based problems, like the one I just mentioned, it can also be used to prove some problems of graph nature. For example, strong induction can be utilized to beautifully to prove that every full binary tree has an odd number of nodes and, even more interestingly, to prove that every chocolate grid of n squares can be broken into separate squares with n-1 breaks. In particular, the chocolate grid really raised my interested in the wide applications of strong induction. Maybe, that’s why it is named as “strong induction”.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment