Given a set (S) of numbers (of any kind), we say that (ellin S) is a **least element of (S)** if (forall xin S), either (x=ell) or (ell

Every non-empty set of natural numbers has a least element.

This principle is often taken as an axiom.

### The Pigeonhole Principle

[thm:pigeonhole] **The Pigeonhole Principle:** Let (s,kinNN) satisfy (s>k). If (s) objects are placed in (k) boxes, then at least one box contains more than one object.

Suppose that none of the boxes contains more than one object. Then there are at most (k) objects. This leads to a contradiction with the fact that there are (s) objects for (s>k).

### The Principle of Mathematical Induction

We now present a valuable tool for proving results about integers. This tool is the principle of mathematical induction.

**The First Principle of Mathematical Induction:** Let (SsubsetNN) be a set satisfying the following two properties:

- (1in S); and
- (forall kinNN, kin SRightarrow k+1in S).

Then (S=NN). More generally, if (Pp(n)) is a property of natural numbers which may or may not be true for any particular (ninNN), satisfying

- (Pp(1)) is true; and
- (forall kinNN, Pp(k)RightarrowPp(k+1))

then (forall ninNN, Pp(n)) is true.

We use the well-ordering principle to prove this first principle of mathematical induction.

Let (S) be the set from the first part of the theorem and let (T) be the set of natural numbers not in (S). We will use a proof by contradiction, so assume (T) is non-empty.

Then, by the well-ordering principle, (T) contains a least element (ell).

Note that (1in S), so (1 otin T) and thus (ell>1). Therefore (ell-1) is a natural number. Since (ell) is the least element of (T), (ell-1) is not in (T), it is therefore in (S).

But by the defining properties of (S), since (ell-1in S), (ell=ell-1+1in S), which contradicts the fact that (ell) is a least element of (T), so in (T), so not in (S).

This contradiction implies that the assumption that (T) is non-empty is false, hence (S=NN).

For the second part of the theorem, let (S={ninNNmidPp(n) ext{ is true}}) and apply the first part.

[eg:inductionv1a] We use mathematical induction to show that (forall nin mathbb{N}) [sum_{j=1}^nj=frac{n(n+1)}{2}.] First note that [sum_{j=1}^1j=1=frac{1cdot 2}{2}] and thus the the statement is true for (n=1). For the remaining inductive step, suppose that the formula holds for some particular (ninNN), that is (sum_{j=1}^nj=frac{n(n+1)}{2}). We show that [sum_{j=1}^{n+1}j=frac{(n+1)(n+2)}{2}.] to complete the proof by induction. Indeed [sum_{j=1}^{n+1}j=sum_{j=1}^nj+(n+1)=frac{n(n+1)}{2}+(n+1)=frac{(n+1)(n+2)}{2},] and the result follows.

[eg:inductionv1b] Now we use mathematical induction to prove that (n!leq n^n) (forall ninNN).

Note that (1!=1leq 1^1=1). We now present the inductive step. Suppose that [n!leq n^n] for some (ninNN), we prove that ((n+1)!leq (n+1)^{n+1}). Note that [(n+1)!=(n+1)n!leq (n+1).n^n<(n+1)(n+1)^{n}=(n+1)^{n+1}.] This completes the proof.

**The Second Principle of Mathematical Induction:** Let (SsubsetNN) be a set satisfying the following two properties:

- (1in S); and
- (forall kinNN, 1,dots,kin SRightarrow k+1in S).

Then (S=NN). More generally, if (Pp(n)) is a property of natural numbers which may or may not be true for any particular (ninNN), satisfying

- (Pp(1)) is true; and
- (forall kinNN,) if (Pp(1),dots,Pp(k)) are all true, then (Pp(k+1)) is also true

then (forall ninNN, Pp(n)) is true.

To prove the second principle of induction, we use the first principle of induction.

Let (S) be a set of integers as in the first part of the theorem. For (ninNN), let (Pp(n)) be the mathematical property “(1,dots,nin S)”. Then we can apply the First Principle of Mathematical Induction to prove that (forall ninNN Pp(n)) is true, which means (S=NN). *[Details left to the reader.]*

The second part of the theorem follows from the first in exactly the same way that the second part of the First Principle of Mathematical Induction followed from the first.

## Exercises

Prove using mathematical induction that (n<3^n) for all positive integers (n).

Show that (sum_{j=1}^nj^2=frac{n(n+1)(2n+1)}{6}).

Use mathematical induction to prove that (sum_{j=1}^n(-1)^{j-1}j^2=(-1)^{n-1}n(n+1)/2).

Use mathematical induction to prove that (sum_{j=1}^nj^3=[n(n+1)/2]^2) for every positive integer (n).

Use mathematical induction to prove that (sum_{j=1}^n(2j-1)=n^2).

Use mathematical induction to prove that (2^n

Use mathematical induction to prove that (n^2

- A fictional mathematician and author of many (non-fictional – they really exist) fine mathematics texts, such as ↩
*Eavesdropper*apparently comes from the Old English*yfesdrype*, meaning literally*one who stands on the eavesdrop*[ground where water drips from the eaves of the roof]*to listen to conversations inside a house.*↩- Another synecdoche!↩
- Al-Kindi is a very interesting figure from early Muslim intellectual history:
*e.g.,*he seems to have brought Hindu numbers, with their place-value notation, into the Muslim world.↩ - On a
*classical*computer – there is an efficient algorithm known for factoring on a*quantum computer*, see and .↩ - Although in fact, some workable public key crypto had been invented earlier within the US/UK intelligence community, and not shared with the public. Since quite early in the Cold War, there have been mathematical theorems and proofs held in secret by large governments.↩
- As is the case with factoring, there is a known algorithm for a
*quantum computer*which solves the DHP efficiently, see .↩

## The Well-ordering Principle

The well-ordering principle says that the positive integers are **well-ordered.** An **ordered set** is said to be **well-ordered** if each and every nonempty subset has a smallest or least element. So the well-ordering principle is the following statement:

Note that this property is not true for subsets of the integers (in which there are arbitrarily small negative numbers) or the positive real numbers (in which there are elements arbitrarily close to zero).

An equivalent statement to the well-ordering principle is as follows:

The set of positive integers does not contain any infinite strictly decreasing sequences.

The proof that this principle is equivalent to the principle of mathematical induction is below.

When you asked about strong induction the other day, I wondered if the well ordering principle was on the way and here we are.

*are we not actually proving that weak induction implies the existence of a particular partial ordering ≤ on N such that it is a well-ordering with $x leq y Rightarrow x leq S(y)$ ?*

That would be a sensible thing to do, but it's probably not what's going on here.

I guess you're self-studying, since you said before that you were working within your own framework for the natural numbers and that you're working with a text that proves that weak induction, strong induction, and well ordering are equivalent.

A text that does that might start with a relatively large set of natural number axioms the Peano axioms, excluding induction, say some order laws and some addition laws. Or it might derive order from addition as it seems Mauro Allegranza's lecture notes do. It might not even state a set of axioms, but just proceed from prexisting informal knowledge: "You already know a lot about the natural numbers, but now we're going to tell you three new things though it will turn out that they're really just one new thing."

Anyhow, this is at a lower theoretical level than starting with the Peano axioms, constructing the order relations and arithmetic operations, and proving strong induction and well ordering. Maybe that's why you decided to develop your own framework.

Bottom line: The question you formulate most likely isn't the same question your text is asking, but a better question.

## Abstract Algebra: PRETEXT XML SAMPLE ONLY

for any natural number (n ext<.>) This formula is easily verified for small numbers such as (n = 1 ext<,>) 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

If we have verified the first (n) cases, then

This is exactly the formula for the ((n + 1))th case.

This method of proof is known as . Instead of attempting to verify a statement about some subset (S) of the positive integers (

###### Principle 2.1.1 . First Principle of Mathematical Induction.

Let (S(n)) be a statement about integers for (n in

###### Example 2.1.2 . An Inequality for Powers of (2).

For all integers (n geq 3 ext<,>) (2^n gt n + 4 ext<.>) Since

the statement is true for (n_0 = 3 ext<.>) Assume that (2^k gt k + 4) for (k geq 3 ext<.>) Then (2^

since (k) is positive. Hence, by induction, the statement holds for all integers (n geq 3 ext<.>)

###### Example 2.1.3 . Some Integers Divisible by (9).

Every integer (10^

is divisible by 9. Suppose that (10^

###### Example 2.1.4 . The Binomial Theorem.

We will prove the binomial theorem using mathematical induction that is,

where (a) and (b) are real numbers, (n in mathbb

is the binomial coefficient. We first show that

If (n = 1 ext<,>) the binomial theorem is easy to verify. Now assume that the result is true for (n) greater than or equal to 1. Then

We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.

###### Principle 2.1.5 . Second Principle of Mathematical Induction.

Let (S(n)) be a statement about integers for (n in

A nonempty subset (S) of (

###### Principle 2.1.6 . Principle of Well-Ordering.

Every nonempty subset of the natural numbers is well-ordered.

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

###### Lemma 2.1.7 .

The Principle of Mathematical Induction implies that (1) is the least positive natural number.

###### Proof .

Let (S = < n in

###### Theorem 2.1.8 .

The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of (mathbb N) contains a least element.

###### Proof .

We must show that if (S) is a nonempty subset of the natural numbers, then (S) contains a least element. If (S) contains 1, then the theorem is true by Lemma 2.1.7. Assume that if (S) contains an integer (k) such that (1 leq k leq n ext<,>) then (S) contains a least element. We will show that if a set (S) contains an integer less than or equal to (n + 1 ext<,>) then (S) has a least element. If (S) does not contain an integer less than (n+1 ext<,>) then (n+1) is the smallest integer in (S ext<.>) Otherwise, since (S) is nonempty, (S) must contain an integer less than or equal to (n ext<.>) In this case, by induction, (S) contains a least element.

Induction can also be very useful in formulating definitions. For instance, there are two ways to define (n! ext<,>) the factorial of a positive integer (n ext<.>)

The *explicit* definition: (n! = 1 cdot 2 cdot 3 cdots (n - 1) cdot n ext<.>)

The *inductive* or *recursive* definition: (1! = 1) and (n! = n(n - 1)!) for (n gt 1 ext<.>)

Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues.

## 1.3 Well Ordering Principle

This is one of over 2,400 courses on OCW. Explore materials for this course in the pages linked along the left.

**MIT OpenCourseWare** is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

**No enrollment or registration.** Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

**Knowledge is your reward.** Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

**Made for sharing**. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

#### About MIT OpenCourseWare

MIT OpenCourseWare is an online publication of materials from over 2,500 MIT courses, freely sharing knowledge with learners and educators around the world. Learn more »

© 2001&ndash2018

Massachusetts Institute of Technology

Your use of the MIT OpenCourseWare site and materials is subject to our Creative Commons License and other terms of use.

## 2. Structural Induction 结构归纳法

To prove results about recursively defined sets, we can use **Structural Induction**

- Basis Step: Show that the result holds for all elements specified in the basis step of the recursive definition to be in the set.
- Recursive Step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

## Section 6 Mathematical Induction

for any natural number (n ext<.>) This formula is easily verified for small numbers such as (n = 1 ext<,>) (2 ext<,>) (3 ext<,>) or (4 ext<,>) 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

If we have verified the first (n) cases, then

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 (

###### Principle 6.31 First Principle of Mathematical Induction

Let (S(n)) be a statement about integers for (n in

###### Example 6.32

For all integers (n geq 3 ext<,>) (2^n gt n + 4 ext<.>) Since

egin

the statement is true for (n_0 = 3 ext<.>) Assume that (2^k gt k + 4) for (k geq 3 ext<.>) Then (2^

egin

since (k) is positive. Hence, by induction, the statement holds for all integers (n geq 3 ext<.>)

###### Example 6.33

Every integer (10^

egin

is divisible by (9 ext<.>) Suppose that (10^

egin

###### Example 6.34

We will prove the binomial theorem using mathematical induction that is,

where (a) and (b) are real numbers, (n in mathbb

is the binomial coefficient. We first show that

If (n = 1 ext<,>) the binomial theorem is easy to verify. Now assume that the result is true for (n) greater than or equal to (1 ext<.>) Then

We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.

###### Principle 6.35 Second Principle of Mathematical Induction

Let (S(n)) be a statement about integers for (n in

A nonempty subset (S) of (**well-ordered** if (S) contains a least element. Notice that the set (

###### Principle 6.36 Principle of Well-Ordering

Every nonempty subset of the natural numbers is well-ordered.

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

###### Lemma 6.37

The Principle of Mathematical Induction implies that (1) is the least positive natural number.

###### Proof

Let (S = < n in

###### Theorem 6.38

The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of (mathbb N) contains a least element.

###### Proof

We must show that if (S) is a nonempty subset of the natural numbers, then (S) contains a least element. If (S) contains 1, then the theorem is true by Lemma 6.37. Assume that if (S) contains an integer (k) such that (1 leq k leq n ext<,>) then (S) contains a least element. We will show that if a set (S) contains an integer less than or equal to (n + 1 ext<,>) then (S) has a least element. If (S) does not contain an integer less than (n+1 ext<,>) then (n+1) is the smallest integer in (S ext<.>) Otherwise, since (S) is nonempty, (S) must contain an integer less than or equal to (n ext<.>) In this case, by induction, (S) contains a least element.

Induction can also be very useful in formulating definitions. For instance, there are two ways to define (n! ext<,>) the factorial of a positive integer (n ext<.>)

The *explicit* definition: (n! = 1 cdot 2 cdot 3 cdots (n - 1) cdot n ext<.>)

The *inductive* or *recursive* definition: (1! = 1) and (n! = n(n - 1)!) for (n gt 1 ext<.>)

Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues.

## SOLUTION: MATH 109 University of California San Diego Math Problems Questions

Math 109 SS1 2020

Homework 3

Lec A Prof. Chow

Due Tuesday, August 25 at 11:59 pm (new due date) by online submission to

gradescope.

All Exercises, Problems, and page number refer to Eccles’ book.

#1. Do Exercise 11.1 on p. 143 of Eccles: Suppose that Nn → X is a surjection. Prove,

by induction on n, that X is a finite set and that |X| ≤ n.

#2. Do #9 in Problems III on p. 184: Prove Proposition 11.1.4: if X → Nn is an

injection, then X is finite and |X| ≤ n.

#3. Do Exercise 11.4 on p. 143 of Eccles: Prove that, if a and b are non-zero integers

with gcd(a, b) = d, then the integers a/d and b/d are coprime.

#4. Prove: If A is a finite non-empty set of real numbers, then A has a minimum

element. (This is #5 in Problems III on p. 183, which is “half” of Proposition 11.2.3.)

#5. Given nonzero integers a1 , . . . , an , let

D(a1 , . . . , an ) =

Prove by induction that max D(a1 , . . . , an ) ≤ min<|a1 |, . . . , |an |>.

#6. Do Exercise 11.6 on p. 143: Prove by induction on n that if A is a set of positive

integers without a least element, then Nn ⊆ Z+ − A for every n, so that A is the empty set.

Deduce the well-ordering principle: every non-empty set of positive integers has a least

element.

#7. Do #11 in Problems III on p. 184. Use the pigeonhole principle and proof by

contradiction to prove Theorem 11.1.7: Given non-empty finite sets X and Y with |X| = |Y |,

a function f : X → Y is an injection if and only if f is a surjection.

#8. Do #12 in Problems III on p. 184: Suppose that there is an injection f : Z+ → X.

Prove by contradiction that X is an infinite set.

#9. Do #15 in Problems III on p. 184: Prove the induction principle from the wellordering principle (see Example 11.2.2(c)).

[Prove the induction principle in the form of Axiom 7.5.1 by contradiction.]

Hint: Axiom 5.4.1 is equivalent to Axiom 5.1.1. Assuming that the well-ordering principle

is false, there exists a subset B … consider the complement of B and apply the strong

induction principle.

Math 109 SS1 2020

Homework 3

Lec A Prof. Chow

#10. Let X1 , . . . , Xk be finite sets, where k is a positive integer. Given a set of j distinct

indices I =

XI =

Xi = Xi1 ∩ Xi2 ∩ · · · ∩ Xij .

i∈I

(a) For each nonempty subset I ⊆ N3 write out the set XI . For example, if I = <1, 3>,

then XI = X1 ∩ X3 .

(b) Write out the sum

X

(−1)|I|−1 |XI |.

∅6=I⊆N3

Do this so that the first line has the terms with |I| = 1, the second line has the terms with

|I| = 2, and the third line has the terms with |I| = 3. For example, if you are listing the

terms in “lexigraphical order”, then the first term of the first line would be |X1 |, since this

is equal to (−1)|<1>|−1 |X <1>|.

(c) Fact: The sum in part (b) is equal to |X1 ∪ X2 ∪ X3 |. That is,

X

|X1 ∪ X2 ∪ X3 | =

(−1)|I|−1 |XI |.

∅6=I⊆N3

Check that indeed this is the statement (don’t prove) of Proposition 10.3.2.

#11. Suppose that k is a positive integer for which we know for any finite sets Y1 , . . . , Yk ,

that (inclusion-exclusion principle for k sets)

|Y1 ∪ · · · ∪ Yk | =

X

(−1)|I|−1 |YI |.

∅6=I⊆Nk

Let X1 , . . . , Xk+1 be finite sets. Of course,

X1 ∪ · · · ∪ Xk+1 = (X1 ∪ · · · ∪ Xk ) ∪ Xk+1 .

(a) Prove by induction that for any n + 1 sets A0 , A1 , . . . , An

(A1 ∪ · · · ∪ An ) ∩ A0 = (A1 ∩ A0 ) ∪ · · · ∪ (An ∩ A0 ).

(1)

(b) Show that (remember the assumption on k)

|X1 ∪ · · · ∪ Xk+1 | =

X

∅6=I⊆Nk

(−1)|I|−1 |XI | + |Xk+1 | − |(X1 ∩ Xk+1 ) ∪ · · · ∪ (Xk ∩ Xk+1 )| .

Math 109 SS1 2020

Homework 3

Lec A Prof. Chow

#12. Continuation of the previous problem.

(a) For 0 ≤ i ≤ k, let Zi = Xi ∩ Xk+1 . Explain why if J ⊆ Nk , then

ZJ = XJ ∩ Xk+1 = XJ∪

(b) Prove that if ∅ =

6 I ⊆ Nk+1 , then exactly one of the following hold:

(i) ∅ =

6 I ⊆ Nk ,

(ii) I =

(iii) I = J ∪

6 J ⊆ Nk .

(c) Explain why

X

(−1)|I|−1 |XI | =

∅6=I⊆Nk+1

X

X

(−1)|I|−1 |XI | + |Xk+1 | +

∅6=I⊆Nk

(−1)|J| |XJ∪

∅6=J⊆Nk

(d) Prove that the sum in part (b) of the previous problem is equal to the sum in part

(c) of this problem, that is,

X

|X1 ∪ · · · ∪ Xk+1 | =

(−1)|I|−1 |XI |.

∅6=I⊆Nk+1

#13. Do #4 in Problems III on pp. 182–183. This is the inclusion-exclusion principle.

This shouldn’t be much work given all the work you have done on the previous problems #8

and #9.

#14. Prove, by induction on n, that for any sets X1 , . . . , Xn , the following equality for

characteristic functions:

χX1 ∪···∪Xn =

X

(−1)|I|−1 χXI .

∅6=I⊆Nn

[The proof of this problem is related to problems #11–#13. But it is much shorter.]

…

Purchase answer to see full

attachment

## 1.1: The Well-Ordering Principle and Mathematical Induction - Mathematics

The basic assumption one makes about the ordering of the integers is the following:

**Well-ordering principle**. *Every nonempty set of positive integers has a least element*.

From this assumption, it is easy to prove the following theorem, which underlies the method of proof by induction:

**Theorem 1: Principle of mathematical induction** *Let A represent a set of positive integers. Consider the following two conditions:*

(ii)*For any positive integer k*, *if k is in A*, *then k* + 1 *is in A*.

*If A is any set of positive integers satisfying these two conditions, then A consists of all the positive integers*.

PROOF: If *A* does not contain all the positive integers, then by the well-ordering principle (above), the set of all the positive integers which are *not* in *A* has a least element call it *b*. From Condition (i), *b* &ne 1 hence *b* > 1.

Thus, *b* &minus 1 > 0, and *b* &mdash 1 &isin *A* because *b* is the *least* positive integer *not* in *A*. But then, from Condition (ii), *b* &isin *A*, which is impossible. ■

Here is an example of how the principle of mathematical induction is used: We shall prove the identity

that is, the sum of the first *n* positive integers is equal to *n*(*n* + 1)/2.

Let *A* consist of all the positive integers *n* for which __Equation (1)__ is true. Then 1 is in *A* because

Next, suppose that *k* is any positive integer in *A* we must show that, in that case, *k* + 1 also is in *A*. To say that *k* is in *A* means that

By adding *k* + 1 to both sides of this equation, we get

From this last equation, *k* + 1 &isin *A*.

We have shown that 1 &isin *A*, and moreover, that if *k* &isin *A*, then *k* + 1 &isin *A*. So by the principle of mathematical induction, all the positive integers are in *A*. This means that __Equation (1)__ is true for every positive integer, as claimed.

*Use mathematical induction to prove the following:*

**1** 1 + 3 + 5 + ⋯ + (2*n* &minus 1) = *n* 2

(That is, the sum of the first *n* odd integers is equal to *n* 2 .)

**2** 1 3 + 2 3 + ⋯ + *n* 3 = (1 + 2 + ⋯ + *n*) 2

**3** 1 2 + 2 2 + ⋯ + *n* 2 = *n*(*n* + 1)(2*n* + 1)

**4** 1 3 + 2 3 + ⋯ + *n* 3 = *n*(*n* + 1) 2

**5**

**6** 1 2 + 2 2 + ⋯ + (*n* &minus 1) 2 2 + 2 2 + ⋯ + *n* 2

If you are the copyright holder of any material contained on our site and intend to remove it, please contact our site administrator for approval.

## Number Theory: In Context and Interactive

Before going further, we need a bit of review. The following three topics may be considered prerequisites for the course.

### Subsection 1.2.1 Well-Ordering

The first principle is both simple and deep. It is a deep property of the positive integers, but we give it its usual name.

###### Axiom 1.2.1 . Well-Ordering Principle.

Any nonempty set of positive integers has a least/smallest element.

This principle actually holds with any subset of (mathbb

Let's use it as an example to prove the following fact which you probably didn't know required proof.

###### Fact 1.2.2 . Consecutive Integers.

There are no integers between 0 and 1.

###### Proof .

This proof proceeds by contradiction. Assume there are some such integers, and let

This set must then have a least element (a ext<,>) and (0<a<1 ext<.>) If we multiply through by (a) (which is positive) then we obtain (0<a^2<a ext<.>)

Thus (a^2) is another integer such that (0<a^2<1 ext<,>) so (ain S ext<,>) but we also know that (a^2<a ext<.>) So (a^2) is an element of (S) which is less than the least element of (S ext<.>) That is a contradiction, so our original assumption was wrong and there are no such integers (i.e. (S) is empty).

###### Remark 1.2.3 .

To review, proofs by and both start by assuming the negation of the conclusion. A proof by contrapositive uses that assumption to prove the negation of the original assumption. A proof by contradiction, on the other hand, leads to some absurdity, but not necessarily just negating the original assumptions. In the proof above of Fact 1.2.2, the contradiction is that you can't have two different smallest elements of a set.

### Subsection 1.2.2 Induction

Sometimes we need a way to prove a statement for all integers (n) after a certain point, for instance integers greater than or equal to (n=1 ext<.>) This is usually called . Usually there are two steps in a typical ‘simple’ induction.

First we prove the “base case” (often (n=1) or (n=0)).

Then we prove the “induction step”, that the case (n=k) implies case (n=k+1 ext<.>)

These combine to prove a fact for *all* cases (ngeq 1 ext<.>)

###### Example 1.2.4 . Archetype for Induction.

The base case is to check that (1=frac<1(1+1)><2> ext<,>) which is easy.

The induction step begins with the assumption that

and then proceeds by showing that the formula is still true when (k) is replaced with (k+1 ext<.>) For this proof, to add just one more integer (k+1) to the sum means

(which we can see by rewriting the sum). Then we can just plug in the induction *assumption* to obtain

which is exactly what is required to finish the induction step, namely

Relative to some other basic axioms, one can actually take the legitimacy of induction as a final axiom and use that to prove well-ordering (Axiom 1.2.1) is true. Instructors will wish to note that *the converse is false* 4 . We will not include any such proofs (or a collection of relevant axioms, such as Peano's) here, but note the helpful exposition in [E.7.33].

### Subsection 1.2.3 Divisibility

###### Definition 1.2.5 .

If an integer (n) can be written as a product (kd=n) of two integers (k) and (d ext<,>) then we say that (d) (n ext<,>) or that (n) is by (d ext<,>) or that (d) is a of (n ext<.>) We write (dmid n) to denote that (d) divides (n ext<.>)

###### Example 1.2.6 .

For instance, the concept that (n) is even is just the same thing as (2mid n ext<.>)

The *divisors* of (n=8) are … (pm 1, pm 2, pm 4, pm 8 ext<.>) (Don't forget negative divisors.)

Very often we can write this generically, so for example (nmid x+1) means that (x+1) can be written as the product of (n) and some other integer (m ext<.>)

We occasionally use the term to denote a positive divisor of (n) which is not (n ext<>) in the example with (n=8 ext<,>) (1 ext<,>) (2 ext<,>) and (4) are all proper divisors.

There are lots of interesting things to say about divisibility. Let's prove a somewhat unexpected statement using induction and just what we already know.

###### Example 1.2.7 .

Show that (4mid 5^n-1) for (ngeq 0 ext<.>)

This proof will proceed by induction. This time the base case will be (n=0 ext<.>) We'll try to make the steps clear with separate bullets.

Base step: If (n=0) the formula says that 4 divides (5^0-1=1-1=0 ext<,>) which is definitely true.

Suppose (4mid 5^k-1 ext<.>) Then, by Definition 1.2.5, (5^k-1=4x) for some integer (x ext<.>)

Hence (5^k=1+4x) is a fact we could use later.

Our goal in this step is to show (4mid 5^

Since we need something true about (5^

Using the fact we obtained from the induction *assumption* we can write this as (5^kcdot 5=(1+4x)cdot 5 ext<>) this means that

Certainly (20x+4) is divisible by 4.

Thus we have shown that (4mid 5^

There are lots of other propositions about divisibility you are probably familiar with from previous courses. Here is a sampler.

###### Proposition 1.2.8 . Divisibility Facts.

If (amid b) and (bmid c) then (amid c ext<.>)

If (amid b) then (camid cb ext<.>)

If (cmid a) and (cmid b) then (cmid au+bv) for any integers (u,v ext<.>)

If (n>0) then all divisors of (n) are less than or equal to (n ext<.>)

These are not hard to prove (see Exercise 1.4.1). For instance, the second one can be proved by simply noting (b=ka) for some (kinmathbb