Mathematical induction has strict requirements on the form of solving problems. In the process of solving problems by mathematical induction:
Step 1: Verify that n holds when it takes the first natural number.
Step 2: Assume that n=k holds, and then deduce it according to the conditions of verification and hypothesis. In the following derivation process, n=k+ 1 cannot be directly substituted into the assumed original formula.
The last step is to summarize the statement.
It should be emphasized that the two steps of mathematical induction are both very important and indispensable, otherwise the following absurd proof may be obtained:
Proof 1: All horses are one color.
First of all, in the first step, this proposition holds for n= 1, that is, when there is only 1 horse, the horse has only one color.
In the second step, assume that this proposition holds true for n, that is, assume that any n horses are one color. So when we have n+ 1 horses, we might as well number them:
1，2，3……n，n+ 1 .
For (1, 2...n) these horses, we can get from our hypothesis that they are all the same color.
For (2,3 ... n, n+ 1) these horses, we can also get that they are one color.
Because there are (2, 3, ... n) horses in two groups, it can be concluded that the n+ 1 horses are all of the same color.
The error of this proof comes from the second inference: when n= 1 and n+ 1=2, at this time, the number of horses is only 1 and 2, so the two groups are (1) and (2)-they do not intersect, so the second inference is wrong. The second step of mathematical induction requires that the process of n→n+ 1 holds for all numbers of n= 1, 2,3. ...
The above proof is like the gap between the first block and the second block of a domino is too big. The first block is pushed down, but the second block will not be pushed down. Even though we know that the fall of the second block will push down the third block and so on, this process has been interrupted between the first block and the second block.
rationality
The principle of mathematical induction is usually defined as the axiom of natural numbers (see Piano's axiom). But on the basis of other axioms, it can be proved by some logical methods. The principle of mathematical induction can be derived from the following axiom of good order (principle of minimum natural number):
Natural number set is orderly. (Each set of non-empty positive integers has a minimum element).
For example, the number of {1, 2,3,4,5} is the smallest-1.
Below we will prove mathematical induction through this property:
For the mathematical proposition that has been proved in the above two steps, we assume that it is not true for all positive integers.
There must be a minimum element k in the set s composed of those invalid numbers. (1 does not belong to the set s, so k >: 1).
K is already the smallest element in the set S, so k- 1 does not belong to S, which means that k- 1 is valid for the proposition-since it is valid for k- 1, it should also be valid for K, which contradicts the second step we completed. So this two-step proposition holds for all n.
It is worth noting that some other axioms are actually alternative axioms of mathematical induction principle. More precisely, the two are equivalent.
Refer to the above? Baidu Encyclopedia-Mathematical Induction