I set a voluntary assignment for my course a few weeks back. Students had just learned about proof by induction, and I tend to find that this is a subject which many get confused by. I think that one of the best ways to really understand a topic is to try and teach it to someone else, so I set up an exercise which was to write an explanation of Proof by Induction for a young high school student. We had around 100 entries, which took a while to read through! Of these 100 entries there were four which stood out (and many which were also very good). We (myself, and two senior tutors) have been unable to come up with an outright winner. That’s where you come in!

 

Please take a look at the following entries, and vote for the one that you think is best at this link: https://www.surveymonkey.com/r/9K3P8BJ.

 

Note that the names of the entries are my own:

 

Note that there are some interesting subtleties, even to these winning entries which were not 100% accurate. I have put a * by the slight issues. Can you see why?

 

Entry 1 (A journey of a thousand steps)

 

“A journey of a thousand miles begins with a single step.” ~ Lao Tzu

 

A powerful quote. One reason it’s so insightful is because it suggests that only a single step is required to start any journey, and no matter how tired you are, it just takes another step to continue it. You might argue that you’re only human, you have a limit to how many steps you can take, but we’ll ignore that technicality for now.

 

Generally speaking though, wouldn’t you agree that if you knew you always had another left step in you, you could always take that step and repeat the process for however long you like? This is the essence of an extremely powerful concept known to mathematicians as the Principle of Mathematical Induction (Induction for short). Wherever you are, if you can always take just one more step, you can take them all. Great. So say you want to walk to your friend Bob’s house, if you just stood looking out your front door thinking, “as long as I can always take another step, I’ll get to Bob’s house”, are you going to get there? Of course not! As Lao Tzu said, you actually need to actually TAKE a step in the first place. Your statement is abstract and without any real meaning until it’s anchored in something real, such as Step Number 1, also known as the Base Case. Once you prove to yourself that you can take Step Number 1, you remember your statement and take Step Number 2! Then Step Number 3, and so on. Before you actually took the first step, taking “another step” (called an Inductive Step) had no meaning to your stationary self.

 

Mathematically, this repetitive process would take you on a journey to infinity and beyond, but we’ve already deduced that we’re not Buzz Lightyear (at least, not all of us). Because we have an infinite amount of numbers (1, 2, 3, 4 … etc.) we can use this abstract tool to prove something all the way to infinity (in theory). The nice thing is this covers all possibilities, so the logic could be applied realistic things, such as a walk around the block or a journey of a thousand miles! Back to Induction. So we’ve decided we can do something for as long as we like if the following are true:

 

  1. We can do that something in the first place (the Base Case).
  2. We can always do that something one more time (the Inductive Step).

 

These two pieces of information are all that are required for you to prove something by Induction. Your starting point doesn’t even matter; if you were sleep-walking and only registered Step Number 67 on your journey, that’s fine. There’s nothing special about Step Number 1, it just means that you can only prove you’re capable of taking all the steps you want to take from Step Number 67 (the Base Case) onward, not before. You snooze, you lose.

 

Of course though, mathematicians are a fussy bunch. Those two criteria above aren’t going to fall out the sky, you actually need to PROVE them. Proving the Base Case is easy, you just need to put your foot in front of you and show you can take the first step. But proving the Inductive Step is another kettle of fish, and it involves some clever algebra which we won’t go into here. For now, just know that you first need to mathematically prove both facts before allowing the Principle of Induction to finish the job for you.

 

Now go take a walk or go for a run, because as long as you decide to always take that next step, you’re guaranteed to reach your destination. Maths really does get you places.

 

Entry 2 (A Christmas Tale)

 

At the end of every year, many families celebrate the holiday season by decorating a christmas tree, and almost all of them will use some form of lights. The kind of cheap lights that sit on a long wire that gets wrapped around a tree, and then sparkle in a whole lot of awesome colours when you plug them into the power socket.

 

In my family, we have a whole lot of these kinds of cheap, fragile lights in a big box. Every year, when we decorate the tree, the box gets opened and is full of hopelessly tangled wires which were hastily shoved in the year before. It’s always a bit of a pain untangling the wires and it can get really
boring testing each string of lights to see if they are still working. But, as I am about to tell you, if you think about some really clever maths, it’s a whole lot more fun!

 

So, when I want to test a string of lights, the first thing I do is untangle the the wire from any others and lay it out in a nice straight line along the floor.

 

The next thing I do is plug the wire into the wall socket so that it’s set up for what I’m about to do.

 

