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 Ոչ մի հաշվիչ չի կարող լուծել այս խնդիրը, բայց դրա մասերը հաշվարկելի են։ Փորձեք ստորեւ նշվածներից մեկը կամ գրեք ձեր սեփականը։

Ձեր սեփական աշխատանքը շարունակեք

Ազատ հաշիվը յուրաքանչյուր դասավանդման համար գրառումներ է ավելացնում, Ձեր ավարտելիք դասերի և լուծված խնդիրների ցուցակ է պահում մեկ տեղում, և ուսուցիչ, ում կարող եք հարցնել այս էջի մասին։ Մաթեմատիկան բաց է բոլորի համար, անկախ նրանից մուտքագրվել եք արդյոք կամ ոչ։

Գրանցվել Գրանցում

Օգտագործված սիմվոլներ

Տեղադրեք ցանկացած նշան՝ ամբողջական սահմանման, նկարի և դրա մեջ ամեն մի տառի իմաստը տեսնելու համար։

Հարցեր, որոնք մարդիկ տալիս են :

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.

Այս էջը կառուցված է հետևյալ սկզբունքով. Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Ընդհանուր և հատուկ դասակարգումներ: Ընդհանուր դասակարգում.

Ցուցադրել 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