Summary notes

119 views39 pages
12 Sep 2010
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.

Already have an account? Log in
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
1. Contradiction.
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.

Already have an account? Log in
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
(
)
(
)
(
)
1111111212211 |||| qpqppqpqqpqqpppp llk. Contradiction!
www.notesolution.com
Unlock document

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

Already have an account? Log in

Get OneClass Grade+

Unlimited access to all notes and study guides.

Grade+All Inclusive
$10 USD/m
You will be charged $120 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.