Problem-solving recipes

A step-by-step procedure for every problem type this course teaches — what to do first, what to do next, and how to tell which case you're in.

What are you being asked to do?

Start with what you're actually being asked to produce.

A division or a sum/product to evaluate — readiness review: apply the division algorithm, or expand a sum or product written in index notation.

A compound proposition — build its truth table, or classify it as a tautology, contradiction, or contingency once you have one.

A quantified statement — find a predicate's truth set, check a universal claim, decide an existential claim, or evaluate a nested quantifier statement.

A claim to prove or disprove — disprove a universal claim with a counterexample, or prove a unique-existence claim.

A claim about every natural number at or above some starting value — prove it by mathematical induction, by strong induction if the inductive step needs more than the single immediately preceding case, or using the well-ordering principle if assuming a least counterexample is the more natural move.

Two sets, or one claimed relationship between them — check whether $A \subseteq B$ , prove set equality by double inclusion, find a union, intersection, or difference, find a complement, simplify with set identities, or prove an identity by element-chasing.

A function — find its domain/codomain/range, test one-to-one or onto, compute a composition, find an inverse, evaluate floor/ceiling, compute an image or preimage, or find where one function eventually dominates another.

A relation given as a list of pairs — classify it as reflexive or irreflexive, symmetric or antisymmetric, test transitivity, compute a composite of two relations, or find its equivalence classes.

A sequence or recurrence — evaluate a recursive definition, solve a linear homogeneous recurrence, or derive and solve a recursive algorithm's running-time recurrence.

A counting problem with an added condition — count a selection with a restriction, write a combinatorial proof of a counting identity, or apply the pigeonhole principle to guarantee a repeat exists.

A claim that one function grows no faster than another — prove a Big-O bound directly from its definition.

A graph — apply the handshaking theorem, or determine whether it has a cycle.

A tree — test whether its counts are consistent with a tree, find a vertex's parent/children/level/height, classify a binary tree, or find a minimum spanning tree by removing costliest cycle edges.

A loop, or a random variable — check a loop's total correctness, or compute expected value by summing over outcomes.

Readiness

Apply the Division Algorithm

Use when: you're given integers $a$ and $b$ , with $b$ positive, and need the quotient $q$ and remainder $r$ satisfying $a = bq + r$

Goal: the one pair of integers $q$ and $r$ with $0 \le r < b$

Divisibility, parity, and remainders

Expand a sum or product written in index notation

Use when: you see a sigma or pi symbol with a lower limit, an upper limit, and a formula for the general term

Goal: the fully written-out list of terms, ready to add or multiply by hand

Summation and product notation

Logic and propositions

Build a truth table for a compound proposition

Use when: you have a compound proposition with two or more atoms and need its truth value under every possible assignment

Goal: a complete table listing the formula's truth value on every row

Truth tables

Classify a formula as a tautology, contradiction, or contingency

Use when: you have a compound proposition and need to know whether it's always true, always false, or true on some rows and false on others

Goal: one of the three labels, backed by the formula's full truth table

Tautologies, contradictions, and contingencies

Needs a truth table built first, from the recipe above.

Predicate logic

Find the truth set of a predicate

Use when: you're given a predicate $P(x)$ and a finite, listable domain, and asked which elements make $P(x)$ true

Goal: the complete truth set, the subset of the domain where the predicate actually holds

Predicates and truth sets

Check a universal claim over a finite domain

Use when: you're given $\forall x\, P(x)$ over a finite, listable domain and must decide whether it's true

Goal: a settled verdict: true only if every domain element checks out, false the moment one counterexample turns up

The universal quantifier

Decide an existential claim over a finite domain

Use when: you're given $\exists x\, P(x)$ over a finite, listable domain and must decide whether it's true

Goal: a settled verdict: true with one witness in hand, or false only after every domain element has been ruled out

The existential quantifier

Evaluate a nested quantifier statement

Use when: you have a statement with two quantifiers, such as $\forall x\, \exists y\, P(x,y)$ , over finite domains, and need a verdict

Goal: a settled verdict for the whole statement, found by resolving the inner quantifier separately for each fixed outer value

Nested quantifiers

Combines the universal and existential recipes above, one quantifier at a time.

Methods of proof

Disprove a universal claim with a counterexample

Use when: you suspect $\forall x\, P(x)$ is false and need to produce one object that breaks it

Goal: one verified counterexample: an object the claim is actually about, where the claim's conclusion fails

Counterexamples and disproof

Prove a unique-existence claim

Use when: you must show $\exists! x, P(x)$ : exactly one object satisfies $P$ , not just at least one

Goal: both halves established together: one object satisfying $P$ , and a proof no second, different object could

Uniqueness proofs

Mathematical induction

Prove a statement by mathematical induction

Use when: you need to establish a claim P(n) for every integer n starting at some fixed n0, and each new case only ever depends on the single case right before it

