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.
Now you Không máy tính nào có thể tính toán được nó, nhưng các mảnh của nó có thể tính toán được. Thử một trong những cách dưới đây, hoặc gõ theo ý bạn.
Ký hiệu được dùng ở đây
Nhấn vào bất kỳ ký hiệu nào để xem định nghĩa đầy đủ, một bức ảnh, và ý nghĩa của từng chữ cái trong nó.
Câu hỏi người ta hỏi
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.
Một số phần của trang này được chuyển từ Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Được nén lại và giải thích lại ở đây; lỗi là của chúng tôi.
More in 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