# Summary notes

119 views39 pages
School
Department
Course
Professor 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 7k.
www.notesolution.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 39 pages and 3 million more documents. 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 Tt1
1 (1
1tbecause S
1), so St1
1.
But by assumption 2,
(
)
St+11
1, so St
1 and Tt
Notation
Let Nba, . 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
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 39 pages and 3 million more documents. 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 dont 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.
lkqqppN11 == . Note that all the pis are different than the qjs. So in particular, 11 qp (say
11 qp <).
Let
(
)
(
)
112212121 qpqqqqpqqqqqpNMllll === , but also,
(
)
lklklqqpppqqppppqqpNM221212121 === . So
(
)
(
)
(
)
112221 qpqqqqppp llk=. Since
(
)
(
)
(
)
www.notesolution.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 39 pages and 3 million more documents.