false

Study Guides
(248,269)

United States
(123,305)

New York University
(638)

Math
(12)

MATH-UA 120
(1)

Ray Yang
(1)

Unlock Document

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.