- On the Web:
- Mathematics LibreTexts - Mathematical Induction (Oct. 17, 2026)
mathematical induction
-
What is mathematical induction?
Mathematical induction is a technique to prove mathematical propositions. In its simplest form, it verifies a statement for the integer 1. Then, assuming it holds for an integer (x), it proves it for (x + 1). By this principle, all positive integers satisfy the statement.
A more complex form, double induction, proves a binary relation F holds among all positive integers by showing:
1. F holds between 1 and 1.
2. Whenever F holds between (x) and (y), it holds between (x) and (y + 1).
3. Whenever F holds between (x) and a positive integer (z), it holds between (x + 1) and 1.Transfinite induction generalizes this to well-ordered domains beyond positive integers.
1 Britannica SourceCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
When do we use mathematical induction in mathematics?
Mathematical induction is a method used to prove mathematical propositions.
An example of mathematical induction is the proof that the sum of the first (n) odd positive integers is (n^2):
[
1 + 3 + 5 + ... + (2n-1) = n^2
]
for every positive integer (n).There are also more complex kinds of mathematical induction such as proof by double induction. To prove that a particular binary relation (F) holds among all positive integers, it is sufficient to show:
1. The relation (F) holds between 1 and 1.
2. Whenever (F) holds between (x) and (y), it holds between (x) and (y + 1).
3. Whenever (F) holds between (x) and a certain positive integer (z), it holds between (x + 1) and 1.A general form of mathematical induction is the method of proof by transfinite induction, applicable to any well-ordered class or domain (D), instead of the domain of positive integers.
1 Britannica SourceCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What are the basic steps of a mathematical induction proof?
Mathematical induction proves statements for all positive integers. The basic steps are:
-
Base Case: Verify the statement is true for the first integer (usually ( n = 1 )).
-
Inductive Hypothesis: Assume the statement is true for an arbitrary integer ( k ) (the hypothesis of induction).
-
Inductive Step: Prove that if the statement is true for ( n = k ), then it must also be true for the next integer ( n = k + 1 ).
If these steps are completed, the principle of mathematical induction implies the statement is true for all positive integers.
1 Britannica SourceCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
-
What is the base case in mathematical induction, and why is it important?
In mathematical induction, the base case is the initial step that proves a statement is true for the smallest possible value, often ( n = 1 ).
The importance of the base case lies in establishing a foundation upon which the inductive step can build. It confirms the statement holds true at the starting point, ensuring the subsequent inductive reasoning is valid. Without the base case, the entire proof would be unsubstantiated, as there would be no guarantee that the statement holds true for any value of ( n ).
1 Britannica SourceCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
How does the inductive step work in a mathematical induction proof?
The inductive step in a mathematical induction proof shows that if a statement is true for some integer ( x ), it is also true for the next integer, ( x + 1 ).
To do this, first assume that the statement holds for ( x ). This assumption is called the hypothesis of induction. Then, using this assumption, prove that the statement also holds for ( x + 1 ). If you can prove this, you've shown that whenever the statement is true for an integer, it is also true for the next one. By the principle of mathematical induction, all positive integers will belong to ( F ).
1 Britannica SourceCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
Can you give an example of a problem that can be solved using mathematical induction?
A classic example of a problem solved by mathematical induction is proving that the sum of the first (n) odd positive integers equals (n^2).
To prove:
[
1 + 3 + 5 + \dots + (2n - 1) = n^2
]Base Case: For (n = 1), the equation holds because (1 = 1^2).
Inductive Hypothesis: Assume the equation holds for some positive integer (x), so
[
1 + 3 + 5 + \dots + (2x - 1) = x^2
]Inductive Step: We need to prove that the equation holds for (x + 1). Adding the next odd integer ((2x + 1)) to both sides of the hypothesis:
[
1 + 3 + 5 + \dots + (2x - 1) + (2x + 1) = x^2 + (2x + 1) = (x + 1)^2
]This shows that if the equation holds for (x), it also holds for (x + 1). By the principle of mathematical induction, the equation holds for all positive integers (n).
1 Britannica SourceCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
mathematical induction, one of various methods of proof of mathematical propositions, based on the principle of mathematical induction.
Principle of mathematical induction
A class of integers is called hereditary if, whenever any integer x belongs to the class, the successor of x (that is, the integer x + 1) also belongs to the class. The principle of mathematical induction is then: If the integer 0 belongs to the class F and F is hereditary, every nonnegative integer belongs to F. Alternatively, if the integer 1 belongs to the class F and F is hereditary, then every positive integer belongs to F. The principle is stated sometimes in one form, sometimes in the other. As either form of the principle is easily proved as a consequence of the other, it is not necessary to distinguish between the two.
The principle is also often stated in intensional form: A property of integers is called hereditary if, whenever any integer x has the property, its successor has the property. If the integer 1 has a certain property and this property is hereditary, every positive integer has the property.
" height="20" alt="HEW Logo">
Proof by mathematical induction
An example of the application of mathematical induction in the simplest case is the proof that the sum of the first n odd positive integers is n2—that is, that (1.) 1 + 3 + 5 +⋯+ (2n − 1) = n2 for every positive integer n. Let F be the class of integers for which equation (1.) holds; then the integer 1 belongs to F, since 1 = 12. If any integer x belongs to F, then (2.) 1 + 3 + 5 +⋯+ (2x − 1) = x2. The next odd integer after 2x − 1 is 2x + 1, and, when this is added to both sides of equation (2.), the result is (3.) 1 + 3 + 5 +⋯+ (2x + 1) = x2 + 2x + 1 = (x + 1)2. Equation (2.) is called the hypothesis of induction and states that equation (1.) holds when n is x, while equation (3.) states that equation (1.) holds when n is x + 1. Since equation (3.) has been proved as a consequence of equation (2.), it has been proved that whenever x belongs to F the successor of x belongs to F. Hence by the principle of mathematical induction all positive integers belong to F.
The foregoing is an example of simple induction; an illustration of the many more complex kinds of mathematical induction is the following method of proof by double induction. To prove that a particular binary relation F holds among all positive integers, it is sufficient to show first that the relation F holds between 1 and 1; second that whenever F holds between x and y, it holds between x and y + 1; and third that whenever F holds between x and a certain positive integer z (which may be fixed or may be made to depend on x), it holds between x + 1 and 1.
The logical status of the method of proof by mathematical induction is still a matter of disagreement among mathematicians. Giuseppe Peano included the principle of mathematical induction as one of his five axioms for arithmetic. Many mathematicians agree with Peano in regarding this principle just as one of the postulates characterizing a particular mathematical discipline (arithmetic) and as being in no fundamental way different from other postulates of arithmetic or of other branches of mathematics.
Henri Poincaré maintained that mathematical induction is synthetic and a priori—that is, it is not reducible to a principle of logic or demonstrable on logical grounds alone and yet is known independently of experience or observation. Thus mathematical induction has a special place as constituting mathematical reasoning par excellence and permits mathematics to proceed from its premises to genuinely new results, something that supposedly is not possible by logic alone. In this doctrine Poincaré has been followed by the school of mathematical intuitionism which treats mathematical induction as an ultimate foundation of mathematical thought, irreducible to anything prior to it and synthetic a priori in the sense of Immanuel Kant.
The trusted destination for professionals, college students, and lifelong learners.
SUBSCRIBE
Directly opposed to this is the undertaking of Gottlob Frege, later followed by Alfred North Whitehead and Bertrand Russell in Principia Mathematica, to show that the principle of mathematical induction is analytic in the sense that it is reduced to a principle of pure logic by suitable definitions of the terms involved.
Transfinite induction
A generalization of mathematical induction applicable to any well-ordered class or domain D, in place of the domain of positive integers, is the method of proof by transfinite induction. The domain D is said to be well ordered if the elements (numbers or entities of any other kind) belonging to it are in, or have been put into, an order in such a way that: 1. no element precedes itself in order; 2. if x precedes y in order, and y precedes z, then x precedes z; 3. in every non-empty subclass of D there is a first element (one that precedes all other elements in the subclass). From 3. it follows in particular that the domain D itself, if it is not empty, has a first element.
When an element x precedes an element y in the order just described, it may also be said that y follows x. The successor of an element x of a well-ordered domain D is defined as the first element that follows x (since by 3., if there are any elements that follow x, there must be a first among them). Similarly, the successor of a class E of elements of D is the first element that follows all members of E. A class F of elements of D is called hereditary if, whenever all the members of a class E of elements of D belong to F, the successor of E, if any, also belongs to F (and hence in particular, whenever an element x of D belongs to F, the successor of x, if any, also belongs to F). Proof by transfinite induction then depends on the principle that if the first element of a well-ordered domain D belongs to a hereditary class F, all elements of D belong to F.
One way of treating mathematical induction is to take it as a special case of transfinite induction. For example, there is a sense in which simple induction may be regarded as transfinite induction applied to the domain D of positive integers. The actual reduction of simple induction to this special case of transfinite induction requires the use of principles which themselves are ordinarily proved by mathematical induction, especially the ordering of the positive integers, and the principle that the successor of a class of positive integers, if there is one, must be the successor of a particular integer (the last or greatest integer) in the class. There is therefore also a sense in which mathematical induction is not reducible to transfinite induction.
The point of view of transfinite induction is, however, useful in classifying the more complex kinds of mathematical induction. In particular, double induction may be thought of as transfinite induction applied to the domain D of ordered pairs (x, y) of positive integers, where D is well ordered by the rule that the pair (x1, y1) precedes the pair (x2, y2) if x1 < x2 or if x1 = x2 and y1 < y2.