Class Notes (836,052)
Canada (509,597)
Mathematics (1,919)
MATH 135 (334)
Lecture 3

MATH135 lecture 3.docx

5 Pages
86 Views
Unlock Document

Department
Mathematics
Course
MATH 135
Professor
Janelle Resch
Semester
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

Log In


OR

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