CISC 102 Lecture Notes - Lecture 30: Mathematical Induction, Complex Instruction Set Computing

62 views3 pages

cerisegiraffe538

6 Dec 2017

School

Department

Course

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

bronzeskunk641 and 150 others unlocked

CISC 102 Full Course Notes

Verified Note

34 documents

Document Summary

An informal proof of this result could be that either a or a+1 must be divisible by 2, so their product must also be divisible by 2. however, we have seen a similar template" for proving this result. Familiar facts from high school math, as well as results that we have seen this term and used repeatedly can be assumed without further proof. In practice for a course like this there is usually a very similar proof that you have seen that can be used as a template. and this will implicitly use assumptions that you may use. Proof by cases: prove that 2|a(a+1) for all natural numbers a, prove that 3|a(a+1)(a+2) for all natural numbers a. 3|a, so by result 1. 2|(a+1)(a+2). so 6|a(a+1)(a+2). Proof: who have met or not met x. Amongst those who have met x, at least one pair have met each other. since.

Related Questions

Complete problem 3 using the information above.

Math 151 Sections 34, 35, 36 Workshop 11 ted to arn This workshop deals with an addition formula in section 5.1. This formula is rel oft told story about the great mathematician Gauss. Here is one version of the story When Gauss was ten years old, he attended a certain math class with other kids. One fine day, the math teacher discovered that he was running out of time to grade the latest batch of math homeworks. This is why he decided to finish the grading during his math period. To keep the students busy while he graded, he gave them the following task at th of the period: Use your slate (the small personal blackboard that every student had start in class) to add up the numbers 1,2,3,... , 100 Seconds after the teacher gave this in-class assignment, little Gauss pointed to his slate Here is the answer." Then Gauss did nothing for an hour, while the other students labored with the additions and the teacher graded. At the end of the perioc Gauss showed the correct answer 5050 on his slate. Only Gauss got the correct answer. Then Gauss told everybody that the sum 12 +3.+ 100 is (1+100)+(2+99) + (3498)+ Problem 1. Explain carefully what Gauss had done. Include the reason why it is impor tant that 100 happens to be an even number Problem 2. Let N be an even positive integer. Use the method of Problem 1 to prove the formula 1 +2 +3+.. . +N(N. Include the reason why it is important that N +(50+51) = 101 + 101 +101 + +101-101.50-5050 an even number. Problem 3. The formula is still valid when N is an odd integer. Prove this, using a variation on the argument given by Gauss The story continues: Gauss then gave the class a lecture on how his method could be used to sum an arithmeric series (a +1.b) (a +2.b) (a +3.b)+. (a +N b), where a and b are constants Problem 4. Find a formula for the sum (a+1.b)+ (a+2.b) + (a +3.b)+ +(a+ N.b) Prove this formula the way Gauss would have done it. You have to do the case when N is even and the case when N is odd Now let us consider a fictional alternate history where Gauss had not thought of this very clever trick. We can imagine the ten year old Gauss going home and doing the sequential computations 1+2 1+2+3 1+2+3+4 1+2+3+4+5 and so forth, just to see if he could find a pattern in the sequence of answers. He would have discovered somethin like this: once he had the sum 1+2+3+...+ N, he could simply add N +1 to that sum and that would give him the sum 1+2+3+ + (N +1) very quickly Now ass N(N+1 ume that, by trial and error, Gauss discovered that the formula 1+2+3+ is true for several values of N. How could he prove that the formula is r for ALL N? The insight described in the previous paragraph might have led Gauss to other words, he only needed to show: Formula for 1+2+3+ + N plus N +1 equals formula for 1+2+3++N+1). He would have discovered the principle of mathema -.. + N eally true 1)+1) think the following: All he had to do was prove mm) + (N + 1) NN+1 (N+1)(( In ered the principle of mathematical induction Problem 5. Prove N(N+1) (N + 1 of the formula for 1+2+3+.+N. (Nt1MNHHI) Show how this leads to a uCtion a proof

Problem 3

