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.
Friday, December 5, 2008
A breeze of fresh air: structural induction.
One of the reasons why I like CSC236 is that I absolutely adore induction techniques. It is then indescribable how fascinated and excited I was when Danny drew the curtains and showed us the third flavour of induction: structural induction!
It really seems nature to me that many things can be expressed using structural induction. Larger sets can be decomposed as smaller sets. Trees are a combination of trunks and branches. Society is hierarchical and each hierarchy can be divided into different levels of various importances. Structural inductions can thus be utilized to prove a wide range of problems. I didn’t really understand why Professor Danny referred structural induction as “half of an induction technique”, but so be it.
It has to be noted that structural induction plays a very important role in the several definitions of regular expressions and languages introduced later in the course. See, structural induction rocks!
It really seems nature to me that many things can be expressed using structural induction. Larger sets can be decomposed as smaller sets. Trees are a combination of trunks and branches. Society is hierarchical and each hierarchy can be divided into different levels of various importances. Structural inductions can thus be utilized to prove a wide range of problems. I didn’t really understand why Professor Danny referred structural induction as “half of an induction technique”, but so be it.
It has to be noted that structural induction plays a very important role in the several definitions of regular expressions and languages introduced later in the course. See, structural induction rocks!
Recursions and python, the good old days in CSC148.
Oh, python, why did you leave me behind! Well, I guess Java is fun too.
During the fourth week, we were once again introduced to recursions. However, this time, recursions came with the tedious unwinding technique and even more mind-numbing proofs. The recursive structure in Fibonacci sequences is nothing new to me and the unwinding technique, though laborious, does not pose that big of a challenge to me either. This week was the most uninteresting week so far, which probably explains why I have nothing to write.
During the fourth week, we were once again introduced to recursions. However, this time, recursions came with the tedious unwinding technique and even more mind-numbing proofs. The recursive structure in Fibonacci sequences is nothing new to me and the unwinding technique, though laborious, does not pose that big of a challenge to me either. This week was the most uninteresting week so far, which probably explains why I have nothing to write.
Ternary Trees == Tribal Dancers!
Just in case you are completely weirded out by the title. Here is a little illustration.
A ternary with no children:
dOdddO
// \ = //\ = a tribal dancer.
dddddd/
ddddd/ \
So a forest ternary trees = a gang tribal dancers.
This is exactly what my scratch paper looked like when I was scratching my head, trying to figure out how to solve this problem during the fourth week. Imagine how much effort I had to put in just to explain to friends who were studying with me that I have graduated from kindergarten and I didn’t suck at doodling.
Wow, that was fun. Here comes back the serious stuff. The ternary trees question is EXCEEDINGLY HARD! It’s hard not because its solution involved strong induction, permutation, combination, and excellent tree-drawing skills, but because it requires two variable to nail the problem. TWO VARIABLES. As a student just graduated from MAT137, I did not see that coming! I tried so hard to actually come up with a formula using a single variable and I inevitably failed. I vividly remember how my eyes lit up when the friendly TA Tim Capes told me that we need two variables to get the solution. What an awesome question! Well, it was even more awesome to learn that this question was delayed to the second assignment due to its extreme awesomeness! Hurray, ternary trees! Hurray, tribal dancers.
The gathering of three brothers.
Among three basic ideas of computational logic, principle of well-ordering is my least favourite theory. The round-robin domino tournament example used in the class was somewhat puzzling and confusing for me. I still couldn’t figure it out until I visited Professor Danny Heap during his office hour. Nevertheless, principle of well-ordering proves to be of extreme importance in the golden ratio question in the assignment 1 and I loved how we don’t have to structure our proof (assume and then) when applying principle of well-ordering. Oh, I loved the golden ratio question too. It posed some manageable challenges to me and the process of resolving it was definitely satisfying!
The equivalences of three brothers (theories): principle of simple induction, principle of strong induction, and principle of well-ordering are unimaginably laborious and boring. Danny didn’t seem to be having fun proving them and neither did we. Personally, I don’t think that a perfect understanding of those equivalences will facilitate our problem-solving skills in the context of inductions.
The tricks and traps, on the other hand, are refreshing and informative. I still remember how I couldn’t figure out at all why one particular proof presented in the class because I omitted the all-important base cases. This goes to show the base cases, often neglected by me, should not be underestimated. When applying inductions, one should think seriously about the legitimacy and the number of base cases. Invalid base cases will disqualify a seemingly valid proof and unnecessary base cases will simply ruin the elegance of induction. Never ever underestimate the importance of base cases!
Strong induction is weaker than simple induction.
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”.
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”.
A sea of simple induction.
During week 1, we dived straight into a sea of induction, the fundamental concept of computational logic in the class. As a smooth transition from the three month summer vocation to the busy study season, our good friend: simple induction was introduced to us first. Examples of simple induction presented in the class were familiar yet interesting. The rightmost digit of 3^n reinforced the idea of appropriate base cases and the number of odd subsets of a set introduced, for the first time, a brand-new way of inductive thinking. After digging some dusted memories of CSC165, I did not have a hard time comprehending those examples.
Here is a simple exercise I did to understand the mechanism of simple induction. I used the structural proof I learned in CSC165.
Claim: There are no more than two consecutive elements of the Fibonacci sequence that have remainder 1 when divided by 7.
Proof using simple induction:
\forall i \in N, (mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1) \implies mod(F(i+2), 7) != 1.
Assume i \in N
Assume mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1
Then mod(F(i+2), 7) = mod(F(i) + F(i+1), 7)
# The property of the element in the Fibonacci sequence.
Then mod(F(i) + F(i+1), 7) = mod(mod(F(i), 7) + mod(F(i+1), 7), 7)
Then mod(mod(F(i), 7) + mod(F(i+1), 7), 7) = mod(1+1, 7) = 2
Then mod(F(i+2), 7) = 2
Then mod(F(i+2), 7) != 1
Then (mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1) \implies mod(F(i+2), 7) != 1
Then \forall i \in N, (mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1) \implies mod(F(i+2), 7) != 1
Here is a simple exercise I did to understand the mechanism of simple induction. I used the structural proof I learned in CSC165.
Claim: There are no more than two consecutive elements of the Fibonacci sequence that have remainder 1 when divided by 7.
Proof using simple induction:
\forall i \in N, (mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1) \implies mod(F(i+2), 7) != 1.
Assume i \in N
Assume mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1
Then mod(F(i+2), 7) = mod(F(i) + F(i+1), 7)
# The property of the element in the Fibonacci sequence.
Then mod(F(i) + F(i+1), 7) = mod(mod(F(i), 7) + mod(F(i+1), 7), 7)
Then mod(mod(F(i), 7) + mod(F(i+1), 7), 7) = mod(1+1, 7) = 2
Then mod(F(i+2), 7) = 2
Then mod(F(i+2), 7) != 1
Then (mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1) \implies mod(F(i+2), 7) != 1
Then \forall i \in N, (mod(F(i), 7) = 1 \and mod(F(i+1), 7) = 1) \implies mod(F(i+2), 7) != 1
Subscribe to:
Posts (Atom)