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 “2n  is an even number” is true if we let n=1, n=2, n=3, ... 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

Induction10

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.

induction11

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!

induction12

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:

induction13

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.

induction14

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.

induction15

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

induction16
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, n = 1 ?
Yes! Because indeed (2\times 1) = 2  and this is even!

Condition II:

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

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

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

Since we have EVEN+EVEN, then the answer should be EVEN!
Thus 2(n+1) is even!

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

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

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!

induction17

Thanks for reading!

-Sinthorel

Advertisements

6 thoughts on “Induction

  1. HeineBorel says:

    Excellent post, Sinthorel! Would you mind writing about other methods of proofs when you have time? I have some problems understanding the difference between proofs by contradiction and proofs by contraposition.

    Liked by 1 person

    1. sinthorel says:

      Thanks a lot!
      Yes, I had a post about a contradiction proofs and why they work in the making :)!
      I will most definitely analyze a proof by contraposition after that though!

      Thanks for the suggestion!

      Like

  2. Kevin M-C says:

    Thank you for visiting and liking one of my posts on trigonometry! You have a great blog and I want to wish you the best on your university studies. When you have a passion for the subject you are studying, you will definitely succeed.

    I enjoyed reading your entry on induction. It was clear, enjoyable and reminded me of my days in my university and post graduate studies where I tried to apply mathematics to problem solving. It is wonderful to see others try to make mathematics enjoyable and mentally stimulating instead of the usual memorization and regurgitation. haha

    Best of luck on your studies, and I look forward to seeing more of your entries. Keep up the great work! 🙂

    Liked by 1 person

    1. sinthorel says:

      Thanks for your comment! I very much enjoy the way you write, so it wasn’t very difficult liking your content!

      I wholeheartedly agree. Passion is contagious. When a teacher – or any person really – has a passion in what they teach or explain, the people listening can’t help but pick up on that same passion, even though it might be on a subconscious level.

      I’m very glad you enjoyed it! My goal here is to always frame things in a different light, to make them more clear and I am happy that I have managed in that respect. Indeed, so many have absorbed mathematics in the wrong way, as just being memorisation and regurgitation, boring calculation and almost running around with no goal. My mother always told me Mathematics was a game. It was true back when I was finding 5×4, and it true now when you study university Mathematics.

      Thank you very much, I wish you all the best and shall take your comment to heart :)!

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s