Today I taught my class about recursion in computer science. As a precursor to this important topic, I also review the concept of Mathematical Induction. For those not in STEM, even if symbolic logic isn’t your cup of tea and Math isn’t your forte, please read on. I promise not to meditate on the Math in the topic. Instead I will focus on the Fun of it. This article contains digested material from various sources, classical and modern, laid out in lay terms for bedside reading.
Kinds of arguments
As those of us who studied philosophy know, there are two major kinds of philosophical arguments: Deductive and inductive. Deductive arguments give you conclusions that are guaranteed to be true if the premises are true. Suppose the first premise is that all men are mortal and the second premise is that “Socrates is a man”. The deductive conclusion you can draw from these two premises is that Socrates is mortal. There are no two ways about it. The important thing to keep in mind is that the argument is valid even if the conclusion is false. How can that be? Well, one of the premises could be false. If some men are immortal, or if Socrates is a god, for instance, then it’s entirely possible that Socrates could be immortal – yes?
Inductive arguments, in contrast, appeal to statements about the real world. Their domain is the universe of observations and measurements. Induction is what lies behind our daily lives (“It’s not gonna rain today so I’m gonna go on a hike”). The entire field of empirical science is based on inductive logic. It allows us to form tentative conclusions about reality while accepting the possibility that the premises do not necessarily lead to the conclusion always.
For example, my premise could be that the sun has always risen in the East every morning and my conclusion from this premise that the sun will rise in the East tomorrow. While it’s most likely true, there’s a slim chance that a comet could strike the Earth at night causing it to reverse its spin before dawn. In this case, my conclusion would be false even though the premise is true – The sun has indeed risen in the East every morning thus far.
The point about deductive and inductive logic is that by guaranteeing the truth value of the premises, the factory of deduction faithfully promises to deliver a true conclusion. But the factory of induction could only give you a conclusion that’s likely true.
Knowing this, we can now look at the amazing technique of mathematical induction which combines deduction and induction in a clever way to arrive at absolute (not tentative) truths about an infinity of things. It’s important to appreciate the distinction. Both induction and math induction rely on observations or experiments on some small set of things. In the induction example above, the observations were regarding where the sun rose for every day of recorded history. Its ambitious conclusion was that it would rise in the East every day of the future. Clearly, this conclusion will be wrong some day. In contrast, math induction is able to examine a similarly finite set of observations, but pronounce a truth that is guaranteed to be true for an infinite set of similar items – not just likely, but guaranteed. Imagine that! A technique that allows you to make true statements about everything by examining a small set of things. How does it do that?
It starts by combining an absolute truth you can establish using deduction with an observable truth about one or a few items. The items, however, share an important trait. They are related in some sequential way. They can be put in order.
Suppose you’re trying to prove a statement about life and all humans – say, “All humans like ice cream”. Math Induction says to first use deductive logic to prove a statement about the statement – specifically, prove that “If the statement is valid for some human, THEN the statement is valid for some other humans.” Typically “other humans” will be the next set of humans in some imaginary line such that as we progress down the line we’d eventually cover every single human.
So the first step is to show that IF some person likes ice cream, then the next person will also like ice cream. Note two important things about this step. First, the choice of “some person” should be purely arbitrary in that it could apply to any human, not just Bob, whom you know to like ice cream. Second, the establishment of that fact must be deductive, that is, bulletproof. Effectively what you’ll be saying is that IF A likes ice cream then B is guaranteed to like ice cream as well. And A could be any person in the infinite line of humans.
Often, proving this is no small feat, of course, and you may have to resort to fancy logic to simply establish this fact. But the critical thing to note is that this proof by itself, magical as it may be, DOES NOT GUARANTEE that all humans will like ice cream. It may still be that no humans like ice cream.
To conclusively prove that all humans like ice cream, you need one more important ingredient. That’s the second step, which is called the basis of induction. All you have to do now is to inject the result of an experiment or direct observation into this chain. Now you go and test if the first human in the line of humans likes ice cream. Suppose she does. Then BAM! You’ve instantly proven that every human likes ice cream. Why? Since person #1 likes it, person #2 must also like it because of the first step where you showed that if someone likes ice cream then the next one MUST like it too.
And since person #2 likes it, by appealing to the same logic, #3 must like it, and so ad infinitum. Sweet?
The beauty of this technique is that it combines deductive logic with direct experimental data to make a grand truth. The first step is the deductive logic (strangely called the inductive step) and the second is the experimental validation for a particular case (called the basis). It’s like you have this grand castle of logic in a different intangible dimension, and by tethering it to a small part of our testable and observable world you’ve brought it down to impact the entire world.
Having mindful fun
As I say in my mindfulness blog, the discriminative mind is the mind that plans. It is the part of our consciousness that wields the scalpel of logic. Clearly it must be kept sharp and incisive. But we must always keep in mind that the discriminative mind is a humble servant. To what end do we plan? Why do we do the things we do? A moment’s reflection suffices to show that all cerebral activity is geared towards generating positive experiential responses in our feeling mind. What good is it to have a powerful tool with nothing to use it on? Even those who claim they practice pure logic or art for its own sake only do so because it makes them feel good. To claim otherwise is disingenuous. On the other hand, a desire to feel good only, at the expense of a sharp and keen intellect (the discriminative mind) goes nowhere either. It’s only the fruitful union of the two – the feeling mind and the discriminative mind – that results in harmony.
How does this all tie in to having fun? Well, we like to have fun – that’s a no-brainer. We’ve already seen that. Learning a skill for the discriminative mind, say Math, Computer Science, or indeed any other endeavor, is surely useful, but serves no purpose by itself. One can become mechanically perfect in playing the piano, for instance. But what shines through to the audience is not their mechanical perfection, but their passion for the piece, their love of the art. I liken the perfection of a skill like programming to the mechanical calculus required to turn one thing into another.
Mechanical perfection, which is important, is like step 1 of Math induction – Elaborate, sophisticated and requiring much training, intellect and expertise. But if it doesn’t serve the “feeling master” within us, then it’s worth precious little. The positive experiential response that practicing the skill causes in you – I liken to the basis, and it’s priceless. It is that which grabs the ornate floating castle of logic and anchors it to the ground so we may enjoy it. Neither by itself will suffice.
So the first step in learning any skill is to cut a fast path to sampling the fun in it, and thereafter always keep the fun in focus. To this end, I try to get my students to appreciate and enjoy computer science as quickly as possible. The routine technical skills then come naturally as the desire to have fun with Math and CS takes root.