Math 151 - Sections 34, 35, 36 - Workshop 11 This workshop deals with an addition formula in section 5.1. This formula is related to an ld story about the great mathematician Gauss. Here is one version of the story Wh en Gauss was ten years old, he attended a certain math class with other kids. One fine day, the math teacher discovered that he was running out of time to grade the latest batch of math homeworks. This is why he decided to finish the grading during his math lecture period. To keep the students busy while he graded, he gave them the following task at the start of the period: Use your slate (the small personal blackboard that every student had in class) to add up the numbers 1,2,3,... , 100 Seconds after the teacher gave this in-class assignment, little Gauss pointed to his slate and yelled "Here is the answer." Then Gauss did nothing for an hour, while the other students labored with the additions and the teacher graded. At the end of the period Gauss showed the correct answer 5050 on his slate. Only Gauss got the correct answer Then Gauss told everybody that the sum 1+2+3+ + 100 is ( 1 + 100) + (2+99)+ (2+98)+--+ (50+51) = 101 + 101 + 101 +. . . +10 101. 50-5050 Problem 1. Explain carefully what Gauss had done. Include the reason why it is impor tant that 100 happens to be Problem 2. Let N be an even positive integer. Use the method of Problem 1 to prov the formula 1 +2+3+.+N) be an even number Problem 3. The formula is still valid when N is an odd integer. Prove this, using a variation on the argument given by Gauss The story continues: Gauss then gave the class a lecture on how his method could be used to sum an arithmeric series (a+1.b) + (a+2 b) + (a+3.b)+. + (a + N b), where a and b are constants Problem 4. Find a formula for the sum (a+1.b)+(a+2.b)+ (a +3.b)+(a+ N b) Prove this formula the way Gauss would have done it. You have to do the case when N is even and the case when N is odd Now let us consider a fictional alternate history where Gauss had not thought of this ve clever trick. We can imagine the ten year old Gauss going home and doing the sequential computations 1+2 1+2+3 1+2+3+4 1+2+3+4+5 and so forth, just to see if he could find a pattern in the sequence of answers. He would have discovered somethin like this: once he had the sum 1+2+3++N, he could simply add N+1 to that sum, and that would give him the sum 1+2+3 Now assume that, by trial and error, Gauss discovered that the formula 1+2+3+ +N an even numbe +) Include the reason why it is important that +Â·Â·Â· + (N +1) very quickly is true for several values of N. How could he prove that the formula is really true for ALL N? The insight described in the previous paragraph might have led Gauss to think the following: All he had to do was prove N(N+1) Â± (N + 1) other words, he only needed to show: Formula for 1 + 2+3+.+ N plus N +1 equals formula for 1+2+3+(N+1). He would have discovered the principle of mathematical induction Problem 5. Prove of the formula for 1+2 +3+... + N (N +1)(+1X++1) Show how this leads to a proof N(N+1 N+)

ey table is seen below xeecions tor Chapter 1 12, Fori, b â¬ Î.el * b-aa (0 (D 14 ForVEQ r the operation defined in Example 1 on the wr John Sue Henry. P iDFor 15ine if is ass ociative by determining if the final six engu defined ang property (ii)of Theorem 1 . So no element i if the operntion debined in Example 1 of Emle if each element has an inverse Section 1.3 Groups iw comutatityn ild Chapter 3 where the Funda the exercises that follow etermining why they are not Write out the Cayley table for the gru(o)nud lensify thee element the 10 elements of the group Z 18 its operation uses ts in the first coordinnte and +2 in the secotu Ldessity the Zn and write out the Cayley table. Reeall th of each element does Theorem 1.14 tell us aont the entries in the Cayley table ol s xrewp that is set with exactly one element. A {n), will always form group since there 19. What nly one way to define an operation on the set. Be sure to shhow that the properi combination of the usual notice what set the rule is be of a group all hold. 21. We can create even create groupe with games! Consider four cups placed in a ssare patter table. If we have a penny in one of the cups there are four ways we can move it to t cup: Horizontally, Vertically, Diagonally, or Stay nehere it is. We will p, S. To define nn operation, consider two movements in a row, v.e.,m ove the penny as r tells us to, then after that move the penny as y instruets. the set of integers the set of real numbers n the set of positive integers. e set of positive integers. n the set of positive integers. on the set of integers e set of negative integers. we ple, HV D since if we first move it horizontally and then vertically nltogether e moved it diagonally. Create the Cayley table for this group, identify the identity and the inverse of cach element 22. Prove that the set A 0 under matrix multiplication. Is it abelian? 23. Verify that 3(R) is a group using the addition of funetions as defined in Example 13 e set of nonzero rational n he set of nonzero real num n on the set R (-1 Section 1.4 Basic Algebra in Groups 24. Prove the Cancellation Law (Theorem 1.20). Do not use any theorems that occur after it in the text ssociative, commutative, has roof or counterexample fo 25. Assume G is a group and a e G. Consider a fixed integer k and use PMI (Theorem 0.3) to prove that for all nEN, a aYou will need to consider cases here since k can be positive, negative, or o 26. Prove Theorem 1.23 (ii) for the case of n > 0 and m

CISC 102 Lecture Notes - Lecture 30: Mathematical Induction, Complex Instruction Set Computing

CISC 102 Full Course Notes

Document Summary

Get access

Related Documents

CISC 102 Lecture Notes - Lecture 11: Natural Number, Complex Instruction Set Computing, Modular Arithmetic

CISC 102 Lecture Notes - Lecture 9: Mathematical Induction, Complex Instruction Set Computing

CISC 102 Lecture Notes - Lecture 8: Mathematical Induction, Complex Instruction Set Computing

Related Questions