If I turn the switch on, electricity will flow through the wires. But, even if some of the lights are working, this cheap string of lights won’t light up because the circuit is broken. For the whole string to light up, electricity has to flow through each and every light. This only happens if that light is working and is properly connected to the next light too. If all the lights work and the connections between all the lights also work, then the entire string will shine and I’ll know that the whole thing works.

 

Okay cool, but what does this have to do with some fancy mathematics stuff?

 

Well, grown-up mathematicians do more than just follow rules to add and times numbers together. If you study maths in university, you learn how to create your own own rules. But you can’t just make up any old rules! You have to prove to all the other mathematicians that your rules make sense. One way to do this is by using something called ‘Mathematical Induction.” It sounds fancy, but it’s just as simple as setting up those christmas-tree lights. This is how it works:

 

  • First, they think up some ‘rule’ that they want to prove. This is just like taking a string of lights out of the box.
  • Next, they use maths to clearly describe what their rule says. This is called ‘stating’ and is just like untangling the string of lights and laying it out on the floor so you can easily see what on earth’s going on.
  • Next, they show that the rule is true for the first number in their set. This is called the ‘base case’ and is like plugging the string of lights into the wall. It’s how you start things going and provide the energy.
  • Mathematicians then assume one of the lights (called ’n’) works. They then use that to check that the wire connecting it to the next light (called ‘n+1’) isn’t broken. If they can show that the wire between any two lights is working, then they know that if the first light works, energy will flow into the second light and it will work too. This is called the ‘inductive step.’

     

     

     

The mathematicians have already plugged the string in (proven the base case) and they have proved that all the connections between lights are working. This means that if any light is shining, then the light next to it also shines (inductive step). Now, they can flick the switch and by the “Principle of Mathematical Induction”, the whole string will shine — proving that their rule was true and putting a festive smile on their overworked and underpaid faces.

 

Entry 3 (The Mathematical Detective Agency)

 

Mathematical Induction. Sounds scary does’t it? A long unfamiliar word that you’ve probably never heard of before. But if we just take the words apart, maybe we can get a little bit of an idea of what this could be. “Mathematical”, well that’s just sounds like the number stuff you see in school every day! That just leaves “induction”, which you could say is just similar to confirming a guess.

 

The best way to explain this would be to imagine that you are a detective; but even better than that, you’re a detective of numbers. And one day as you, the young Sherlock Holmes of the Mathematical world, sit enjoying your morning cereal you get an urgent call from the Math Police, with a new case that they’d like your opinion on. They’ve already got their suspicions about the details of the crime, but they just can’t find any evidence. And that’s where you come in, determined to build a logical case to get to the bottom of it all. So imagine know that the local Sergeant comes past and presents you with the case file. Opening it up you see that all they have so far is a hunch. All that the case file says is that if you put a collection of integers into a certain equation then you’d get something that divides nicely by 3 without any remainder. But of course their hunch by itself is not enough to close the case!

 

The first thing you’d do is to take a look if the statement they’ve made is at all close to the truth. You check the facts and try and put in one of the numbers from the collection into the equation. It turns out that it is divisible by 3 so maybe the police were right after all! So we’ve established a base for our case. We know it works for the number you put in. That seemed pretty easy but what do we do now? We know that it the police’s statement is true for the number we just checked but what about all the other numbers in the collection they spoke about? Surely one example is not enough to say that the statement is true for all the other values as well. So you take a magic bottomless Christmas stocking and throw all the numbers from the collection the police mentioned into that stocking. You blindfold yourself and reach into the stocking and pull out some number from the bag, but  because you’re blindfolded you don’t actually know what it is. You just know that it is a number from the collection of numbers. Now, this is the part where your deduction skills really shine through. You assume that the  the number you are holding really is divisible by 3, even if you don’t really know. You decide to give this number a name and call it n. You realise that the number that follows it on the number line must be n + 1, the same way that the number that follows 1 on the number line is 1 + 1 = 2. Armed with this assumption, you realise that if you somehow show with logic and maths that the next number n + 1 is also divisible by 3, then you have shown that the statement is true for all the numbers in the collection starting from the one you checked in the beginning.

 

This is similar to the example that if dominoes are lined up in a row,  just like numbers are lined up, and you can show that when one domino falls it will always knock over the next one, Then knowing that the the first domino falls, in your case the first number you checked the statement with, then all the other dominoes, or numbers, will also fall and the statement must be true for all the dominoes or numbers. Dazzling the sergeant with your great maths skills you manage to prove that the statement is true for your n* and n + 1. Explaining to the sergeant what this means, it begins to dawn on him and he breathes a sigh of relief saying “Your skills of induction and deduction are unparalleled my friend. You’ve cracked the case.”.

 

