STOR 215

Study Guide for Midterm 2: Version 3 November

Sequences: recurrence relations vs. closed form descriptions, completing sequences

Summations: multiple sums, formulas for geometric series, sum of 1 up to n

Cardinality of sets: finite, countably infinite, and uncountably infinite

The division algorithm: integers modulo m

Modular arithmetic: basic properties

Primes, greatest common divisors, least common multiples

The fundamental theorem of arithmetic

The Euclidean algorithm

Bezout's Theorem

Induction: basic principle, and method of proof

Examples of proofs by induction

Strong induction

Basic rules of counting: product rule, sum rule, and inclusion-exclusion

The pigeon hole principle and applications

Permutations and combinations: factorial representations, basic properties of binomial coefficients

The binomial theorem

Identities for binomial coefficients: Pascal and Vandermonde, combinatorial proofs

Permutations and combinations with repetition.

Distinguishable objects and distinguishable boxes

Indistinguishable objects and distinguishable boxes

Basic definitions for graphs: vertex, edge, directed and undirected graphs

Degree: Handshaking theorem and corollaries