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.

Sekarang kau Tiada kalkulator yang dapat menyelesaikan ini, tetapi bahagian-bahagian boleh dikira. Cuba salah satu di bawah, atau taipkan sendiri.

Jaga kerja awak sendiri.

Akaun percuma menambah nota pada setiap pengajaran, rekod apa yang anda selesaikan, masalah yang anda selesaikan di satu tempat, dan seorang guru yang anda boleh tanya tentang halaman ini. Matematik itu sendiri terbuka kepada semua orang, sama ada anda log masuk atau tidak.

Daftar Masuk Log masuk

Simbol yang digunakan di sini

Tekan simbol mana-mana untuk definisi penuh, gambar, dan apa makna setiap huruf dalamnya.

Soalan yang orang tanya

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.

Bahagian halaman ini diadaptasi dari Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Dikemas kini dan dijelaskan di sini; kesilapan adalah kami.

Lebih dalam 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