Study Guides (248,317)
Mathematics (302)
MATH 135 (50)
Midterm

# MATH 135 Algebra Notes III (Sept 23 - Sept 27): Inductions, (little on Divisibility), Greatest Common Divisor

5 Pages
95 Views

School
Department
Mathematics
Course
MATH 135
Professor
Wentang Kuo
Semester
Fall

Description
MATH 135: Algebra for Honours Mathematics Notes III Michael Brock Li Computational Mathematics 1A September MXIII Concordia Cum Veritate I: Induction: Simple and Strong Induction The Sum Notation, denoted as ▯ is the sum of all numbers within the range from the bottom of the sigma notation to the top of the sigma notation. Example I: 10 P 2 2 2 2 2 i = 1 + 2 + 3 + ::: + 10 i=1 i: Summation Principles I: n n X X ci = c xi i=m i=m II: Xn Xn X x ▯ y = (x ▯ y ) i i i i i=m i=m i=m III: n n+k X X xi= xj▯k i=m j=m+k ii: Principle of Mathematic Induction Let P(n) be a statement that depends on n. If I: P(1) is true (the Base Case) 1 II: Inductive Hypothesis: If P(k) is true implies... III: Inductive Conclusion: P(k + 1) is true. then P(n) is true for all n 2 N. Example I: 2 2 2 P 2 n(n+1)(2n+1) Prove: 1 + 2 + ::: + n = i = 6 for all n 2 N i=1 Proof. Base Case: 1 X 2 1(1 + 1)(2(1) + 1) P(1) : L:H:S: = i = = 1 i=1 6 Inductive Hypothesis: Let’s assume that the statement P(k) is true for some k ▯ 1;k 2 N k X 2 k(k + 1)(2k + 1) i = i=1 6 Inductive Conclusion: Let’s show that P(k + 1) is true X+1 Xk i = i + (k + 1) i=1 i=1 k(k + 1)(2k + 1) 2 = + (k + 1) 6 [(2k + k) + 6(k + 1)] = (k + 1) 6 With expanding and factoring, we get [(k + 2)(2k + 3)] = (k + 1) 6 (k + 1)[((k + 1) + 1)(2(k + 1) + 1)] = 6 Thus P(k + 1) is true. By Principles of Mathematics Induction, P(n) is true for all n 2 N ▯ 2 III: Principal of Strong Induction Let P(n) be a statement that depends on n. If I: P(1) is true (the Base Case) II: Inductive Hypothesis: If P(1);P(2);:::P(k) is true implies... III: Inductive Conclusion: P(k + 1) is true. then P(n) is true for all n 2 N. Example I: Let x1= 0; x 2 30. For n ▯ 3; x =nx n▯1 + 6xn▯2 . n n Prove that xn= 2(3) + 3(▯2) ; n ▯ 1 Proof. Base Case: n = 1 L:H:S: = 0;R:H:S: = 2(3) + 3(▯2) = 0 n = 2 L:H:S: = 30;R:H:S: = 2(3) + 3(▯2) = 30 Inductive Hypothesis: Assume that 1 ▯ i ▯ k is true xk= x k▯1 + 6x k▯2; k ▯ 2 Inductive Conclusion: Let n = k + 1; k ▯ 2 xk+1 = x k 6x k▯1 k
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.