## induction (logic)

**-**

## Induction

# Induction

In mathematics, induction is a technique for proving certain types of mathematical statements. The induction principle can be illustrated by arranging a series of dominoes in a line. Suppose two facts are known about this line of dominoes.

- The first domino is knocked over.
- If one domino is knocked over, then the next domino is always knocked over.

What can be concluded from these statements? If the first domino is knocked over, then the second domino is knocked over, which knocks over the third, fourth, fifth, and so on, until eventually all of the dominoes fall.

Induction is a simple but powerful idea when applied to mathematical statements about positive integers. For example, consider the following statement: *n* ^{2} ≥ *n* for all positive integers, *n*. To prove that this statement is true using induction, it is necessary to prove two parts: first, that the statement is true for *n* = 1; and second, that if the statement is true for a positive integer *n = k,* then it must be true for *n = k* + 1. Demonstrating both of these parts proves that the mathematical statement has to be true for all positive integers.

Suppose using the induction principle it has been shown that *n* ^{2} ≥ *n*. It is then instructive to see how the statement is true for all positive integers, *n*. The first part says that *n* ^{2} ≥ *n* is true for *n* = 1, which is, in effect, knocking over the first domino. According to the second part, *n* ^{2} ≥ *n* is also true for *n = k* + 1 when it is true for *n = k*, so it is true for 1 + 1 = 2. This proves that the next domino is always knocked over. Now apply the second part again and take *k* = 2. Continuing this process proves that *n* ^{2} ≥ *n* is true for all positive integers.

Using the induction principle, it can also be shown that 2*n* is always an even number for all positive integers, *n.* Substitute 1, 2, 3, and 4 for *n,* and the results are 2, 4, 6, and 8, which are all even numbers. But how can it be certain that, without fail, every positive integer *n* will result in an even number for 2*n* ? It looks obvious, but often what looks obvious is not necessarily a valid proof. The induction principle, however, provides a valid proof.

The mathematical statement we want to prove is that 2*n* is an even number when *n* is a positive integer. To test the first part, we know that for *n* = 1, 2*n* is 2 × 1, or 2. The first even number is 2. So the statement is true for *n* = 1. To test the second part, suppose that 2*n* is an even number for some positive integer *n = k.* Therefore, 2*k* is even. Remember, adding 2 to any even number always produces an even number. So 2*k* + 2 is also an even number, but 2*k* + 2 = 2(*k* + 1). Hence, 2(*k* + 1) is an even number. Assuming that the statement is true for *n = k* leads to the fact that the statement is true for *n = k* + 1. Therefore, the induction principle proves that 2*n* is an even number for all positive integers, *n.*

see also Proof.

*Rafiq Ladhani*

## Bibliography

Amdahl, Kenn, and Jim Loats. *Algebra Unplugged.* Broomfield, CO: Clearwater Publishing Co., 1995.

Miller, Charles D., Vern E. Heeren, and E. John Hornsby, Jr. *Mathematical Ideas,* 9th ed. Boston: Addison-Wesley, 2001.

## induction (in logic)

induction, in logic, a form of argument in which the premises give grounds for the conclusion but do not necessitate it. Induction is contrasted with deduction, in which true premises do necessitate the conclusion. An important form of induction is the process of reasoning from the particular to the general. Francis Bacon in his *Novum Organum* (1620) elucidated the first formal theory of inductive logic, which he proposed as a logic of scientific discovery, as opposed to deductive logic, the logic of argumentation. Both processes, however, are used constantly in research. By observation of events (induction) and from principles already known (deduction), new hypotheses are formulated; the hypotheses are tested by applications; as the results of the tests satisfy the conditions of the hypotheses, laws are arrived at—by induction; from these laws future results may be determined by deduction. David Hume has influenced 20th-century philosophers of science who have focused on the question of how to assess the strength of different kinds of inductive argument (see Nelson Goodman; Sir Karl Raimund Popper). For a classic account of inductive arguments see J. S. Mill, *System of Logic* (1843).

See also R. Swinburne, ed., *The Justification of Induction* (1974); J. Cohen, *An Introduction to the Philosophy of Induction and Probability* (1989).

## induction

**induction** **1.** A method of logical inference in which a general but not necessarily true conclusion is drawn from a set of particular instances. In machine learning, for example, the term induction is used to describe an approach to machine learning in which generalized structures or statements are inferred from particular examples.

**2.** A process for proving mathematical statements involving members of an ordered set (possibly infinite). There are various formulations of the principle of induction. For example, by the *principle of finite induction*, to prove a statement *P*(*i*) is true for all integers *i *≥ *i*_{0}, it suffices to prove that

(a) *P*(*i*_{0}) is true;

(b) for all *k* ≥ *i*_{0}, the assumption that *P*(*k*) is true (the *induction hypothesis*) implies the truth of *P*(*k*+1).

(a) is called the *basis* of the proof, (b) is the *induction step*.

Generalizations are possible. Other forms of induction permit the induction step to assume the truth of *P*(*k*) and also that of *P*(*k*–1), *P*(*k*–2), …, *P*(*k*–*i*)

for suitable *i*. Statements of several variables can also be considered. See also structural induction.