Study Guides (248,317)
Canada (121,484)
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
Unlock Document

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

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