Goal: a complete proof establishing P(n) for every n at or above n0, with both obligations verified

Anatomy of an induction proof

Prove a claim by strong induction

Use when: the inductive step for P(k+1) needs more than P(k) alone, such as splitting k+1 into two smaller, unpredictable pieces, or a recurrence referencing more than one prior term

Goal: a complete proof establishing P(n) for every n at or above n0, using the full strong inductive hypothesis

Strong induction

Needed when the inductive step reaches back further than the single immediately preceding case.

Prove a claim using the well-ordering principle

Use when: you want to show a property holds for every natural number at or above n0, and assuming a counterexample would hand you a concrete smallest case to work with

Goal: a proof that no counterexample to the claim exists, built from well-ordering's guaranteed least element

The well-ordering principle

An alternative to induction, built from a least-counterexample argument instead.

Set theory

Check whether A is a subset of B

Use when: you're given two sets $A$ and $B$ and must decide whether $A \subseteq B$ , and if so, whether it's proper

Goal: a settled verdict on $A \subseteq B$ , plus whether it's proper, backed by a full element check or one counterexample

Subsets and proper subsets

Prove set equality by double inclusion

Use when: you must prove $A=B$ for sets described by a rule, where listing and comparing every element isn't possible

Goal: both subset directions established, together showing $A=B$

Set equality and double inclusion

Runs the subset check above in both directions.

Find a union, intersection, or difference

Use when: you're given two sets by their elements and asked for $A \cup B$ , $A \cap B$ , or $A \setminus B$

Goal: the exact resulting set, with no duplicate elements and the right direction if it's a difference

Union, intersection, difference

Find the complement of a set

Use when: you're given a set A and a universal set U, either stated or clear from context, and asked for A's complement

Goal: the exact set of elements of U that are not in A

Complement and the universal set

Simplify a set expression using identities

Use when: you have a set expression built from union, intersection, complement, or difference that a named identity can shorten

Goal: an equivalent, shorter expression, with each rewrite justified by the identity's name

Set identities

Prove a set identity by element-chasing

Use when: you need to prove two set expressions are equal and no shortcut identity already covers the claim directly

Goal: a two-direction proof that every element of the left side lands in the right side, and every element of the right side lands in the left

Proving set identities two ways

A second way to prove the same kind of claim as double inclusion, argued element by element.

Functions

Find the domain, codomain, and range of a function

Use when: you're given a function in $f: A \to B$ notation, with a rule, and asked for its domain, codomain, and range

Goal: the domain and codomain read off the notation, plus the range computed from the rule and checked against the codomain

Domain, codomain, range, image

Test whether a function is one-to-one

Use when: you're given $f: A \to B$ by a formula or an explicit list of pairs and asked whether it's one-to-one (injective)

Goal: either a general derivation showing $f(a_1) = f(a_2)$ forces $a_1 = a_2$ , or one explicit counterexample pair disproving it

One-to-one functions

Test whether a function is onto

Use when: you're given $f: A \to B$ and asked whether it's onto (surjective), meaning every element of the codomain actually gets produced

Goal: either a construction showing an input exists for every element of the codomain, or one specific codomain element no input reaches

Onto functions

Compute a function composition

Use when: you're given f and g and asked to evaluate or simplify $g \circ f$ or $f \circ g$ , at a number or as a general formula

Goal: the correct output or formula for the composite, with its domain checked, not just the algebra carried out

Function composition

Find the inverse of a function

Use when: you're given a function f and asked to find its inverse f^{-1}

Goal: the inverse function's formula, or a clear reason no inverse function exists

Inverse functions

Needs one-to-one and onto confirmed first, from the two recipes above.

Evaluate floor and ceiling of a real number

Use when: you need $\lfloor x \rfloor$ or $\lceil x \rceil$ for one specific real number x, especially a negative one

Goal: the exact integer values of floor(x) and ceiling(x), without a sign error

Floor and ceiling

Compute the image or preimage of a set under a function

Use when: you're given a function f and a subset of its domain or codomain, and asked for f(S) or f^{-1}(T)

Goal: the exact set f(S) or f^{-1}(T), built element by element

Images and preimages of sets

Find where one function eventually dominates another

Use when: you're given two functions f and g and asked whether one stays ahead of the other forever, past some point

Goal: the crossover point N beyond which f(n) >= g(n) for every n >= N, or a reason no search is needed

Growth of functions: a first look

Relations

Classify a relation as reflexive, irreflexive, or neither

Use when: you're given a relation R on a set A and asked whether every, no, or only some elements relate to themselves

Goal: the correct label -- reflexive, irreflexive, or neither -- with the specific pair that proves it

Reflexive and irreflexive

Classify a relation as symmetric or antisymmetric

Use when: you're given a relation R on a set A and asked whether every arrow has a return arrow, no distinct pair does, or both

