Induction

A very common way how to prove a certain type of theorem or result in Mathematics is through a method of proof called Induction. The first time I personally was introduced to such a concept was through an immediate exposure to the method without any introduction, background or time to absorb what was taught. My goal here today will be to give this to you in reasonable enough quantity so as to appreciate its incredible power in solving problems of many different types.

Consider the following statement as an example:

“The number 2n is an even number for every n = 1, 2, 3, …”.

This statement will act as our motivation to prove by the end of this post.

At a glace, this statement makes the assertion that “ is an even number” is true if we let all the way to infinity.
One might reasonably ask the following:

“How can I show this for EVERY possible number, wouldn’t that require an infinite amount of time to do?”

Yes it would. Although Mathematics is all about finding ways/shortcuts to solve problems, and today we shall attempt to solve such a type of problem. To show something is true for an infinite number of numbers.

To understand the ideas behind such a mechanism, we first need to understand an analogous situation involving dominoes.
Suppose that you have a number of dominoes upright all across a room. Now these dominoes are special, in that each and every domino is either able to toppled or not.

The catch is that you do not know which dominoes ARE able to topple, and which ARE NOT able to topple. What you are left with are the following possibilities:

1. All your dominoes are able to be knocked over
2. All your dominoes are unable to be knocked over
3. You have some dominoes which can be knocked over and some which can’t

You now wish to check whether you have the 1st option; that all the dominoes are able to be knocked down.

Take a moment to think about ways of checking this.

NOTE: You are allowed to move around the dominoes as you please.

————————————————————————–

1. LONG WAY:

The long way would be to individually check that every single domino is capable of being knocked down. This means taking the time of day to try to topple every. single. domino that you might have.

An arduous task, given you don’t know how many dominoes you have to check…possibly an infinite number!!!

Does the long way sound eerily similar to our dilemma at hand?

“How can I show this for EVERY possible number, wouldn’t that require an infinite amount of time to do?”

2. SHORT WAY:

The short way, is to do what the inner child in all of us wants to do when they see dominoes, and that is…to make a chain!

In the long way, we had to manually ‘push’ every domino to check whether or not it is able to topple or not. While this way, we handily save ourselves time by using the act of one domino falling over as the ‘push’ for the domino in front of it.

—————————————————————–

Essentially, we shall now concern ourselves in finding the answer to the following problem:

What must happen to the dominoes over all else, to make sure all of them fall down?

The first condition is easy enough. What must absolutely happen to start off the chain reaction?

One domino must be knocked down

Whether it is by you pushing it purposefully, or accidentally, if this does not happen THEN NONE OF THE DOMINOES WILL FALL AT ALL.
So it is a must for what we want to happen!

For the second condition, think about the difference between these 2 cases:

 

On the right hand side, you can see that our chain stops halfway through! But why?

Remember what we had said originally…

“…you do not know which dominoes ARE able to topple, and which ARE NOT able to topple.”

So how can we avoid this? What must be the condition that will guarantee we won’t have one of these stick ups? Here it is.

If one domino topples, then the domino in front of it must topple

“Well of course this is the case!” you might remark.
It seems rather an obvious thing to say, but it is subtly rather powerful.

If this wasn’t true, then there would inevitably be a domino which is unable to ‘push’ the one in front of it! Look at the case below:

These are the ‘bad’ cases we want to avoid. So, what we are left with are the 2 conditions:

I) One domino must topple
II) If one domino topples, then the domino in front of it must topple

We already saw how the Condition I most definitely has to happen for the purposes of getting things started. Nevertheless, remember how this alone was not quite enough, as in the case where it stopped halfway through. We need Condition II to make sure there are no breaks in the chain reaction.

So as you can see, both of these conditions are crucial to guarantee that all the dominoes will topple over.

For those that feel that this is somewhat anti-climactic, consider the alternative. Checking each and every domino (possibly an infinite number) for whether they are able to be knocked down or not. All of that work, all of that checking…reduced to 2 simple conditions, which if not kept, will GUARANTEE that not ALL the dominoes are able to be toppled over.

This is indescribably powerful. Let me show you how this logical tool can be used to crack our original motivation:

“The number 2n is an even number for every n = 1, 2, 3, …”.

Suppose as before, we have a line of dominoes but this time, each domino is uniquely associated to some number.

Now we associate a domino ‘falling over’ with whether or not the particular number associated to it, satisfies what we want to show i.e. that is an even number.
For example, if , and is even (which it is) then the domino associated with the number is able to be toppled over! Similarly, if say is not an even number for then the domino associated with is not able to be toppled over!

Bit by bit you should be starting to see things start to fall in place…

Remember the conditions which guaranteed that all the dominoes must fall down?

I) One domino must topple
II) If one domino topples, then the domino in front of it must topple

Remember that a domino toppling means that the number associated with that domino SATISFIES what we want to prove. So keeping this in mind, how can we convert our conditions to the language we are using?

I) One particular n is satisfied
II) If n is satisfied then n+1 is also satisfied

This means that if we show the above conditions, similar to the case with dominoes, we are GUARANTEED that what we wanted to prove is SATISFIED for an infinite number of numbers!

Let us show this for our statement of interest. Recall for the last time:

“The number 2n is an even number for every n = 1, 2, 3, …”.

Condition I:

Is it true for a particular number, say, ?
Yes! Because indeed  and this is even!

Condition II:

Now we are tasked to show that if ANY satisfies what we want to prove, then so must . How do we set out to show this?

Well, since everything is pivoted around the fact that “IF  satisfies our statement”, then we already know that must be satisfied. This means that is an even number!
What we need to show is that must also satisfy what we want to prove i.e. is also an even number.

Let’s look at .
By simple algebra, we may distribute across addition like so:
But…we already know that is even. Why? Because and we have already shown that our statement is satisfied for !
Furthermore, we know that is also even. Why? Because we are assuming it! Remember that we are saying IF it is satisfied for .

Since we have EVEN+EVEN, then the answer should be EVEN!
Thus is even!

You might be a bit dubious that we’ve only shown Condition II for only 1 possible case of , but the beauty of Mathematics allows us to say that “If you have some number in mind that I haven’t checked (say ), then let , and what we have shown remains unchanged!”

And so, by what we’ve been discussing today. We have concretely shown that is an even number for every positive number !

In summary, we have created a powerful tool that allows us to tackle a vast amount of problems related with checking whether a particular statement is true for an infinite number of numbers, through the use of dominoes!
Watch it go!

Thanks for reading!