MAT246Y1a.doc

Page 1 of 39

Mathematical Induction

Notation

{

}

,3,2,1:=N are called the “natural numbers”.

Principle of Mathematical Induction

Suppose S is a set of natural numbers (i.e. N

⊆

S). If:

1) S

∈

1.

2) Sk∈+1 whenever Sk∈.

Then N

=

S.

Example

Prove for all N

∈

n the following formula holds:

(

)

(

)

6

121

21 222 ++

=+++ nnn

n.

Proof:

• Let

(

)

(

)

++

=++∈=6

121

1|22 mmm

mmSN.

• S

∈

1:

1

1

2

=

and

(

)

(

)

1

6

321 =.

• Assume Sk∈. Show Sk

∈

+

1.

•

(

)

(

)

6

121

122 ++

=++

∈kkk

kSk.

•

( )

(

)

(

)

( ) ( )

(

)

(

)

( ) ( )( )( )

( ) ( )( ) ( )( )

6

112111

6

3221

6

672

1

6

1612

11

6

121

11

2

22

22

+++++

=

+++

=

++

+=

+++

+=++

++

=++++

kkk

kkkkk

k

kkk

kk

kkk

kk

. So Sk

∈

+

1.

Extended Principle of Mathematical Induction

Suppose S is a set of natural numbers (i.e. N

⊆

S). If:

3) Sn ∈

0.

4) Sk∈+1 whenever Sk∈.

Then

{

}

Snnn ⊆++ ,2,1,

000

.

Example

Prove for 7

≥

n that n

n3!≥.

Proof:

• Let

{

}

m

mmS3!|≥∈=N. Let 7

0=n.

• S

∈

7: 218735040!77=>= .

• Assume Sk∈. Show Sk

∈

+

1.

• k

kSk3!≥∈. Note by assumption 7≥k.

www.notesolution.com

MAT246Y1a.doc

Page 2 of 39

•

(

)

(

)

(

)

(

)

1

33383131!+

=≥≥+≥+ kkkk kkk .

Well Ordering Principle

Every subset of N other than

φ

has a smallest element.

Theorem

Suppose N

⊆

S. If:

1) S

∈

1.

2) Sk∈+1 whenever Sk∈.

Then N

=

S.

Proof:

• Let

{

}

SnnT∉∈=|N, i.e., T is the “complement” of S.

• Want to show that

φ

=

T. This is equivalent to N

=

S.

• Suppose

φ

≠

T. Then (by well ordering principle) T has a smallest element, call it Tt∈

1.

• So Tt∉−1

1 (1

1≠tbecause S

∈

1), so St∈−1

1.

• But by assumption 2,

(

)

St∈+− 11

1, so St∈

1 and Tt∉

1. Contradiction.

Notation

Let N∈ba, . Say “a divides b” (write ba |) if cab ⋅= for some N

∈

c.

Definition

N

∈

p is prime if the only divisors of p are 1 and p, and 1

≠

p.

Extended Principle of Mathematical Induction

Suppose S is a set of natural numbers (i.e. N

⊆

S). If:

1) Sn ∈

0.

2) Sk∈+1 whenever Sknn ∈+,,1,00 .

Then

{

}

Snnn ⊆++ ,2,1,

000

.

• Note: nmm <

′

<,1, so Smm ∈

′

, . It means ll

l

lqqppmmn

qqm

ppm

′

′

⋅=

′

=

=

′

=

11

1

1.

Example: False Proofs

“Claim”: In any set of n people, all of them have the same age.

“Proof”:

• 1

=

n. True.

• Assume true for k. Show for 1+k.

• Let

{

}

11 ,, +k

pp be a set of 1+k people.

• Consider

{

}

k

pp ,,

1. They will all have the same age by assumption.

• Consider

{

}

12 ,, +k

pp . They will all have the same age by assumption.

www.notesolution.com

MAT246Y1a.doc

Page 3 of 39

• So the set

{

}

11 ,, +k

pp of 1+k people all have the same age.

The “proof” was false because if take 2=k, then

{

}

11 pT= and

{

}

22 pT= have no common element.

Number Theory

PRIME NUMBERS

Lemma

Suppose N

∈

n and 1

≠

n. Then n is a product of prime numbers.

Proof:

• Case 1: n is prime. Done!

• Case 2: n is not prime.

• Let

{

}

primes ofproduct a is and 1|nnnS ≠∈=N.

• S

∈

2.

• If sn

∈

−

1,,3,2, then Sn

∈

:

• Since n is not prime, there is some natural number nm,1

≠

such that nm|, i.e.

N∈

′

′

=mmmmn,, where nmm ,1,≠

′

.

Theorem

There is no largest prime number.

Proof:

• Assume p is the largest prime number. In particular, this says

{

}

p,,3,2 is the set of all primes.

• Let 132

+

⋅

⋅

⋅

=

pM. Note that 2, 3, …, p don’t divide M.

• Now,

1

>

M

, so there is some prime number q such that Mq|.

• But pq ,,3,2

≠

, so q is a “new” prime. Contradiction.

Theorem: Fundamental Theorem of Arithmetic

Every natural number not equal to 1 is a product of primes, and the primes in the product are unique

(including multiplicity) except for the order in which they occur.

Proof:

• Suppose there are natural numbers not equal to 1 with 2 distinct factorizations into primes. Then there

is the smallest of such number (well-ordering), call it N.

• lkqqppN 11 == . Note that all the pi’s are different than the qj’s. So in particular, 11 qp ≠ (say

11 qp <).

• Let

(

)

(

)

112212121 qpqqqqpqqqqqpNMllll −=−=−= , but also,

(

)

lklklqqpppqqppppqqpNM 221212121 −=−=−= . So

(

)

(

)

(

)

112221 qpqqqqppp llk−=− . Since

(

)

(

)

(

)

1111111212211 |||| qpqppqpqqpqqpppp llk−−− . Contradiction!

www.notesolution.com