Study Guides (256,436)
CA (124,640)
UTSG (8,518)
MAT (561)
MAT246H1 (13)
idk (1)

summary notes

39 Pages
143 Views

Department
Mathematics
Course Code
MAT246H1
Professor
idk

This preview shows pages 1-3. Sign up to view the full 39 pages of the document.
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
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
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

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
Description
MAT246Y1a.doc Mathematical Induction Notation N := 1,2,3,}are called the natural numbers. Principle of Mathematical Induction Suppose S is a set of natural numbers (i.e. S N ). If: 1) 1S . 2) k +1S whenever k S . Then S =N . Example 2 2 2 n(n +1 2n +1) Prove for aln N the following formula hol1s:+2 ++ n = . 6 Proof: m m + 2m 1 + ) Let S = m N 12 + + 2= . 6 1 S : 1 =1 and 1 2 3 =1. 6 Assume k S . Show k +1S . 2 2 k k+ 1)(k +1) k S 1 + k+ = 6 . 12+ k+ 2+ k +1 2)= k k+1 2 k+1)+ (k+ 12)= k +1 k(2k)+1)+6 k +1) 6 6 2 2k +7 k+ 6 (k+ 1 k(+2 2 k+(3 ) =(k 1 ) 6 = 6 . So k +1S . = k +1 (k+(1 +1 2 k+(1 +1 )) 6 Extended Principle of Mathematical Induction Suppose S is a set of natural numbers (i.e. S N ). If: 3) n 0S . 4) k +1S whenever k S . Then {n0, 0 +1, 0 + 2,} S . Example Prove for n 7 that n! 3 . Proof: Let S = mN m! 3 m}. Letn = 7 . 0 7S :7!= 5040 > 3 = 2187. Assume k S . Show k +1S . k S k! 3k. Note by assumption k 7. Page 1 of 39 www.notesolution.com MAT246Y1a.doc k!(k +1) 3 ( +1 ) 3 8 ( ) 3 =( ) k+. Well Ordering Principle Every subset of N other than has a smallest element. Theorem Suppose S N . If: 1) 1S . 2) k +1S whenever k S . Then S = N . Proof: Let T = {nN nS }, i.e., T is the complement of S. Want to show that T = . This is equivalent to= N. Suppose T . Then (by well ordering principle) T has a smallest element, call it 1 So 1 1T (t1 1 because 1S ), st11S . But by assumption 2, (1 1)+1S , so1 S and t1T . Contradiction. Notation Let a,bN . Say a divides b (writea b) if b = ac for somecN . Definition pN is primeif the only divisors of p are 1 and p,p 1 . Extended Principle of Mathematical Induction Suppose S is a set of natural numbers (i.e. S N ). If: 1) n0S . 2) k +1S whenever n 0n 01, ,k S . Then n 0 n0+1, n0+ 2, } S . m = p1 pl Note: 1< m,m < n , so m,m S . It means n = mm = p1 p l 1 q l. m= q1 ql Example: False Proofs Claim: In any set of n people, all of them have the same age. Proof: n =1 . True. Assume true for k. Show for k +1. Let {p1, , pk+1}be a set of k +1 people. Consider {p1, , k}. They will all have the same age by assumption. Consider {p , , p }. They will all have the same age by assumption. 2 k+1 Page 2 of 39 www.notesolution.com MAT246Y1a.doc So the set{p1 , k+1}of k +1 people all have the same age. The proof was false because if take k = 2 T1= p 1 and T2= p 2 have no common element. Number Theory P RIME N UMBERS Lemma Suppose nN and n 1 . Then n is a product of prime numbers. Proof: Case 1: n is prime. Done! Case 2: n is not prime. Let S = nN n 1and nisa product of prime}. 2S . If 2,3,,n 1s , thennS : Since n is not prime, there is some natural number m 1,n sucm n, i.e. n = mm ,m,m N where m,m 1,n . Theorem There is no largest prime number. Proof: Assume p is the largest prime number. In particular, t{2,3a, } is the set of all primes. Let M = p + 1. Note that 2, 3, , p dont divide M. Now, M >1 , so there is some prime number q suchq M. But q 2,3,, p, 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. N = p p = q q . Note that all tie p s are different jhan the q s. So p qrt(sayar, 1 k 1 l 1 1 p1< q1). Let M = N p1 2 ql= q 1 2 ql p 1 2 ql= q(2 ql)(p1q 1), but also, M = N p1 2 ql= p1p 2 pk p1 2 ql= p 1( 2 pkq 2 ql). So p1p 2 pkq 2 ql= q 2 ql)p1q 1). Since p p p p q q ) p q q )p q ) p p q p q . Contradiction! 1 1 2 k 2 l 1 2 l 1 1 1 1 1 1 1 Page 3 of 39 www.notesolution.com
More Less
Unlock Document


Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit