maths.free › Abstract Algebra › 2. The Integers › Mathematical Induction
Mathematical Induction
Suppose we wish to show that \[\begin{aligned}\end{aligned}\] for any natural number n.
Mathematical Induction
Suppose we wish to show that \[\begin{aligned}\end{aligned}\] for any natural number \(n\). This formula is easily verified for small numbers such as \(n = 1\), \(2\), \(3\), or \(4\), but it is impossible to verify for all natural numbers on a case-by-case basis. To prove the formula true in general, a more generic method is required.
Suppose we have verified the equation for the first \(n\) cases. We will attempt to show that we can generate the formula for the \((n + 1)\)th case from this knowledge. The formula is true for \(n = 1\) since \[\begin{aligned}\end{aligned}\]. If we have verified the first \(n\) cases, then \[\begin{aligned}1 + 2 + \cdots + n + (n + 1) & = \frac{n(n + 1)}{2} + n + 1 \\ & = \frac{n^2 + 3n + 2}{2} \\ & = \frac{(n + 1)[(n + 1) + 1]}{2}\end{aligned}\]. This is exactly the formula for the \((n + 1)\)th case.
This method of proof is known as mathematical induction. Instead of attempting to verify a statement about some subset \(S\) of the positive integers \({\mathbb N}\) on a case-by-case basis, an impossible task if \(S\) is an infinite set, we give a specific proof for the smallest integer being considered, followed by a generic argument showing that if the statement holds for a given case, then it must also hold for the next case in the sequence. We summarize mathematical induction in the following axiom.
Example
For all integers \(n \geq 3\), \(2^n \gt n + 4\). Since \[\begin{aligned}\end{aligned}\], the statement is true for \(n_0 = 3\). Assume that \(2^k \gt k + 4\) for \(k \geq 3\). Then \(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\). But \[\begin{aligned}\end{aligned}\] since \(k\) is positive. Hence, by induction, the statement holds for all integers \(n \geq 3\).
We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.
A nonempty subset \(S\) of \({\mathbb Z}\) is well-ordered if \(S\) contains a least element. Notice that the set \({\mathbb Z}\) is not well-ordered since it does not contain a smallest element. However, the natural numbers are well-ordered.
Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.
Symbols used here
x belongs to A; every element of A is in B.
Inequalities that allow equality; < and > exclude it.
Naturals, integers, rationals, reals, complex numbers.
Marks the point where the statement has been established.
n divides a − b; a and b have the same remainder.
b is a multiple of a; the largest number dividing both.
A set with an operation; the do-nothing element; the element that undoes g.
Same structure; the group of cosets of a normal subgroup N.
The remainders 0…n−1 with clock arithmetic.
The set of morphisms; do g then f.
Questions people ask
What is a group, in plain words?
A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.
What is the difference between a ring and a field?
A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.
Prøv din egen
Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.
Mere i Abstract Algebra
GroupsSubgroups, cosets and Lagrange's theoremCyclic groups and permutation groupsHomomorphisms, normal subgroups and quotient groupsRings and fieldsGalois theory: why the quintic has no formula