Textbook Notes
(363,261)

United States
(204,477)

New York University
(916)

Math
(87)

MATH-UA 120
(1)

Ray Yang
(1)

Chapter

# Scheinerman full semester notes

Unlock Document

New York University

Math

MATH-UA 120

Ray Yang

Fall

Description

Kevin Jin 1
MATH-UA 120 Cumulative Notes
Direct proof of conjecture
o Convert conjecture to “If , then ”
o Write first statement of proof, “Let ”, and write last statement of proof, “Therefore, ”
o Unravel definitions in , putting them after first statement, and unravel definitions in ,
putting them before the last statement until nothing can be unraveled
o Glue the two ends together by doing some algebra and equivalencies and
Direct proof of “ if and only if ”
o Prove “If , then ” and “If , then ”
Proving a proof false is as simple as finding an example thaands
Combinatorial proof of
o “In how many ways …?”
o is one correct answer to the question.
o is another correct answer to the question.
o Therefore, .
o Example:
Let { }. How many nonempty subsets does have?
: Consider number of subsets of whose largest element is [ . Such
subsets are of the form }, where the other elements are chosen from
{ }. has subsets whose largest element is . Summing up
for all gives nonempty subsets of .
: has subsets if we disregard the empty set.
Boolean algebra
o : “not”, : “and”, : “or”
o ( ) ( ) ( )
( )
o
o These could be proved by truth tables for all combinations and ( of them)
List
o Ordered sequence of objects where repetition is permitted
o Ordered pairs are lists
o Multiplication principle: There are number of possibilities for a two element list
where there are choices for the first element andchoices for the second
o The number of lists of length whose elements are chosen from a pool of possibilities:
= {
( )
o ( ) ( )And by extension, ( )
o
Set
o Unordered sequence of objects where repetition is forbidden
o : “be in”/”be a member of”/”is a member of”/”is an element of”
o Set equality: ) ( )
o Subset:( ) ( ) Kevin Jin 2
MATH-UA 120 Cumulative Notes
o { }
o The number of subsets of | |
can either be in or not, has can be one of two states
o Power set: { }
| | | |
o Union: { }
o Intersection: { }
o Set difference: { }
Alternatively,
( )
DeMorgan’s Law:
( ) ( ) ( )
( ) ( ) ( )
o Symmetric set difference: ( ) ( )
( ) ( )
o Cartesian product: {( ) }
{ } { } {( ) ( ) ( ) ( )}
{ } { } {( ) ( ) ( ) ( )}
Not commutative
| | | | | |
o Disjoint:
Addition principle: If , then| | | | | |
o Inclusion-exclusion principle: | | | | | | |
o ( ) ( )
o
Quantifiers
o : “there exists”, : “for all”,: “there exists a unique”
o ( ) ( )
“for all , is ” = “there is a such that is not “
o ( ) ( )
“there is a such that is ” = “for all , is not “
o ( )
“there is a such that for all , is ” = “for all , there exists a such
that is not “
o ( )
“for all , there exists asuch that is ” = “there is a such that for all ,
is “
o ( )
“there exists and such that is A” = “for alland , is not “
Relations
o Relation: set of ordered pairs
E.g. {( ) ( ) ( )} Kevin Jin 3
MATH-UA 120 Cumulative Notes
( ) ( )
E.g. relation is equivalent to ) }
o Relation on :
All and are elements of
o Relation from to :
All are elements of and all are elements of
o Inverse relation: {( ) ( ) }
( )
o Properties:
Reflexive:( )
Irreflexive: ( )
is never reflexive
Symmetric: ( )
Antisymmetric: ( ( ) ( ))
is never symmetric, except if is reflexive and you’re doing
Transitive:(( ) )
o Equivalence relation: is reflexive, symmetric, and transitive
Example: Congruence modulo : ( ( )) ( |( ))
and differ by a multiple of
o Equivalence class of on : [ ] { }(provided )
[ ]
( ) ([ ] [ ])
[ ]
([ ] [ ] ) ([ ] [ ])
All equivalence classes of are nonempty, pairwise disjoint subsets of whose
union is
Partitions
o Partition of : set of nonempty, pairwise disjoint sets whose union is
The equivalence classes of form a partition
o Part: a set that is a member of a partition
Each part is a subset of , nonempty, and pairwise disjoint
The union of all parts is
o Is-in-the-same-part as: and are related provided there is some part of the partition
that contains both and
Equivalence relation
The equivalence classes of this relation are exactly the parts of the partition
o Counting equivalence classes: if all the equivalence classes of the equivalence relation
[ ]
have the same size, , then the number of equivalence classes is
o Example: How many rearrangements of “AARDVARK” are there?
Kevin Jin 4
MATH-UA 120 Cumulative Notes
|[ ]|
|[ ]|
|[ ]| |[ ]| |[ ]|
Answer:
| | |[ ]| |[ ]| |[ ]| |[ ]|
Binomial coefficients
o Binomial coefficient: when , ( ) is the number of element subsets of an -
element set
The thcoefficient of the expanded ( )
th th
The column in the row of Pascal’s triangle
( ) ( ) ( ) ( ) ∑ ( )
( ) ( ) for all with
( ) ( )
o Binomial theorem: ( ) ∑ ( )
th
The term is ( )
o Pascal’s identity: ( ) ( ) ( ) for all with
( )
o The sum of all elements in { } is
o ∑ ( ). Answer to “how many subsets can be formed from an -element set?”:
: because each member in the -element set can either be in or not be in
a subset.
Let be the largest element in a subset of length , i.e. { }where the
other ( ) elements have a value less than . ( ) is the number of
possibilities of{ } when the other ( ) elements are chosen from a pool
of distinct possible values. The sum of all ( ), from to , is the
total number of subsets that can be made from elements.
Therefore .
Inclusion-exclusion
o Extends | | | | | | | |for an arbitrary number of sets
o is equivalent to ( ) is equivalent to ( )
o | |
| | | | | |
| | | | | | | | | |
| | | |
( ) | |
Basically, add sizes of all intersections of one set, subtract sizes of all
intersections of two sets, add sizes of all intersections of three sets, subtract
sizes of all intersections of four sets, etc. Kevin Jin 5
MATH-UA 120 Cumulative Notes
th
First row has terms, second row has ( ), row has ( ) terms
Condensed: |⋃ | ∑ ( ) ∑ ⋂ |
o Proof template:
Classify objects as either “good” (do count) or “bad” (don’t count)
Decide either count number of “good” objects directly or subtract number of
“bad” objects from total number of objects
Cast the counting problem as the size of the union of sets. Each set describes
one way the objects might be “good” or “bad”
Use inclusion-exclusion
o Example: How many length- lists use all elements in { }at least once?
Good lists are those who use all elements in the set at least once
( ) ( )
Let be the set of all lists of lengtthat do not contain the element . The
set is the set of all bad lists.
Observe each , , has( ) elements and there are number of
s, so| | | | | | ( ) . Observe each has
( ) elements and there are ( ) possible pairing, so| |
th
| | ( ) ( ) . We see a pattern of ( )( ) for the row in
the inclusion-exclusion formula.
Therefore | | ∑ ( ) ( ) ( ) .
(( ) ( ) ( ) ( ) ( ) ( ) ( ) )
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
∑ ( ) ( ) ( )
o Derangement: list of length- without repetition using elements of { } where the
th
value does not occupy the position of the list, .
( )
There are ∑ derangements of length Kevin Jin 6
MATH-UA 120 Cumulative 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 7
MATH-UA 120 Cumulative 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 set and 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 Ignore and substitute in recurrence function
o Multiply both sides by
o Solve the quadratic
( ) √( ) ( ) √
( ) √( ) ( ) √
If then
o General form:
Find and
Kevin Jin 8
MATH-UA 120 Cumulative Notes
( )
if then
o General form:
Find and
If then
o Evaluate
o General form:
Find , , and
[ | ]
if
o Evaluate
o General form:
Find , , and
[ | ]
o Josephus’s problem: , , . is the size of the circle
and is the guy who survives. , Kevin Jin 9
MATH-UA 120 Cumulative Notes
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
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 ) ( ) Kevin Jin 10
MATH-UA 120 Cumulative Notes
is a function if and only ifis injective
and
For function

More
Less
Related notes for MATH-UA 120