# Mathematical Induction

Also found in: Dictionary, Thesaurus, Medical, Legal, Financial, Wikipedia.

## mathematical induction

(mathematics)
A general method of proving statements concerning a positive integral variable: if a statement is proven true for x = 1, and if it is proven that, if the statement is true for x = 1, …, n, then it is true for x = n + 1, it follows that the statement is true for any integer. Also known as complete induction; method of infinite descent; proof by descent.

## 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) = n2

holds for all natural (integral positive) numbers n. When n = 1, this formula yields 1 = 12. 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) = N2

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) = N2 + (2N + 1) = (N + 1)2

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 un of a geometric progression with the first term a and ratio q: (1) u1 = a and (2) un+1 = unq. Conditions (1) and (2) uniquely determine the terms un 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 un directly in terms of n:

un = aqn−1

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+.

References in periodicals archive ?
On the other hand, mathematical induction can be formalized as follows (P is a boolean function, or predicate, of one argument, and P.
My experiences tell me that, in the classroom, the first example of a proof by mathematical induction shown to students tends to be the general result for triangular numbers, but only modelled as symbolic representation (Bruner, 1966), or at the extended abstract level of the SOLO taxonomy (Biggs & Collis, 1982).
By using the functional equation and employing mathematical induction, we show that for any positive integer m, [[bar.
by the assumption of mathematical induction, we get that
Mathematical induction is a very powerful proof technique.
Hence, by the strong form of mathematical induction, we can conclude f(n) = n, n = 1, 2, 3 .
For example, the theoretical principles of mathematical induction are used to define useful recursive C++ objects.
and it can be shown by mathematical induction that this formula also holds for n = 4, 5, etc.
The authors begin by covering the development of Peano arithmetic, mathematical induction and recursion theory.
1] for p, following through mathematical induction on p to prove that assertion.
He also offers very good appendices on mathematical induction and congruences, sets of exercises for each chapter, and examples throughout.
Michaelson highlights the notion that many students experience considerable difficulties when they learn and then attempt to construct and communicate proofs of conjectures using the principle of mathematical induction.

Site: Follow: Share:
Open / Close