Entry 4 (Domino Runs)

 

So today we’re going to learn how to prove maths statements using a fancy principle, The Principle of Mathematical Induction. Have you ever played a game where you set up a line of dominoes? When you push the first domino over, it will fall onto the second domino causing it to fall over onto the third domino which then falls over onto the fourth domino etc. If you have set up the dominoes properly, this process will continue until all of the dominoes have fallen over. This is the Domino Effect. If we set up the dominoes properly, we can say that:

 

  1. The first domino falls (since we push it).
  2. When any domino falls, the next domino always falls.

 

This shows that all dominoes will fall! This is exactly how Mathematical Induction works! A maths statement is something that uses an equals sign (=) or an inequality sign (<, >, \le, or \ge). It also often uses a variable, which is usually a lowercase letter, such as “x”.  A variable is a symbol for a number that we don’t know yet. Think of it as an empty box that you can put a number in. An example of a maths statement is:

 

1 + 2 + 3 + . . . + x =\dfrac{(x(x + 1))}{2}

 

The maths statement that we are trying to prove is like the game where we set up the dominoes. If the maths statement is true then it works for all numbers*, just like if we set up the dominoes properly then it works for all the dominoes and makes all the dominoes fall.  If the maths statement is not true then it doesn’t work for all the numbers,  just like if we don’t set up the dominoes properly then it doesn’t work for all the dominoes and doesn’t make all the dominoes fall.

 

Now let’s look at the dominoes game the other way around:   Once you have set up the game, if you know that when any domino falls, the next domino will fall, and you push the first domino, then you know that they will all fall. If you were a smart gambler you would bet all your money on this one.      However, once you have set up the game, if you know that when any domino falls, you can’t be sure that the next domino will fall, and you push the first domino, then you don’t know for sure that they will all fall. If you were a smart gambler you would bet no money on this one.

 

Similarly, for a maths statement, if we know that the starting number for x makes the statement true and we know that if any number in the place of x makes the statement true then the next number in the place of x will also make the statement true, then we know that all numbers after the starting one will make the statement true, just like we knew that all dominoes after the first one would fall over. (Because we know it is true for any x+1 if it is true for x and we know that it is true for x=1. So it is true for 1 but 1=x. So it is true for 1+1=2. But 2 can also equal x. So it is true for 2+1=3. But 3 can also equal x etc. Therefore it is true for 1, 1+1=2, 2+1=3, 3+1=4, 4+1=5, 5+1=6, 6+1=7,…)

 

So, the Mathematical Induction steps are:

 

  1. Show that the statement is true for x=1 (or some other starting number).
  2. Show that if any number in the place of x makes the statement true then the next number in the place of x will also make the statement true.

 

In maths terms we write: “Show that if some x=k is true, then x=k+1 is also true.”*

 

‘k’ stands for some number and therefore ‘k+1’ stands for the next number. How do we do this?   We just say that we are assuming (or guessing*) that it is true for x=k.  Then all we have to do is prove that it is true for x=k+1 using the information from the above step (that it is true for x=k).

 

An example: Prove

 

1 + 2 + 3 + . . . + x = \dfrac{x(x + 1)}{2}

 

(where x represents any of the natural numbers, also known as counting numbers) by Mathematical Induction.

 

  • Step 1 : Prove that it is true for x=1: LHS=1, RHS=  (1(1 + 1) )/2  = (1(2) )/2 = (2 )/2 = 1 =LHS

 

Therefore it is true for x=1.

 

  • Step 2:
    • Assume that it is true for some x=k: Therefore,  1 + 2 + 3 + . . . + k = \dfrac{k(k + 1)}{2}
    • Prove that it is true for x=k+1: Which means prove that 1 + 2 + 3 + . . . + k+(k+1) = \dfrac{(k+1)((k + 1)+1)}{2}
    • But 1 + 2 + 3 + . . . + k = \dfrac{k(k + 1)}{2}
    • Therefore:
      • (1 + 2 + 3 + ...+ k)+(k+1)=\dfrac{k(k + 1) }{2} + (k+1)=\dfrac{k(k + 1)}{2} + \dfrac{2(k + 1)}{2}
    • k+1 is a common factor:
      • \dfrac{k(k + 1)+ 2(k + 1) }{2}=\dfrac{(k + 1)(k+2)}{2}
    • 1 + 2 + 3 + . . . + x = \dfrac{x(x + 1)}{2} is true for x =k+1 if* it is true for some x =k and it is true for x =1.
    • Therefore it is true for any x where x is a natural number (counting number).

Now go vote!!!

How clear is this post?