Induction, Mathematical

an extremely general method of mathematical proof and definition. Proofs by induction are based on the principle of mathematical induction, which is one of the fundamental mathematical axioms. Suppose we are required to prove that the formula

(1) 1 + 3 + 5 + ... + (2n - 1) = n²

holds for all natural (integral positive) numbers n. When n = 1, this formula yields 1 = 1². Next we assume that our formula holds for some definite value N of n, that is, we assume that

(2) 1 + 3 + 5 + ... + (2N - 1) = N₂

and prove its validity for a number one greater, that is, for n = N + 1. To do this, we need only add the single term (2N + 1) to the sum on the left-hand side of (2). Then the right-hand side of the equality is increased by (2N + 1) and consequently

1 + 3 + 5 + ... + (2N - 1) + (2N + 1) = N² + (2N + 1) = (N + 1)²

However, the same result is obtained if N + 1 is substituted for n in formula (1).

Thus the validity of (1) for n = N (for a fixed but arbitrary N implies the validity of (1) for n = N + 1. But when n = 1, formula (1) holds and consequently it also holds for n = 2 = 1 + 1, 3 = 2 + 1, 4 = 3 + 1, 5 = 4 + 1, and so on.

At this point we would be inclined to say that we have established the validity of (1) for all n. However, the very use of the term “and so on” is an admission of defeat. To establish the validity of (1) for all n we must, in fact, make use of an axiom that is not reducible to general rules of logic, although it expresses one of the fundamental properties of natural numbers. This axiom can be formulated in the following manner.

Principle of mathematical induction. Let the number 1 possess a certain property A. Furthermore, suppose that if some natural number n possesses the property A, then the number n + 1 also possesses the property A. Under these conditions, any natural number possesses the property A.

In the example we have examined above, the property A of the number n is expressed thus: “equation (1) is valid for the number n. “Upon reflection, the reader will see that the use of the principle of mathematical induction changes our pseudoproof into a proof. We note that in a proof [for example of formula (1)] based on this principle we do not argue from the particular to the general since one of the premises (the principle of mathematical induction itself) is at least as general as the conclusion.

The principle of mathematical induction formulated above is used, as has been shown, in the proof of mathematical theorems. Furthermore, mathematics makes use of definition by induction. An example is the following definition of the terms u_n of a geometric progression with the first term a and ratio q: (1) u₁ = a and (2) u_n+1 = u_nq. Conditions (1) and (2) uniquely determine the terms u_n of the progression for all natural numbers n. The proof that this is in fact so can be based on the principle of mathematical induction. In this case, however, we can express u_n directly in terms of n:

u_n = aqⁿ⁻¹

The principle of mathematical induction can be replaced by statements equivalent to it, such as: if a subset M of the set Z⁺ of all natural numbers contains 1 and together with any of its elements m contains m + 1, then M = Z⁺.