A Comprehensible Introduction To Mathematical Induction

Math can actually be easy! Most of the time, the real problem is not that students aren’t smart enough, but that mathematical topics are taught in highly confusing ways. I have done a lot of math tutoring, and at some point I realized that once students see the bigger picture, things tend to fall into place almost automatically. So that’s how we’ll do it. Bigger picture first, math second, and hopefully some fun along the way. Once we get to the second part, the math will most likely no longer scare you. As for previous knowledge, it is only assumed that you know how to transform basic terms and equations. Alright, let’s get started then.

The stunning discovery of Carl Friedrich Gauss

Carl Friedrich Gauss was a German mathematician and is widely regarded as one of the smartest and most influential mathematicians of all time. Born in 1777, he went to school at a time when students had to get by without calculators and other fancy stuff. There wasn’t much more than blackboards and chalk. The story goes that his teacher wanted to have some off-time and was looking for a way to keep his students busy for a while. So he told them to add up all natural numbers from 1 all the way up to 100. Back then, you could still get caned if you screwed up, so the teacher expected that his students would be busy for quite some time, giving him a chance to basically take a nap. After all, they had to carefully calculate the result of this simple yet cumbersome term by hand:

1 + 2 + 3 … + 98 + 99 + 100

That’s a whopping 99 additions. While the first ones are still easy, the difficulty keeps going up as the numbers keep getting larger. Your chances of not screwing up are quite low since it only takes one miscalculation out of 99 to get a wrong result. While everybody else started to do one calculation after another, Gauss just sat there for a few minutes and thought about the problem at hand. Then he simply wrote down the correct solution:

5050

Yes, that’s right. The correct solution is 5050, and Gauss simply wrote it down on his blackboard. He was the only one who came up with the correct answer. While his teacher initially thought he might have to give Gauss a thorough beating for being lazy, he eventually had to admit that Gauss was right. At this time Gauss may have been just six or seven years old. Well, the dude was a genius after all. Alright then, how exactly did he manage to do 99 additions in just a few minutes without writing down anything? Well, he actually didn’t.

What Gauss really did was to recognize a simple pattern. He saw that the sum of the first and the last number equals 101. So does the sum of the second and second-last number. The same applies to the third and the third-last number. I guess by now you’re getting the picture.

1 + 100 = 101

2 + 99 = 101

3 + 98 = 101

.

.

49 + 52 = 101

50 + 51 = 101

Once you see this pattern, the solution is quite simple. Since we have 100 numbers in total and we need two of them for each equation, we end up with a grand total of 50 equations, right?

100 / 2 = 50

Now we simply have 101 times 50 which, big surprise, is the result that little Gauss wrote down.

101 * 50 = 5050

Great, now we have learned about how smart Gauss already was at quite an early age. The story is certainly a nice one, but how on earth will it help us learn about mathematical induction? Don’t worry, we’ll get there soon.

A slightly more abstract way to look at what Gauss discovered

Mathematicians are a strange bunch of people. They are never happy nor satisfied, they always want to know more and more. So instead of going all nuts and bananas about having found such an amazing shortcut to add up all the natural numbers from 1 to 100, they tend to immediately ask the next question. They would really love to know if this only works for an upper limit of 100, or if we can use the very same approach for any upper limit of our choice. Mathematicians want to know if there’s a formula where we can simply put in the upper limit and then get the sum of all the natural numbers all the way up to the upper limit we chose.

What mathematicians do in order to accomplish this is to substitute the upper limit of our specific case, right here that would be 100, with a letter. In math we call such a letter a variable. In our case, it stands for any natural number of our choice. Let’s pick “n” to represent this variable. Any other letter would work just the same. In fact, we could also use emojis instead of letters, it absolutely wouldn’t matter.

Let’s take one more look at the final equation for adding up all natural numbers from 1 to 100.

101 * 50 = 5050

Our upper limit is 100 and we would now like to be able to pick any natural number for the upper limit, not just 100. What we need to do is to substitute 100 with our variable, but let’s first write the equation in a slightly different way. On the left side we will express both numbers, 101 and 50, by using our upper limit of 100.

( 100 + 1 ) * ( 100 / 2 ) = 5050

Now we can easily substitute 100 with the variable “n”.

( n + 1 ) * ( n / 2 ) = “The sum of all natural number from 1 to n”

Great job! Now we have a formula where we can simply pick any upper limit we want, substitute the variable “n” with this limit of our choice, and then we get the sum by simply calculating the result of the term! That’s one heck of an accomplishment. Let’s say somebody picked 1,000,000,000 as the upper limit. Calculating the sum by hand would take forever and not screwing up along the way would be virtually impossible. With our newly discovered formula, the necessary calculations always remain constant. One addition, one division and one multiplication, that’s all it will take no matter what upper limit we pick! Could be 10, could be 1,000,000. It doesn’t matter.

