Mathematical induction is a method of mathematical proof used to prove the truth of an infinite number of propositions. The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers and consists of two steps:
- Base case: show that the statement holds for n = 0, on = 1, depending on the definition of N used.
- Inductive step: show that if the statement is valid for n = k, then the same statement is valid for n = k + 1
This method works by testing that the statement is true for an initial value, and then testing that the process used to get from one value to the next is valid.
If both things are proven, then any value can be obtained through repetition of this process. To understand why two steps are enough, it is useful to think about the domino effect: if you have a long row of standing dominoes, then you can ensure that:
- The first domino will fall.
- Whenever one domino falls, the next one will fall too.
Thus, you can conclude that all the dominoes will fall.
Characteristics
Some of the characteristics of mathematical induction are:
- It is based on the demonstration of a general statement from particular cases: Mathematical induction begins by proving the truth of the statement for a particular case, and then shows that this extends to all subsequent particular cases.
- Used to prove results on infinite sets: Mathematical induction is often used to prove results on infinite sets, as in proving theorems in number theory or set theory.
- It is based on the induction hypothesis: The induction hypothesis is a statement that is assumed to be true at the beginning of the proof. This hypothesis is used as a basis to demonstrate the truth of the statement for all the following particular cases.
- Requires a proof of the base of induction and the induction step: To prove a result using mathematical induction, it is necessary to first prove the truth of the statement for the base case (the induction hypothesis), and then show that this extends to all the following particular cases (the induction step).
- It can be used to prove recursive results: Mathematical induction can also be used to prove recursive results, that is, results that are based on the result of previous cases.
Difference between mathematical induction and empirical induction
In natural sciences, empirical induction is used. That is, from a large number of properly selected particular observations, laws are formulated that must govern certain phenomena. The validity of a mathematical theorem, however, is established in a completely different way.
In the case of the natural sciences, it cannot be concluded that this statement is valid (as seen in the Four Color Theorem, for example). The principle of complete induction is used to prove that the proposition holds for all cases (that is, there is actually one proposition for each case, usually an infinite number of cases).
Example
Try to prove 1 + 3 + 5 + … + (2n – 1) = n2.
P(n) = 1 + 3 + 5 + … + (2n – 1) = n2. Then it will be able to show that P(n) is true for every n N.
The first step
These examples of mathematical induction questions and answers will definitely make things easier for you.
If you face a problem like this, you should take the first step first.
The initial step will show that p(1) is true 1 = 12. So, p(1) is true.
Induction Step
Next, you can immediately apply the induction step. Just imagine if P(k) is true, namely:
1 + 3 + 5 + … + (2k – 1) = k2, k N
1 + 3 + 5 + … + (2k – 1) + 2(k + 1) – 1) = (k + 1)2
1 + 3 + 5 + … + (2k – 1) = k2
1 + 3 + 5 + … + (2k – 1) + (2(k + 1) – 1) = k2 + (2(k + 1) – 1)
1 + 3 + 5 + … + (2k – 1) + (2(k + 1) – 1) = k2 + 2k + 1
1 + 3 + 5 + … + (2k – 1) + (2(k + 1) – 1) = (k + 1)2
Based on this description, it is known that p(n) is true for each n of the natural numbers.