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