An introduction to mathematical induction: A picture with players represented as match stick figures. The last ranked player gets 1 point, the second last player gets 2 points, and so on until the first player who gets 569 points. The picture then poses the question: "Total Points = ?"

Mathematical induction is an ingenious mathematical construct that originates from the human will to save time and effort. Imagine that you are an online game designer.

You are designing a new massively multiplayer online (MMO) game that involves a unique ranking system. This ranking system ranks each active player on a daily basis.

At the end of the daily allocated playtime, the player who places last gets 1 point, the player who places second to last gets 2 points, the player who places third to last gets 3 points, and so on. Naturally, the number of active players varies daily. Therefore, the total number of points that need to be allocated on any given day also varies.

All active players are required to sign up for daily playtime within a specified time limit. As soon as this time limit is up, your game servers crunch the data and provide you with the total number of players for that particular day.

You are now interested in computing the total number of points that you need to allocate for any given day as soon as you receive the total number of active players for that day. How would you go about this?

In this article, we will initially use the intuition behind the concept of mathematical induction to solve this problem. Following this, we will cover the explicit mathematical algorithm for mathematical induction. Finally, we will see how this method can be applied to a generalized mathematical use case.

This essay is supported by Generatebg

Counting Points

Let us first start with the most intuitive approach that comes to mind. We could treat each active player on any given day as a variable and assign points to each variable. Then, we could just sum up the number of points assigned to each variable to come up with the answer.

Consequently, the total points (TP) for any given day would be a sequential sum as follows:

Introduction to mathematical induction: : TP = 1 + 2 + 3 + 4 + 5 + …
Math illustrated by the author

This is a clever start. However, you get the feeling that the process could be faster and more efficient. We are currently not explicitly taking into account the total number of players.

Hypothesis Testing

You go over to a friend who is math-savvy and pose this problem. He proposes that you guys start with small sequences and try to observe patterns. Eventually, both of you come up with a pattern that seems to be working.

For sequences up to 5, you observe that the sum of the sequence is given by half the product of the number considered and the discrete number next to it. Expressed mathematically, if the total number of players were ‘n’, then your observation is as follows:

Introduction to mathematical induction: : Total Points (TP) = n*(n + 1)/2
Math illustrated by the author

You and your math-savvy friend are delighted about this finding. The only thing that remains is to prove that this observation/hypothesis is valid for any number of players.

You first increase the total number of players one by one to see if the hypothesis holds:

1 + 2 + 3 + 4 + 5 = 5(5 + 1)/2 = 5*6/2 = 30/2 = 15; 1 + 2 + 3 + 4 + 5 + 6 = 6(6 + 1)/2 = 6*7/2 = 42/2 = 21
Math illustrated by the author

You quickly realise that this is too tedious and exhausting. You will need to come up with a smarter way to prove your hypothesis.

Intuition for Mathematical Induction

Let us assume that your hypothesis is indeed true for any natural number. If this were the case, it would be true for a specific natural number k as well. The variable k here can take the value of any natural number.

What if we could test and prove your hypothesis for (k +1)? Let’s go ahead, do that, and see what happens.

We know that 1 + 2 + 3 + … + k = k*(k + 1)/2 Now, 1 + 2 + 3 + … + k + (k + 1) = [k*(k + 1)/2 ] + (k + 1) = [K(k + 1) + 2(k + 1)]/2 = (k + 1)(k + 2)/2 = [k + 1]( [(k + 1) + 1]/2
Math illustrated by the author

Based on this we can deduce that if our statement holds for any k, it will hold for the corresponding (k + 1) as well.

Imagine that your proof is like a domino system. If you are sure that one domino falls, you can prove that all dominoes following the first one will also fall.

Introduction to mathematical induction: A picture of dominoes lined up to be pushed down in a sequential order.
Image from Wikimedia Commons

In this sense, it is important to realise that even though we started with an assumption, there is no longer any assumption in the conclusion (proof). This is the beauty of mathematical induction.

There you have it. We just proved that we can use a simple formula to calculate the total number of points (TP) that need to be allocated given the total number of players participating on any given day:

TP = n(n +1)/2
Math illustrated by the author

So, your MMO game is in safe hands!

The Algorithm Behind Mathematical Induction

Mathematical induction is a mathematical proof method that can be applied to statements (hypotheses) that hold for all natural numbers. Consequently, it can be extended to other functions based on natural numbers such as trigonometric functions (inequalities) as well.

The algorithm as such consists only of two simple steps:

1. Prove the statement for a base case. The base case could be n = 0 or n = 1 or pretty much any fixed value of n (where n is a natural number).

2. Assume that the statement holds for a given natural number n = k, and prove (algebraically, for instance) that the statement holds for n = (k + 1) as well.

That is pretty much it. In the first step, you test out your hypothesis for a base case. In the second step, you prove that there is a domino effect. If the second step cannot be proved, there is no domino effect, and hence, there is no proof by mathematical induction.

This simplicity is what makes mathematical induction such a powerful tool in discrete mathematics.

Generalised Mathematical Use Cases

In our MMO game example, we just showed that mathematical induction can be used to prove that the sum of any n natural numbers is equal to n(n + 1)/2.

Similarly, mathematical induction can be applied to prove the results for many natural number sequences.

Below are a few examples of such provable sequences. I am not going into the proof for each one of these sequences. For now, it suffices if you get the broader picture about the range of applications for mathematical induction.

1. 1 + 2 + 2² + 2³ + … + 2^(n-1) =(2^n)-1

2. 1³ + 2³ + 3³ + … + n³ = n²(n + 1)²/4

3. |Sin(nx)| <= n|Sin(x)|, where n is a natural number and x is a real number; |x| denotes the absolute value of x.

Final Remarks

If you come from a philosophical background, it is important not to confuse mathematical induction with inductive reasoning. This mathematical proof method actually uses deductive reasoning even though its name might be a little misleading.

In this method, we examine an infinite number of cases (using ‘n’ as the variable) to prove a general statement using a finite chain of deductive reasoning steps.

Mathematical induction is one of those mathematical constructs that is quite simple to understand. One does not need exceptional mathematical skills to learn how to use it and appreciate its usefulness.

It is a beautiful illustration of how generations of human effort towards efficient problem-solving can lead to very elegant and simple solutions that are broadly applicable. Beauty and elegance are often associated with efficiency. In the case of mathematical induction, this is certainly the case!

I hope you found this article interesting and useful. If you’d like to get notified when interesting content gets published here, consider subscribing.

Further reading that might interest you: The Thrilling Story Of Calculus and Why Earning More Leads To Lesser Satisfaction?

Street Science

Explore humanity's most curious questions!

Sign up to receive more of our awesome content in your inbox!

Select your update frequency:

We don’t spam! Read our privacy policy for more info.