Scheinerman textbook sections 20-27, 29, 35-37

9 Pages
138 Views
Unlock Document

Department
Math
Course
MATH-UA 120
Professor
Ray Yang
Semester
Fall

Description
Kevin Jin 1 MATH-UA 120 Exam 2 Notes  Proof by contrapositive of “If , then ” o o Assume . …show is false… Therefore .  Proof by contradiction of “If , then ” combines direct proof and proof by contrapositive o o Assume . Suppose, for the sake of contradiction, . …show that there is a contradiction… . Therefore .  Proof by smallest counterexample of “If , then ” for is a specialized form of proof by contradiction o if and only if there is no counterexample i.e. o …Let the smallest number that would make sense in the problem, e.g. when working with indices, for all natural numbers, 5 if problem says , or 1 if problem says … Assume . Suppose, for the sake of contradiction, . Let * +, i.e. be the set of counterexamples to . Since we have supposed , . By the Well-Ordering Principle, contains a least element (i.e. is the smallest counterexample to ). We know that because is true for (rule out being the very smallest possibility). Thus, . Since , we see that is a natural number and smaller than and therefore is (consider an just smaller than , i.e. , and show that is ). …Manipulate the expression for so that is in there, e.g. add one to the result or substitute like in induction, and show that is also so that there is a contradiction… We find that is also true for although we supposed earlier that is true for .  Proof by induction of “If , then ” for is derived from proof by smallest counterexample o …Let the smallest number that would make sense in the problem, e.g. when working with indices, for all natural numbers, 5 if problem says , or 1 if problem says … Let * + Basis step: because… Inductive step: If then (by substituting identity forin ).  Proof by strong induction should be done when standard proof by induction does not suffice. Assumes all results before are true and not just result for o …Let the smallest number that would make sense in the problem, e.g. when working with indices, for all natural numbers, 5 if problem says , or 1 if problem says … Let * + Basis step: because… Inductive step: Assume result is true* + . Prove (by substituting identities for and ). Kevin Jin 2 MATH-UA 120 Exam 2 Notes o Useful for Fibonacci because standard induction only assumes is true when trying to prove , while Fibonacci needs and .  (Miscellaneous on sets) o To prove a set is empty: “Suppose, for the sake of contradiction, set is not empty. …” o To prove there is a unique element: “Suppose, for the sake of contradiction, two different objects , that satisfy the conditions. …” o Let be an equivalence relation on setand let . If , then| | | |  (Miscellaneous propositions) o , : exists unique with o No integer is both even and odd  Recurrence relations o First order:  Convert to closed form by formula, given : . /  Convert to closed form by solving system of equations, given:  Evaluate  General form: o Find and      o Second order:  Convert to closed form by solving system of equations, given and :  First find and o Substitute in recurrence function  o Multiply both sides by  o Solve the quadratic  √   √  General form: o If then Find and   Kevin Jin 3 MATH-UA 120 Exam 2 Notes   ( )  o if then Find and      o Second order:  Convert to closed form by solving system of equations, given and :  First find and o Forget and substitute in recurrence function  o Multiply both sides by  o Solve the quadratic  √  √   Evaluate  General form: o If then Find , , and        [ | ] o if Find , , and  Kevin Jin 4 MATH-UA 120 Exam 2 Notes       [ | ] o Josephus’s problem: , , . is the size of the circle and is the guy who survives. ,  Difference operator ( ) ( ) :: ( ) ∫ ( ) o Let be a sequence of numbers in which is given by a degree- polynomial in where . Then is a sequence given by a polynomial of degree  If a sequence is generated by a polynomial of degree , then is the all- zeros sequence o Derivative like properties;  ( )  ( ) o Let be a positive integer and . / . Then . / o Let and be sequences of numbers and let be a positive integer. Suppose that , , and , ) Then . o Let be a sequence of numbers. The terms can be expressed as polynomial expressions in if and only if there is a nonnegative integesuch that for all , we have . In this case, . / ( ). / ( ) . /  Basically, stop when  Functions ( ) ( ) o Function : Relation where  means is a function from to , or is a mapping from to  o Domain: * ( ) + * ( ) + o Codomain: , where is mapped to * + o Image: ( ) * ( ) + o One-to-one/injective: function is one-to-one if whenever( ) ( ) ,  Prove directly: Suppose ( ) ( ) … Therefore . Therefore is one-to- one  Prove by contrapositive: Suppose . … Therefore ( ) ( ). Therefore is one-to-one Kevin Jin 5 MATH-UA 120 Exam 2 Notes  Proof by contradiction: Suppose ( ) ( ) but . … . Therefore is one-to-one o Onto/surjective: function is onto if for every there is an where ( ) .  Prove directly: Let be an arbitrary element of . (show that there exists such that ( ) ) Therefore is onto.  Prove by set equality: (show that sets and are equal) o Bijective: is a bijection if it is both injective and surjective o Inverse function: for every ( ) ( )  is a function if and only ifis injective  and  For function , inverse relation is a function from to if and only if is bijective on
More Less

Related notes for MATH-UA 120

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