Alright, let’s give it a try then. Let’s pick an upper limit of 4.

1 + 2 + 3 + 4 = 10

Now let’s use our cool formula instead.

( 4 + 1 ) * ( 4 / 2 ) = 5 * 2 = 10

Amazing, this really seems to work! One more try with an upper limit of 7.

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

( 7 + 1 ) * ( 7 / 2 ) = 8 * 3.5 = 28

Great, this works as well! You may now go ahead and try some more upper limits if you want to. Chances are they’ll work just the same.

Why we need some sort of proof technique

Mathematicians would now keep playing with this formula for a while. They want to see if they can find an example that doesn’t work. After many hours of playing around and not finding a single example that didn’t work, they come up with the educated guess that this formula works for any natural number we can possibly pick for “n”. Often times, 0 is also considered a natural number. This is the one upper limit we should rule out, because adding all natural numbers from 1 to 0 makes little sense. Picking 1 as the upper limit would be ok. We would only have one natural number and we actually need two of them to perform an addition, but simply using 0 as the second number will do the trick since adding 0 doesn’t change the final result.

1 + 0 = 1

Using the formula yields the same result.

( 1 + 1 ) * ( 1 / 2 ) = 2 * 0.5 = 1

So we are safe if we just rule out 0 as the upper limit. Alright, now here comes the part where we’ll eventually get to mathematical induction. The problem is that an educated guess isn’t going to cut it! It’s simply not how math works. Our intuition may tell us this formula should always work, but mathematics is about delivering hard proof. That’s a very important point. Mathematicians want to prove that the formula always works. That’s the beauty of mathematics. Every formula, every theorem has to be proven. Hard evidence is the very essence of math. Alright then, now on to the hard(er) part, let’s do some mathematical induction.

Mathematical induction to the rescue!

A formula such as ours is basically a statement about natural numbers. It tells us how to use a fancy shortcut in order to quickly get the sum of all natural numbers all the way up to an upper limit of our choice. When mathematicians first started trying to prove such formulas, they simply couldn’t quite figure out how to do it. Explicitly proving the formula for an upper limit of 1, then 2, then 3 and so on doesn’t get you anywhere. There is an infinite amount of natural numbers, so you can never say your job is done. What we need is some kind of trick, some insight that will help us reach our goal. Just like little Gauss found a hidden pattern and came up with his famous 5050, we now also need to find something that will get us far. Trying to figure out this trick all by yourself is almost impossible. I sure know I would never have found it on my own. Good thing is that’s not the goal. We’ll be perfectly fine with just comprehending what others have already discovered.

Ok, let’s take a look at the small trick that’s called mathematical induction. It’s a lot like dominoes. We all have seen a long line of dominoes. Tipping over the very first one triggers a chain reaction, and all the other dominoes will drop one by one. What we have to do when performing the miracle of mathematical induction is to explicitly topple over the first domino of our chain, and then we need to show that this will cause all other dominoes to drop as well. As for the bigger picture, that’s absolutely all there is to know! Really, it is that simple.

So let’s start doing some serious math then. Now that you know what we want to accomplish, it won’t be all that hard to follow along. Things simply tend to make a lot more sense once you know why they’re being done in the first place. First up is how to tip over the very first domino.

Getting the first domino to fall

Getting the first domino to fall is very simple. All it takes is to show that our formula works for the very first number it can be applied to. In our case, this is 1. Toppling over the first domino is called the base case in math. You might want to remember this term because chances are your teacher will ask you about it in a future test. Alright, that’s what the base case looks like.

1 + 0 = 1

( 1 + 1 ) * ( 1 / 2 ) = 2 * 0.5 = 1

Thats all, base case done! What we have just shown is that our formula indeed works for the very first domino which happens to be 1. The first line explicitly calculates the sum from 1 to 1. Since we only have one number, but two numbers are needed in order to perform an addition, we simply choose 0 as the second number. The second line simply uses the formula we want to prove, but we substitute “n” with 1 and then show that the result of this term equals 1. The sum from 1 to 1 equals 1 and our formula gives us the same result. Great, now there is only one more thing left to do, and that’s the actual hard part. Well, not quite all that hard, but a bit harder than the base case.

Showing that all the other dominoes will fall as well

Showing that toppling over the first one will eventually bring down all other dominoes as well is the tricky part, and we call it the induction step. It’s just another mathematical term for you to remember, but it’s not all that hard if you keep the domino picture in mind. Before I’ll show you the actual math behind the induction step, I’ll explain it to you without mathematical symbols. Again, math becomes way easier to follow along if you already know what all the equations are actually about.

