Math 201 §C: Objectives for Second Midterm Exam
This document incorporates the Objectives for the
First Midterm Exam.
Induction
- State the definitions and use them in proofs.
- The set N of natural numbers.
- A sequence.
- A zero of a function.
- Polynomial; degree of a polynomial.
- Binomial coefficient
- State the theorems and use them in proofs.
- The Principle of Induction.
- Factorization of xn-yn.
- The Geometric Sum
- Every polynomial of degree d has at most d zeros.
- Strong induction principle.
- Well-ordering property.
- Pascal Triangle rule for binomial coefficients
- The number of k-subsets of an n-set is binomial(n,k).
- Factorial formula for binomial coefficients.
-
- Apply techniques of proof and of computation.
- Proof by induction.
- Proof by strong induction.
- Proof by the method of descent.
- Use sigma-notation to represent sums.
- Rename the index.
- Shift the index.
Cardinality
- State the definitions and use them in proofs.
- Base q representation of natural numbers.
- Bijection; injection; surjection.
- Inverse of a bijection.
- Binary encoding of subsets of [n].
- Composition of functions.
- Finite set; infinite set; size of a set.
- Countable set; uncountable set.
- Sets A and B have the same cardinality
if there is a bijection from A to B.
-
- State the theorems and use them in proofs.
- Every natural number has a unique base q
representation with no leading zeros.
- Strictly monotone functions from R to R are injective.
- The composition of two injections, surjections or bijections
is, respectively, an injection, surjection or bijection.
- Composition of functions is associative.
- If there is a bijection f: [m] → [n], then m=n.
- The sets N and N × N have the
same cardinality.
- Schroeder-Bernstein Theorem
- Skills and computations
- Given natural number n and base q,
find the base-q representation of n.