Goal: the correct symmetric and antisymmetric labels, with the specific pair that proves or disproves each one

Symmetric and antisymmetric

Test a relation for transitivity

Use when: you're given a relation R on a set A and asked whether every two-step chain already has its shortcut pair in R

Goal: an answer, backed by either a complete check of every chain or one specific broken chain

Transitive relations

Compute the composite of two relations

Use when: you're given R from A to B and S from B to C, and asked for the composite S∘R

Goal: the full list of pairs (a,c) reachable by an R-step into B followed by an S-step out of B

Combining and composing relations

Find the equivalence classes of a relation

Use when: you have a confirmed equivalence relation on a set and need to sort every element into its class

Goal: every equivalence class the relation produces, each one written exactly rather than by a partial sample

Equivalence classes

Assumes the relation already passed the three property tests above.

Sequences and recurrence

Evaluate a recursive definition at a given input

Use when: you're given a base case plus a recursive rule and asked for the value at one specific input

Goal: the definition's exact value at that input, reached by unwinding down to the base case and substituting back up

Recursive definitions

Solve a linear homogeneous recurrence

Use when: you have a recurrence where every term is a first-power multiple of some $a_{n-k}$ , with no added constant, plus two initial conditions

Goal: an explicit formula for $a_n$ , built from the characteristic equation's roots and matching both initial conditions

Linear homogeneous recurrences

Derive and solve a recursive algorithm's running-time recurrence

Use when: you're given a recursive algorithm's code or description and asked how its running time grows with the input size $n$

Goal: a running-time recurrence $T(n)$ , solved directly or matched to a growth rate already known

Recursion in algorithms

Often solved with the same characteristic-root method as the recipe above.

Counting principles

Count a selection with a restriction

Use when: a counting problem adds an extra condition, such as a required element, a forbidden or required adjacency, or an order constraint, on top of an otherwise ordinary product, permutation, or combination count

Goal: the count of arrangements or selections that satisfy the restriction, built from the ordinary counting tools plus one targeted fix

Counting with restrictions

Write a combinatorial proof of a counting identity

Use when: you need to prove an identity between two counting expressions holds for every valid input, not just check it for one number

Goal: a proof that both sides of the identity count the exact same collection, so they must be equal

Combinatorial proof

Apply the pigeonhole principle

Use when: you need to show some repeat, collision, or shared property must exist among a group, without needing to identify which specific items collide

Goal: a proof that at least one box must hold more than one object, forcing the guaranteed repeat to exist

The pigeonhole principle

Introduction to graph theory

Apply the handshaking theorem

Use when: you're given some vertex degrees, or an edge count, of a graph and asked to verify a total or find one missing degree

Goal: either a confirmed match between the degree sum and $2|E|$ , or the one missing degree that makes it match

The handshaking theorem

Determine whether a graph has a cycle

Use when: you have a small graph's edge list and need to know whether it contains a cycle, or how short the shortest one is

Goal: either a shortest cycle traced vertex by vertex, or a solid reason none exists

Cycles

Trees

Test whether vertex and edge counts are consistent with a tree

Use when: you know a connected graph's vertex count and edge count and need to decide whether they are consistent with the graph being a tree

Goal: a verdict on whether the counts rule out a tree, confirm the necessary count, or still require a direct check

Properties of trees

Find parent, children, level, and height in a rooted tree

Use when: you're given a rooted tree and asked to name a vertex's parent, children, or ancestors, its level, or the tree's height

Goal: every relationship and level value read directly off the tree, with no guessing

Rooted trees

Classify a binary tree as full, perfect, or complete

Use when: you're given a specific binary tree's shape and asked whether it's full, perfect, or complete

Goal: a correct classification, backed by the specific vertex or level that fails whichever test it fails

Binary trees

Find a minimum spanning tree by removing costliest cycle edges

Use when: you have a connected, weighted graph and need its cheapest spanning tree

Goal: a spanning tree using only the graph's own edges, connecting every vertex at the lowest possible total weight

Spanning trees

Introduction to algorithms

Check whether a loop is totally correct

Use when: you're given a loop and asked whether it terminates, whether its output is correct, or both

Goal: a verdict on termination, a verdict on correctness, and the variant or counterexample that backs each one up

Correctness and termination

Asymptotic analysis

Prove a Big-O bound from the definition

Use when: you're given two functions f(n) and g(n) and asked to prove f(n)=O(g(n)) directly, by exhibiting witnesses, rather than just stating the bound

Goal: a specific constant c>0 and threshold n0, verified to satisfy f(n) <= c*g(n) for every n >= n0

Proving a Big-O bound

Discrete probability fundamentals

Compute E(X) using the outcome-sum definition

Use when: you know every outcome's probability and need E(X), especially when several outcomes share the same X-value

Goal: the value of $E(X)$ , computed outcome by outcome and checked against the table method

Expected value, revisited