What Is Natural Induction?

Mathematical Induction (MI) is a mathematical proof method that is usually used to prove that a given proposition holds within the entire (or local) range of natural numbers. In addition to natural numbers, generalized mathematical induction can also be used to prove general well-founded structures, such as trees in set theory. This generalized mathematical induction is used in the fields of mathematical logic and computer science and is called structural induction.

Mathematical Induction (MI) is a mathematical proof method that is usually used to prove that a given proposition holds within the entire (or local) range of natural numbers. In addition to natural numbers, generalized mathematical induction can also be used to prove general well-founded structures, such as trees in set theory. This generalized mathematical induction is used in the fields of mathematical logic and computer science and is called structural induction.

In number theory, mathematical induction is a mathematical theorem that proves that any given situation is correct (the first, the second, the third, and no exception).

Although there is "induction" in the name of mathematical induction, mathematical induction is not a rigorous inductive reasoning method. It belongs to a completely rigorous deductive reasoning method. In fact, all mathematical proofs are deductive.

The principles of mathematical induction are usually prescribed as natural axioms (see Piano's axiom). But on the basis of other axioms, it can be proved in some logical ways. The principle of mathematical induction can be derived from the following axioms of the well-ordered property (principle of natural numbers):

In application, mathematical induction often needs to adopt some changes to adapt to actual needs. Here are some common mathematical induction variants.

Start with numbers other than 0

If the proposition we want to prove is not all natural numbers, but only all natural numbers greater than or equal to a number b , then the steps of the proof need to be modified as follows:

The first step is to prove that the proposition holds when n = b. The second step is to prove that if n = m (mb) is true, then it can be deduced that n = m + 1 is also true.

In this way, propositions such as "when n 3, n ^ 2> 2n" can be proved.

For even or odd numbers

If the proposition we want to prove is not for all natural numbers, but only for all odd or even numbers, then the steps of proof need to be modified as follows:

Odd numbers:

The first step is to prove that the proposition holds when n = 1. The second step is to prove that if n = m is true, then it can be deduced that n = m + 2 is also true.

Even number:

The first step is to prove that the proposition holds when n = 0 or 2. The second step is to prove that if n = m is true, then it can be deduced that n = m + 2 is also true.

Descending Induction (also known as Recursive Induction)

Mathematical induction is not limited to propositions of the form "for any n ". For propositions of the form "for any n = 0,1,2, ..., m", if the general n is more complicated, and n = m is easier to verify, and we can achieve from k to k- Recursing 1 and k = 1 , ..., m , we can apply the induction method to obtain that for any n = 0,1,2, ..., m, the original proposition is true. If the proposition P (n) holds when n = 1,2,3, ..., t, and for any natural number k, then P (k), P (k + 1), P (k + 2 ), ..., P (k + t-1) holds, where t is a constant, then P (n) holds for all natural numbers.

Jump induction

Let P (n) represent a proposition related to the natural number n. If (1) P (1), P (2), ..., P (l) hold; (2) Assuming that P (k) holds, P ( k + l) holds, then P (n) holds for all natural numbers n.

First mathematical induction

Generally, to prove a proposition P (n) related to the natural number n, there are the following steps:

(1) Prove that the proposition holds when n takes the first value n0. n0 is 0 or 1 for general sequence, but there are special cases;

(2) Suppose that the proposition holds when n = k ( kn0, k is a natural number ), and proves that the proposition holds when n = k + 1.

Synthesizing (1) and (2), for all natural numbers n ( n0), the proposition P (n) holds.

Second mathematical induction (complete induction)

Another generalized method is called the complete induction method (also called the second mathematical induction method). In the second step, we assume that the formula holds not only when n = m , but also when n is less than or equal to m . This can be designed In two steps:

1. Prove that the formula holds when n = 0.

2. Suppose it holds when n m , and prove that the formula holds when n = m + 1.

Then the proposition holds.

For example, this method is used to prove:

The earliest known proof using mathematical induction appeared in Arithmeticorum libri duo (1575) by Francesco Maurolico. Maurolico cleverly proves that the sum of the first n odd numbers is n ^ 2 using recursive relations, and summarizes the mathematical induction.

The simplest and most common method of mathematical induction is to prove that an expression holds when n belongs to all positive integers . This method consists of the following two steps:

Basis of recursion: Prove that the expression holds when n = 1.

Basis of recursion: Prove that if n = m holds, then it also holds when n = m + 1.

The principle of this method is that the first step proves that the starting value is valid in the expression, and then proves that the proof process from one value to the next is valid. If both steps are proven, then the proof of any value can be included in the iterative process.