maths.free › Abstract Algebra › 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.

Acum tu Nici un calculator nu se așeză pe acesta, dar piesele sunt computabile. Încercați unul de mai jos, sau tastați propriul.

Păstrează-ţi propria muncă.

Un cont gratuit adaugă notițe despre fiecare lecție, un record de ceea ce ați terminat, problemele rezolvate într-un singur loc, și un tutor puteți întreba despre această pagină. Matemática în sine este deschisă tuturor, semnat sau nu.

Înregistrează Login

Simbole utilizate aici

Atinge orice simbol pentru definiţia completă, o imagine şi ce înseamnă fiecare literă.

Întrebări pe care oamenii le întreabă

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.

Partea acestei pagini este adaptată de la Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensată şi reexplicată aici; erorile sunt ale noastre.

Mai multe în Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula