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

# MATH135 lecture 3.docx

5 Pages
86 Views

School
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
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.

Get notes from the top students in your class.

Request Course
Submit