false

Class Notes
(836,052)

Canada
(509,597)

University of Waterloo
(18,569)

Mathematics
(1,919)

MATH 135
(334)

Janelle Resch
(5)

Lecture 3

Unlock Document

Mathematics

MATH 135

Janelle Resch

Fall

Description

MATH135 week 3 Induction, Proving Implications, Divisibility, Sept. 23, 2013
Division Algorithm, GCD
Principle of Strong Mathematical Induction (PSMI)
Let P(n) be a statement that depends on nEZ +
If 1. P(1), P(2), …, (Pb) are true and
≥
2. k b and P(1), …, P(k) are true
P(k+1) is true
Then P(n) is true ∀ nEZ +
Ex: If {xn} is a sequence, define recursively by 1 =1, 2 =3, n =2n-1xn-2for n ≥ 3 then x n2n-1
∀ nEZ +
ASIDE: To prove…
Base Case – verify that P(1), …, P(b) is true
Inductive Hypothesis – Assume P(k) is true k ≥ b
Inductive Conclusion – Using assumption that (P1), …, P(b) are true, show that
P(k+1) is
True (must explicitly state the ind. hypothesis and
conclusion)
Proof: Let P(n) be the statement above. We want to induct over x =2n-1, n ≥ 3
Base Case: Let n=1, then x =nn-1
x =2(1)-1
1
X 11
Now let n=2, then x n2n-1
x2=2(2)-1
X 23
Thus, P(1), P(2) are true
Inductive Hypothesis: Assume x=2ii1 is true ∀ iE[1, …, k]
≥
So, *xk=2k-1, k 2
Inductive Conclusion: Let n=k+1
We want to prove that
x(k+1)(k+1)-1
xk+1k+1
So xk+1x -k k-1
By *x =2(2k-1)-[2(k-1)-1]
k+1
Xk+1(2k-1)-(2k-3)
Xk+1k+1
P(k+1) is true.
Thus, by PMI, P(n) is true for n ≥ 3 MATH135 week 3 Induction, Proving Implications, Divisibility, Sept. 23, 2013
Division Algorithm, GCD
≥
Ex: Let the sequence be defined by x =0, x 130 an2 x =x +6x m m-1 m-2for m 3
n n ≥
Then x =n(3 )+3(-2) for n 1
Proof: Let P(n) be x =2n3 )+3(-2) , for n ≥ 1
Base case: Let n=1
Then x =n(3 )+3(-2) n
1 1
x1=2(3 )+3(-2)
X =0
1
Now let n=2
n n
Then x =n(3) +3(-2)
x2=2(3) +3(-2) 2
X 230
Thus P(1) and P(2) are true
Inductive Hypothesis: Assume that;
i I ∀ ≥
xi2(3)+3(-2) is true iE[1, …, k], k 2
k k
So *x k2(3) +3(-2)
Inductive Conclusion: Let n=k+1, we want to prove that x =2(3 )+3k+1) k+1 k+1
So, x k+1 (k+1)-1x (k+1)-2)
X k+1+6k k-1
By *x k+1(3) +3(-2) )+6(2(3) +3(-2) ) k-1
k K K-1 K-1
xk+1(3) +3(-2) +2(2)(3 )(3)+3(3)(-2) (2)
K 2 K K 2 K -1 1
X +1=2(3) +2 (3) +3(-2) +3 (-2) (-2) (2)
X +1=2(3) (1+2)+3(-2) (1+3(-1))
K K
X +1=2(3 )(3)+3(-2) (-2)
K+1 K+1
X +1=2(3) +3(-2)
P( K+1) is true
Thus, by PSMI, P(n) is true ∀ n ≥ 1
∃
DEFINTION: An integer n divides an integer m

More
Less
Related notes for MATH 135

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.