false

Class Notes
(836,374)

Canada
(509,758)

University of Toronto St. George
(44,026)

Mathematics
(2,843)

MAT246H1
(30)

Regina
(8)

Lecture

by
OneClass798

Unlock Document

Mathematics

MAT246H1

Regina

Fall

Description

MAT246 Lecture 2 (2012-09-19)
The Principle of Mathematical Induction:
If S is any set of natural numbers with the properties that:
A. 1 is in S, and
B. k+1 is in S whenever k is any number is S,
then S is the set of all natural numbers.
The Well-ordering of the Natural numbers:
Every set of natural numbers that contains at least one element in it has a smallest element
in it.
n(n+1)
Ex. Prove 1 + 2 + 3 + ⋯+ n − 1 + n = 2 ----- P(n)
Hint: want to show that P(1) is true, and P(k) => P(k+1)
Proof:
A. P(1). LHS = 1, RHS = 1(1+1)= 1. That is LHS = RHS.
2
B. Assuming the above formula is true. Then assume
k(k+1)
P k = 1 + 2 + 3 + ⋯+ k − 1 + k =) 2 , then
P k + 1 = P k + 1 + k + 1 )
k(k + 1) k k + 1 + 2(k + 1) (k + 1 (k + 2)
P k + 1 = + k + 1 =) =
2 2 2
(k + 1 , k + 1 + 1-
=
2
( ) ( ) k+1 , k+1 +1-
That is P k + 1 = 1 + 2 + 3 + ⋯+ k + k + 1 = 2
Thus the statement holds for all n by PMI.
2 2 2 2 n n+1 (2n+1)
Theorem 2.1.3: 1 + 2 + 3 + ⋯+ n = 6 ----- P(n)
Proof:
1 1+1 (2×1+1)
A. P(1). LHS = 1, RHS = 6 = 1
B. Assuming above formula is true. Then assume
2 2 2 2 k k+1 (2k+1)
P k = 1 + 2 + 3 + ⋯+ k = 6 , then
P k + 1 = P k + k + 1 )2
k k + 1 2k + 1 ) k k + 1 2k + 1 + 6 k + 1 )2
P k + 1 = + k + 1 )2=
6 6
2
(k + 1 (2k + k + 6k + 6) (k + 1 2k + 3 (k + 2)
P k + 1 = 6 = 6
(k + 1 ) (k + 1 + 1 2 k + 1 + 1 -
P k + 1 =
6
( ),( ) -,( ) -
That is P k + 1 = 1 + 2 + 3 + ⋯+ k + (k + 1) = 2 k+1 k+1 +1 2 k+1 +1
6
Thus the statement holds for all n by PMI. MAT246 Lecture 2 (2012-09-19)
WOP⇔MI
Proof:
1. WOP⟹MI
Let S be a set of natural numbers that satisfies the hypothesis of math induction.
Want to show that S = N.
We are assuming that 1 is in S and if k is in S, then k+1 is in S.
Suppose S ≠ N. Let T be the set of numbers that are not in S and T is not empty.
By the WOP, T contains the smallest element t. t cannot be 1, since 1∈S, t-1∈S.
However, the second hypothesis of MI tells us that t-1∈S, then t∈S.
Contradiction exists.
Thus, S = N.
2. MI⟹WOP
Want to show that any non-empty set of natural numbers containing a smallest
element.
S(n): any set of natural numbers containing a natural number ≤ n has a least
element.
S(1): Suppose S contains 1.
Since there is no natural numbers < 1, then 1 is the smallest element of S.
S(k): any set of natural numbers containing a number ≤ k, has a smallest element.
Let S be a set that contains a natural number ≤ k + 1.
Are there in S any natural numbers that are ≤ k. If yes, then S has a smallest
element by induction hypothesis; if no, then k+1∈S. Thus, k+1 is the smallest.
So, S(k) => S(k+1), proof is done by MI.
Generalized Principle of Mathematical Induction:
Let m be a natural number. If S is a set of natural numbers with the properties that:
A. m is in S, and
B. k+1 is in S, whenever k is in S and is greater than or equal to m,
then S contains every natural number greater than or equal to m.
Theorem 2.1.5: n! > 2 n for n ≥ 4.
Proof: use GPMI,
A. P(4): LHS = 4! = 24, RHS = 2 = 16. That is LHS>RHS.
B. Assuming the above formula is true, then assume
k
P k = k! > 2 , then
P k + 1 = k + 1 k! > k + 1 2 > 2 ∙ 2 = 2 k k+1, since k + 1 > 2.
k+1
That is P k + 1 = k + 1 ! > 2
Thus the statement holds for all n by GPMI.
Ex. Show that number of diagonals in a convex polygon of n sides is given by the formula
( ) n(n−3)
f n = 2 ,n ≥ 3
Proof: use GPMI
A. n = 3, f(3)

More
Less
Related notes for MAT246H1

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.