First of all, we are talking about Mathematics. Not Induction in Physics and Logic, although the latter is related to Mathematical Induction to some extent.
So what is Mathematical Induction? Induction here means to argue the proposition for a small case and then reuse it for a more complex case. To be precise an “Induction” proof must be done in a specific format. But in a very vague sense, you are proving by using simple cases inductively (in literal meaning) to argue the final goal statement. Let’s explore the example below.
Consider a chessboard and an L-shaped domino. How can you place some dominos onto the chessboard so that there is 1 specific uncovered cell (i.e. others fix one random cell which you cannot cover it)? It is trivial as you can place the domino in whatever position and it automatically leaves only 1 empty cell.
Then how about a chessboard? Can you place some dominos onto the chessboard so that there is only 1 uncovered cell too? You can try to do this in your own way. But here we want to do it in a more systematic way so that we can “reuse” the logic in the latter part. We can divide the board into 4 equal parts, that is 4 boards. As we know whenever we have a chessboard with 1 specific empty cell, we can still cover the remaining 3 cells with an L-shaped domino. Therefore, we can cover the middle with an L-shaped domino, then we have 3 chessboards with 1 blocked cell near the centre (blue crosses) and 1 chessboard with 1 preassigned empty cell (red cross).
Then how about a chessboard? We can reuse the logic as above. If we can do so for a chessboard, then for a chessboard, we can divide the board into 4 chessboards. Then we cover the centre with an L-shaped domino. It leaves us 3 chessboards with 1 blocked cell near the centre and 1 chessboard with 1 preassigned blocked cell, which all of them can be covered by some combinations of L-shaped dominos, as we can do it for any board as we assumed.
So why the proof is already complete? It is because we have proved for the case of (i.e. a chessboard), then by above, as whenever we can cover any chessboard with 1 specific empty cell (i.e. the case for ), we can cover a chessboard with 1 specific empty cell (i.e. the case for ).
In other words, if we have the case for , then we know the case for is also true.
Therefore, we can do it for the case of , and hence the case of , and so on for .
Hopefully, you can see this method is powerful to prove any statements related to positive integers. Formally, the principle of Mathematical Induction is as follows.
A statement is true for all positive integers if
- that statement is true for (base case) and,
- assuming that statement is true for , then that statement is true for (inductive step).
It is often described as the domino effect. To use only the base case and then repeat the inductive step, the statement is shown to be true for and so on.
The standard example of using such a principle is to show for all positive integers . If you are new to induction, you can try to follow the following steps.
- Show the statement is true for (base case):
- Assuming that statement is true for , Show that the statement is true for (inductive step):
It is given . If we add onto both sides, can we verify ?
It is too standard that you can even Google the answer directly. But it is always good to try it yourself first.
Although Mathematical Induction often associates with natural numbers, you can use it for negative numbers (by replacing by ) or even rational numbers in some cases (by using the base case and the inductive step from to ).
There are also different versions of Mathematical Induction, such as “Strong Induction” and “Backward Induction”. You can search these terms for more information.
It is very useful when you want to argue statements with discrete variables in Mathematics as well as Competitive Mathematics. Let’s do 2 examples.
Find a function which with . (Note that represents the set of all natural numbers. For the context here, we assume it means all positive numbers.)
To use induction to prove a formula, we need to first guess a plausible formula for . For a valid formula, it must be able to produce a after the squaring (and then multiplying by 2). One of such expression may be , which you may recognise similar technique in a question like “Find the value of if “.
However, . To transform to , we use and get .
Now, to make the form become and become , we employ the exponential function, namely substituting , we indeed get with .
To find , by , we need . By solving, we get . Hence, .
Finally, we get .
You may wonder what is the role of Induction here. The answer is simple, after getting the formula, as we just guess the answer, we must show that the expression is really valid for the condition. Induction is the formal way to go, which is left as an exercise for readers.
Problem 2 (Source: https://math.stackexchange.com/questions/850377/for-every-positive-number-n-there-exists-a-n-digit-number-having-all-odd-di)
Prove that for every positive integer , there exists an -digit number which is divisible by and all digits are odd.
You can try it for some small numbers. You should get , which all you need to get the next number is to add an extra digit in front of the previous number.
It is a strong signal that we can really use induction here. For , it is trivial as the number 5 is an (only) example. Now assume the statement is true for , where is a positive integer. Namely, we have a -digit number where all digits are odd. To add an extra digit, we add , where = 1, 3, 5, 7 or 9. (Note: This is the th digit, not th) We want to make the number divisible .
Therefore, we have . As 5 is a prime, we have . It is the same as solving the linear congruence equation in mod 5, for known numbers of . We know that such odd always exists by the Bézout’s identity.
We have seen some examples showing that time Induction is useful. But do not abuse it. We will see why in a future blog.