The one thing left to prove is that if the formula works for any arbitrary upper limit of our choice, then it also works for its successor. Going back to the dominoes, we simply want to show that if we already know that a certain domino has dropped, then the next one will drop as well. You haven’t seen the math for the induction step yet, but nonetheless you now already know how mathematical induction works. Really, that’s basically it! And if you happen to be halfway familiar with terms and equations, then the few lines of mathematical stuff at the very end won’t be much of a problem at all. It really isn’t all that much anyway.

Alright, let’s just assume for a moment that we already did the math and we indeed managed to show that if our formula works for a certain upper limit, then the same formula also works for this upper limit’s successor. Let’s say somebody happens to come along and claims that for an upper limit of 4 our formula wouldn’t work. Of course, we could just use the formula directly and quickly prove the opposite. This would work just fine. However, the same person can now keep bothering us forever by always picking a new upper limit and challenging us to show that the formula works for it as well. Instead of using the formula over and over again, we can use our universally working proof instead.

Now the line of argument goes as follows. Our formula would work for 4 if it worked for 3. We know this because the induction step proves that if it works for a certain number, then it also works for the next one. So if we knew it worked for 3, then we would also know it must work for 4, because 4 is the successor of 3. Now we simply continue in the same fashion. Our formula would work for 3 if it worked for 2. It would work for 2 if only it worked for 1. But wait, we already know it indeed does work for 1! Still remember our base case? There we explicitly delivered proof that our formula really works for 1. Great, now we can travel the road backwards. We now know it works for 1, so because of the induction step it also must work for the successor of 1 which happens to be 2. Now we know it works for 2, therefore it must work for 3 as well, and if it works for 3, then our formula also works for 4. Proof delivered, and not just for our arbitrary upper limit of 4. This line of argument obviously works for any upper limit we could possibly ever pick! We have shown that our formula works for all upper limits, except for 0 as mentioned earlier.

Let’s do the missing little bit of math

Alright then, let’s do the actual math for the induction step to finish things up. We can simply assume that our formula already works for a certain upper limit, let’s call it “k”. We don’t want to use “n” again, because “n” is already used in the formula we want to prove. Let’s write S( k ) for the sum from 1 to k and S( k + 1 ) for the sum from 1 to k + 1. Introducing such abbreviations is very common in math and only serves the purpose of making equations shorter and therefore easier to read. We start out with the following simple equation.

S( k +1 ) = S( k ) + ( k + 1 )

This makes sense because it only says that the sum from 1 to k + 1 ist the same as the sum from 1 to k, with k + 1 added on top of it. Now let’s transform our original formula a little bit because it will make the rest of the proof somewhat simpler. Developing a feeling how to smartly transform terms and equations in order to get to a certain result quicker is a bit beyond the scope of this article, so I guess you just have to take my word for it.

( n + 1 ) * ( n / 2 ) = n² / 2 + n / 2 = ( n² + n ) / 2

Now, we can use our formula instead of S(k), because we assume that the formula already works for k.

S( k+1 ) = ( k² + k ) / 2 + ( k+1 )

Now we just transform the equation a bit. I won’t comment on the transformations, because this would make this article last forever and I initially assumed some basic knowledge about that stuff. I have to make some assumptions at some point, right? Anyhow, here we go.

S( k+1 ) = ( k² + k ) / 2 + ( k+1 ) = ( k² + k + 2k +2 ) / 2

= ( k² + 2k +1 + ( k +1 ) ) / 2

= ( ( k + 1 )² + ( k + 1 ) ) / 2

The last transformation is simply an application of the first binomial formula. Ok, I ended up making one comment about the transformations, but that’s the only one I’ll make. Just take a look at the last line. It’s our transformed initial formula! Let’s take another quick look at this transformed formula.

( n² + n ) / 2

Now, just substitute n with k + 1 and you end up with the last line of the induction step.

( ( k + 1 )² + ( k + 1 ) ) / 2

Great job, that’s all the math there is to it. We have managed to prove the induction step by starting out with an obvious equation, then using our assumption, and finally transforming the equation until we ended up with a final result which showed that the sum from 1 to k +1 is indeed what our formula suggests it should be. Base case plus induction step is now sufficient proof that our formula works for all natural upper limits. The base case makes the first domino drop, the induction step shows that all the other ones will eventually drop as well.

Often times, people get a little bit confused why exactly we can simply assume things. How can we assume that the formula already works for a certain “k”? The answer is that there is absolutely nothing wrong with doing this. In fact, every mathematical proof makes assumptions and then some new knowledge is derived from them. Usually, these assumptions are theorems or formulas that have already been proven. In our proof, we had already shown in the base case that such a “k” definitely exists, so assuming this later on in the induction step is perfectly alright.

Great job sticking with me all the way to the end! I hope you have gained a basic understanding of what mathematical induction is all about. If you had some trouble with the actual math part at the very end, then please make sure to first learn more about how to properly deal with basic terms and equations. Then just read the last part again and you should be able to follow along just fine. If not, please use the comments section to ask a question. I’ll get back to you as soon as possible.