Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

10.2: Well Ordering and Induction

( \newcommand{\kernel}{\mathrm{null}\,}\)

We begin this section with some important notation. Summation notation, written ji=1i, represents a sum. Here, i is called the index of the sum, and we add iterations until i=j. For example, ji=1i=1+2++j

Another example: a11+a12+a13=3i=1a1i

The following notation is a specific use of summation notation.

Notation 10.2.1: Summation Notation

Let aij be real numbers, and suppose 1ir while 1js. These numbers can be listed in a rectangular array as given by a11a12a1sa21a22a2sar1ar2ars

Then sj=1ri=1aij means to first sum the numbers in each column (using i as the index) and then to add the sums which result (using j as the index). Similarly, ri=1sj=1aij means to sum the vectors in each row (using j as the index) and then to add the sums which result (using i as the index).

Notice that since addition is commutative,

sj=1ri=1aij=ri=1sj=1aij.

We now consider the main concept of this section. Mathematical induction and well ordering are two extremely important principles in math. They are often used to prove significant things which would be hard to prove otherwise.

Definition 10.2.1: Well Ordered

A set is well ordered if every nonempty subset S, contains a smallest element z having the property that zx for all xS.

In particular, the set of natural numbers defined as N={1,2,}

is well ordered.

Consider the following proposition.

Proposition 10.2.1: Well Ordered Sets

Any set of integers larger than a given number is well ordered.

This proposition claims that if a set has a lower bound which is a real number, then this set is well ordered.

Further, this proposition implies the principle of mathematical induction. The symbol Z denotes the set of all integers. Note that if a is an integer, then there are no integers between a and a+1.

Theorem 10.2.1: Mathematical Induction

A set SZ, having the property that aS and n+1S whenever nS, contains all integers xZ such that xa.

Proof

Let T consist of all integers larger than or equal to a which are not in S. The theorem will be proved if T=. If T then by the well ordering principle, there would have to exist a smallest element of T, denoted as b. It must be the case that b>a since by definition, aT. Thus ba+1, and so b1a and b1S because if b1 S, then b1+1=bS by the assumed property of S. Therefore, b1T which contradicts the choice of b as the smallest element of T. (b1 is smaller.) Since a contradiction is obtained by assuming T, it must be the case that T= and this says that every integer at least as large as a is also in S.

Mathematical induction is a very useful device for proving theorems about the integers. The procedure is as follows.

Procedure 10.2.1: Proof by Mathematical Induction

Suppose Sn is a statement which is a function of the number n, for n=1,2,, and we wish to show that Sn is true for all n1. To do so using mathematical induction, use the following steps.

  1. Base Case: Show S1 is true.
  2. Assume Sn is true for some n, which is the induction hypothesis. Then, using this assumption, show that Sn+1 is true.

Proving these two steps shows that Sn is true for all n=1,2,.

We can use this procedure to solve the following examples.

Example 10.2.1: Proving by Induction

Prove by induction that nk=1k2=n(n+1)(2n+1)6.

Solution

By Procedure 10.2.1, we first need to show that this statement is true for n=1. When n=1, the statement says that 1k=1k2=1(1+1)(2(1)+1)6=66=1

The sum on the left hand side also equals 1, so this equation is true for n=1.

Now suppose this formula is valid for some n1 where n is an integer. Hence, the following equation is true.

nk=1k2=n(n+1)(2n+1)6

We want to show that this is true for n+1.

Suppose we add (n+1)2 to both sides of Equation (???). n+1k=1k2=nk=1k2+(n+1)2=n(n+1)(2n+1)6+(n+1)2

The step going from the first to the second line is based on the assumption that the formula is true for n. Now simplify the expression in the second line, n(n+1)(2n+1)6+(n+1)2

This equals (n+1)(n(2n+1)6+(n+1))

and n(2n+1)6+(n+1)=6(n+1)+2n2+n6=(n+2)(2n+3)6

Therefore, n+1k=1k2=(n+1)(n+2)(2n+3)6=(n+1)((n+1)+1)(2(n+1)+1)6

showing the formula holds for n+1 whenever it holds for n. This proves the formula by mathematical induction. In other words, this formula is true for all n=1,2,.

Consider another example.

Example 10.2.2: Proving an Inequality by Induction

Show that for all nN, 12342n12n<12n+1.

Solution

Again we will use the procedure given in Procedure 10.2.1 to prove that this statement is true for all n. Suppose n=1. Then the statement says 12<13

which is true.

Suppose then that the inequality holds for n. In other words, 12342n12n<12n+1

is true.

Now multiply both sides of this inequality by 2n+12n+2. This yields 12342n12n2n+12n+2<12n+12n+12n+2=2n+12n+2

The theorem will be proved if this last expression is less than 12n+3. This happens if and only if (12n+3)2=12n+3>2n+1(2n+2)2

which occurs if and only if (2n+2)2>(2n+3)(2n+1) and this is clearly true which may be seen from expanding both sides. This proves the inequality.

Let’s review the process just used. If S is the set of integers at least as large as 1 for which the formula holds, the first step was to show 1S and then that whenever nS, it follows n+1S. Therefore, by the principle of mathematical induction, S contains [1,)Z, all positive integers. In doing an inductive proof of this sort, the set S is normally not mentioned. One just verifies the steps above.


This page titled 10.2: Well Ordering and Induction is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Ken Kuttler (Lyryx) .

Support Center

How can we help?