Complete Study Guide — Data Science Pre-Master Program
Built from the course lecture slides (584 slides, 10 chapters) · Color-coded for exam revision
How to use the colors
🔵 Blue = Definitions & core concepts | 🟢 Green = Laws, rules & steps |
🟡 Yellow = Very important / attention | 🔴 Red = Warnings, exceptions, common mistakes |
🟣 Purple = Key terms & vocabulary
The Foundations: Logic and Proofs — Sections 1.1–1.8
Logic gives precise meaning to mathematical statements and lets us tell valid arguments from invalid ones. This chapter covers propositions, logical operators, predicates and quantifiers, rules of inference, and methods of proof.
1.1 Propositional Logic
Definition
A proposition is a declarative sentence that is either true or false, but not both. Its truth value is "true" (T) or "false" (F).
Not propositions
Commands ("Sit down!"), questions ("What time is it?"), and statements with free variables ("x + 1 = 2") are not propositions.
Important
A disjunction (∨) is true when at least one proposition is true. A conjunction (∧) is true only when all propositions are true. A truth table for n propositional variables has 2ⁿ rows.
Conditional statement p → q
In "if p, then q," p is the hypothesis and q is the conclusion. p→q is false only when p is true and q is false.
Statement
Name
q → p
Converse of p → q
¬q → ¬p
Contrapositive of p → q
¬p → ¬q
Inverse of p → q
The contrapositive (¬q→¬p) is always logically equivalent to the original conditional p→q. The converse and inverse are not equivalent to p→q in general (but they are equivalent to each other).
1.2 Applications of Propositional Logic — Logic Circuits & Bit Operations
A bit has two values: 0 (false) and 1 (true). Bit operations correspond to AND, OR, XOR on bit strings, comparing respective bits. Logic circuits are built from three basic gates: the inverter (NOT), the OR gate, and the AND gate.
The three basic gates
1.3 Propositional Equivalences
Definition
Two propositions are logically equivalent (written p≡q) if they always have the same truth value — equivalently, if p↔q is a tautology, or if the columns of their truth tables agree.
De Morgan's Laws extend to n propositions: ¬(p₁∨p₂∨⋯∨pₙ) ≡ (¬p₁∧¬p₂∧⋯∧¬pₙ), and similarly with ∧ and ∨ swapped.
Example — Equivalence proof (showing a tautology)
Show (p∧q)→(p∨q) is a tautology:
(p∧q)→(p∨q) ≡ ¬(p∧q)∨(p∨q) [by Example 3]
≡ (¬p∨¬q)∨(p∨q) [De Morgan]
≡ (¬p∨p)∨(¬q∨q) [assoc./comm.]
≡ T∨T ≡ T [negation, domination laws]
Satisfiability
A compound proposition is satisfiable if some assignment of truth values makes it true; it is unsatisfiable if it is false for every assignment.
1.4 Predicates and Quantifiers
Definition
A predicate P(x) is a statement involving a variable that becomes a proposition once x is given a value. E.g., P(x): "x > 3" — P(4) is true, P(2) is false.
The two quantifiersUniversal ∀x P(x): "for all x, P(x)" — true iff P(x) is true for every x in the domain. Existential ∃x P(x): "there exists x such that P(x)" — true iff P(x) is true for at least one x in the domain.
Precedence
Quantifiers have higher precedence than all logical operators: ∃x P(x) ∨ Q(x) means (∃x P(x)) ∨ Q(x), not ∃x(P(x)∨Q(x)) — a common source of error.
Free vs. bound variables
A variable not yet quantified is free; a quantifier "binds" a variable, producing a bound variable.
1.5 Nested Quantifiers
Statement
When True?
When False?
∀x∀y P(x,y)
P(x,y) true for every pair x,y
Some pair x,y makes P(x,y) false
∀x∃y P(x,y)
For every x there is a y making P(x,y) true
Some x has no y making P(x,y) true
∃x∀y P(x,y)
Some x makes P(x,y) true for every y
For every x, some y makes P(x,y) false
∃x∃y P(x,y)
Some pair x,y makes P(x,y) true
P(x,y) false for every pair x,y
Order matters!
∀x∃y P(x,y) and ∃y∀x P(x,y) are generally not the same statement (e.g., with P(x,y): "x+y=0" over the reals, ∀x∃y P(x,y) is true, but ∃y∀x P(x,y) is false).
De Morgan's Laws for Quantifiers
Negation
Equivalent statement
When is negation true?
When false?
¬∃x P(x)
∀x ¬P(x)
For every x, P(x) is false.
There is an x for which P(x) is true.
¬∀x P(x)
∃x ¬P(x)
There is an x for which P(x) is false.
P(x) is true for every x.
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
1.6 Rules of Inference
A proof is a valid argument establishing the truth of a statement. An argument is a sequence of statements ending in a conclusion; it is valid if the conclusion follows from the truth of the premises: (p₁∧p₂∧⋯∧pₙ)→q is a tautology.
The Rules of Inference (Propositional Logic)
Rule of inference
Tautology
Name
p→q, p, ∴ q
[p∧(p→q)]→q
Modus ponens
p→q, ¬q, ∴ ¬p
[¬q∧(p→q)]→¬p
Modus tollens
p→q, q→r, ∴ p→r
[(p→q)∧(q→r)]→(p→r)
Hypothetical syllogism
p∨q, ¬p, ∴ q
[(p∨q)∧¬p]→q
Disjunctive syllogism
p, ∴ p∨q
p→(p∨q)
Addition
p∧q, ∴ p
(p∧q)→p
Simplification
p, q, ∴ p∧q
[(p)∧(q)]→(p∧q)
Conjunction
p∨q, ¬p∨r, ∴ q∨r
[(¬p∨r)∧(p∨q)]→(q∨r)
Resolution
Example — Modus ponens
"If it is snowing, then I will study discrete math." "It is snowing." Therefore, "I will study discrete math."
Example — Hypothetical syllogism
"If it snows, I will study discrete math." "If I study discrete math, I will get an A." Therefore, "If it snows, I will get an A."
Rules of Inference for Quantified StatementsUniversal Instantiation (UI): from ∀x P(x), conclude P(c) for a specific c. Universal Generalization (UG): used implicitly in most proofs. Existential Instantiation (EI): from ∃x P(x), conclude P(c) for some (unspecified) element c. Existential Generalization (EG): from P(c) for a specific c, conclude ∃x P(x).
Universal Modus Ponens
Combines universal instantiation and modus ponens into a single rule, used, e.g., in the classic "All men are mortal; Socrates is a man; therefore Socrates is mortal" argument.
1.7 Introduction to Proofs
Key termsTheorem: a statement shown true using definitions, other theorems, axioms, and rules of inference. Lemma: a "helping theorem." Corollary: a result that follows directly from a theorem. Conjecture: a statement proposed to be true (becomes a theorem once proved).
Proof Methods
Method
Idea
Direct proof
Assume p is true; show q must be true.
Proof by contraposition
Assume ¬q; show ¬p follows (indirect proof of p→q).
Proof by contradiction
Assume ¬p; derive a contradiction (p∧¬p), so p must be true.
Trivial proof
If q is already known true, then p→q is automatically true.
Vacuous proof
If p is already known false, then p→q is automatically true.
Example — Direct proof
Prove: if n is odd, then n² is odd.
n = 2k+1 for integer k → n² = (2k+1)² = 4k²+4k+1 = 2(2k²+2k)+1 = 2r+1
where r = 2k²+2k is an integer, so n² is odd. ∎
Example — Proof by contraposition
Prove: if 3n+2 is odd, then n is odd. Assume n is even (n=2k): 3n+2 = 6k+2 = 2(3k+1), which is even. So ¬q→¬p holds, hence p→q holds. ∎
Example — Proof by contradiction: √2 is irrational
Suppose √2 = a/b (rational, lowest terms). Then 2b²=a², so a² is even, so a is even (a=2c). Substituting gives b² also even, so b is even. But then 2 divides both a and b, contradicting "no common factors." Hence √2 is irrational. ∎
Biconditional proofs
To prove p↔q, show both p→q and q→p are true.
1.8 Proof Methods and Strategy
Proof by Cases
To prove (p₁∨p₂∨⋯∨pₙ)→q, prove each (pᵢ→q) separately — each implication is one "case." A complete proof requires every case to be checked.
Without Loss of Generality (WLOG)
Used when several cases are essentially identical by symmetry — only one representative case needs to be proven in detail.
Existence proofsConstructive: exhibit a specific c for which P(c) is true. Nonconstructive: assume no such c exists and derive a contradiction.
Example — Constructive existence proof
Show some positive integer is the sum of cubes of positive integers in two different ways: 1729 = 10³+9³ = 12³+1³.
Counterexamples
To show ∀x P(x) is false, find one c (a counterexample) for which P(c) is false. Example: "Every positive integer is the sum of the squares of 3 integers" is false — 7 is a counterexample.
🎯 Exam Focus — Chapter 1
Memorize the truth tables for ∧, ∨, ⊕, →, ↔ cold — nearly everything else in the chapter builds on them.
The contrapositive is ALWAYS equivalent to the original conditional; the converse and inverse are NOT (but are equivalent to each other).
De Morgan's Laws come in two flavors — for propositions (¬(p∧q)≡¬p∨¬q) and for quantifiers (¬∀xP(x)≡∃x¬P(x)) — know both and don't mix them up.
Quantifier order matters: ∀x∃y P(x,y) ≠ ∃y∀x P(x,y) in general.
Learn to recognize which proof technique fits: direct for straightforward implications, contraposition when ¬q is easier to work with than q, contradiction when you need to rule out the negation entirely.
The 8 rules of inference table is exam gold — know the name, the pattern, and the corresponding tautology for each.
Boolean algebra works with the set {0,1} and three operations: complementation, Boolean sum, and Boolean product. It underlies circuit design and logic gates.
2.1 Boolean Functions
The three basic operationsBoolean sum (+): 1+1=1, 1+0=1, 0+1=1, 0+0=0. Boolean product (·): 1·1=1, 1·0=0, 0·1=0, 0·0=0. Complement (‾): 0̄=1, 1̄=0.
Boolean functions
Let B={0,1}. Then Bⁿ is the set of all n-tuples of 0s and 1s. A function from Bⁿ to B is a Boolean function of degree n.
Important
There are 22ⁿ different Boolean functions of degree n (by the product rule — see Chapter 6). For n=2, this gives 16 different functions.
2.2 Identities of Boolean Algebra
All Boolean identities except the first and last two come in pairs — each is the dual of the other (swap + and ·, and swap 0 and 1). Boolean identities correspond directly to propositional-logic identities (Section 1.3) and set identities (Section 2.2 of Chapter 3 in this guide).
Formal definition of a Boolean algebra
A set B with two binary operations ∨ and ∧, elements 0 and 1, and a unary complement operation, satisfying for all x,y,z ∈ B:
Law
Statement
Example (x=1,y=0)
Identity laws
x∨0=x, x∧1=x
1∨0=1, 1∧1=1
Complement laws
x∨x̄=1, x∧x̄=0
1∨0=1, 1∧0=0
Associative laws
(x∨y)∨z=x∨(y∨z), (x∧y)∧z=x∧(y∧z)
(1∨0)∨1 = 1∨(0∨1) = 1
Commutative laws
x∨y=y∨x, x∧y=y∧x
1∨0 = 0∨1 = 1
Distributive laws
x∨(y∧z)=(x∨y)∧(y∨z), x∧(y∨z)=(x∧y)∨(y∧z)
1∨(0∧1) = (1∨0)∧(0∨1) = 1
Two natural examples of Boolean algebras: (1) propositional variables with ∧, ∨, T, F, ¬; and (2) subsets of a universal set with ∪, ∩, ∅, U, and set complement.
Key terms
A literal is a Boolean variable or its complement. A minterm of variables x₁,...,xₙ is a product y₁y₂⋯yₙ where each yᵢ is xᵢ or x̄ᵢ — it equals 1 for exactly one combination of input values. The sum of minterms representing a function is its sum-of-products expansion (disjunctive normal form).
Functional completeness
A set of operators is functionally complete if every Boolean function can be expressed using only that set. {·, +, ‾} is functionally complete; so are {·, ‾} and {+, ‾} (since x+y = x̄ȳ and xy = x̄+ȳ). The single NAND operator {|} is functionally complete (x̄ = x|x, xy=(x|y)|(x|y)); so is the single NOR operator {↓}.
2.4 Logic Gates
Combinatorial circuits are built from inverters (NOT), OR gates, and AND gates, which can share inputs and feed each other's outputs to build more complex expressions.
🎯 Exam Focus — Chapter 2
Boolean identities are a direct mirror of propositional-logic equivalences and set identities — if you know one set, you effectively know all three (just relabel the symbols).
Remember the duality principle: swapping ∨↔∧ and 0↔1 in any valid identity gives another valid identity.
Sum-of-products (disjunctive normal form) construction: for each row of the truth table where the function is 1, form a minterm (variable if 1, complement if 0), then OR them together.
Know at least one proof that {NAND} alone is functionally complete — a classic exam question.
Sections 2.1 and following (Sets, Set Operations, Functions, Sequences and Summations)
Sets are the fundamental building block of discrete mathematics. This chapter also covers set operations, functions (including one-to-one, onto, and inverse functions), and sequences and summations.
3.1 Sets
Definition
A set is an unordered collection of objects, called elements or members. We write a∈A ("a is an element of A") and a∉A ("a is not an element of A").
Ways to describe a setRoster method: list elements, {a,b,c,d} (order and repetition don't matter — {a,b,c,d}={b,c,a,d}={a,b,c,b,c,d}). Set-builder notation: S = {x | x is a positive integer less than 100}. Interval notation: [a,b], [a,b), (a,b], (a,b) for closed/half-open/open intervals.
Symbol
Set
N
Natural numbers {1,2,3,...}
Z
Integers {...,-2,-1,0,1,2,...}
Z⁺
Positive integers {1,2,3,...}
Q
Rational numbers
R
Real numbers
C
Complex numbers
Common mistake
The empty set ∅ is not the same as {∅} — the latter is a singleton set whose one element happens to be the empty set. ∅ ≠ {∅}.
Subsets
A⊆B means every element of A is also in B. A is a proper subset of B (A⊂B) if A⊆B and A≠B. Theorem: for every set S, ∅⊆S and S⊆S.
Example
A = {1,3,4}, B = {1,4,3,2}: every element of A is in B, so A ⊆ B.
Cardinality and Power Sets
|A| is the number of distinct elements in A (its cardinality). The power set P(A) is the set of all subsets of A; if |A|=n, then |P(A)| = 2ⁿ.
Example
A = {a,b}: P(A) = {∅, {a}, {b}, {a,b}} (|A|=2, so |P(A)|=2²=4 ✓)
Cartesian product
A×B = {(a,b) | a∈A and b∈B}. A subset of A×B is called a relation from A to B (studied fully in Chapter 8 of this guide).
Example
A = {a,b}, B = {1,2,3}: A×B = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}
3.2 Set Operations
Operation
Definition
Example
Union A∪B
{x | x∈A or x∈B}
{1,2,3}∪{3,4,5} = {1,2,3,4,5}
Intersection A∩B
{x | x∈A and x∈B}
{1,2,3}∩{3,4,5} = {3}
Complement Ā
{x∈U | x∉A} = U − A
U=Z⁺<100, A={x|x>70} → Ā={x|x≤70}
Difference A−B
{x | x∈A and x∉B} = A∩B̄
{1,3,5}−{1,2,3} = {5}
Symmetric difference A⊕B
Elements in exactly one of A, B
A={1,2,3,4,5}, B={4,5,6,7,8} → A⊕B={1,2,3,6,7,8}
Two sets are disjoint if A∩B=∅. Example: {1,2,3}∩{4,5,6} = ∅, so these sets are disjoint.
Inclusion–Exclusion for two sets
|A∪B| = |A| + |B| − |A∩B|
Set Identities (directly parallel Boolean algebra and propositional logic identities)
Law
Statement
Identity
A∪∅=A, A∩U=A
Domination
A∪U=U, A∩∅=∅
Idempotent
A∪A=A, A∩A=A
Complementation
(Ā)̄ = A
Commutative
A∪B=B∪A, A∩B=B∩A
Associative
A∪(B∪C)=(A∪B)∪C, A∩(B∩C)=(A∩B)∩C
Distributive
A∩(B∪C)=(A∩B)∪(A∩C), A∪(B∩C)=(A∪B)∩(A∪C)
De Morgan's
(A∪B)̄ = Ā∩B̄, (A∩B)̄ = Ā∪B̄
Proof of the second De Morgan Law using set-builder notation
Definition
A function f: A→B assigns each element of A to exactly one element of B. A is the domain, B is the codomain. If f(a)=b, b is the image of a, and a is a preimage of b. The range is the set of all images.
Injections, Surjections, BijectionsOne-to-one (injective): f(a)=f(b) implies a=b (equivalently, a≠b implies f(a)≠f(b)). Onto (surjective): for every element of the codomain, there is some element of the domain that maps to it. Bijection: both one-to-one and onto (a one-to-one correspondence). Only bijections have inverse functions.
Example — Testing injectivity
f(x)=x+4 (reals to reals) is one-to-one: if f(x)=f(y), then x+4=y+4, so x=y. But f(x)=x² (integers to integers) is not one-to-one: f(1)=f(−1)=1, yet 1≠−1.
Inverse functions
If f is a bijection from A to B, its inverse f⁻¹: B→A reverses the correspondence: f⁻¹(b)=a exactly when f(a)=b.
Composition
(f∘g)(x) = f(g(x)). Note f∘g requires the range of g to be a subset of the domain of f — g∘f may not even be defined when f∘g is.
Definition
A sequence is a function from a subset of the integers to a set S; the notation aₙ denotes the term (the image of n).
Geometric progression: aₙ = arⁿ (initial term a, common ratio r) — discrete analog of f(x)=arˣ. Arithmetic progression: aₙ = a+dn (initial term a, common difference d) — discrete analog of f(x)=dx+a.
Recurrence relations (preview)
A sequence can also be defined by giving a₀ and a rule for aₙ in terms of earlier terms (e.g., the Fibonacci sequence: f₀=0, f₁=1, fₙ=fₙ₋₁+fₙ₋₂ — full treatment in Chapter 7 of this guide).
Summation notation
Σ (from j=m to n) of aⱼ represents aₘ + aₘ₊₁ + ⋯ + aₙ. The variable j is the index of summation.
Some Useful Summation Formulae
Sum
Closed form
Σ (k=0 to n) ark (r≠1)
(arn+1 − a)/(r−1)
Σ (k=1 to n) k
n(n+1)/2
Σ (k=1 to n) k²
n(n+1)(2n+1)/6
Σ (k=1 to n) k³
n²(n+1)²/4
Σ (k=0 to ∞) xk, |x|<1
1/(1−x)
Σ (k=1 to ∞) kxk−1, |x|<1
1/(1−x)²
🎯 Exam Focus — Chapter 3
∅ ≠ {∅} — a classic trick question. The power set of a set with n elements has 2ⁿ elements.
Set identities directly mirror Boolean algebra and propositional logic identities — learn the pattern once, apply it in all three contexts.
To prove a function is one-to-one: assume f(a)=f(b) and show a=b. To prove NOT one-to-one: find one counterexample pair. To prove onto: show every codomain element has a preimage.
Only bijections have inverses — check both injectivity and surjectivity before claiming f⁻¹ exists.
Memorize the four summation closed forms (Σk, Σk², Σk³, geometric series) — they appear constantly in later chapters (especially induction and recurrence relations).
This chapter defines what an algorithm is, covers classic search and sort algorithms, and introduces Big-O, Big-Omega, and Big-Theta notation for describing how fast functions (and algorithm running times) grow.
4.1 Algorithms
Definition
An algorithm is a finite set of precise instructions for performing a computation or solving a problem.
Properties of algorithms
Input, Output, Correctness (produces correct output for every valid input), Finiteness (terminates after finitely many steps), Effectiveness (each step can be performed exactly), Generality (works for all problems of the desired form).
Three classes of algorithm problemsSearching (find an element in a list), Sorting (put a list in order), Optimization (find a max or min value).
Linear Search
Compare x to each element in sequence, starting from the first, until found or the list ends.
Binary Search
Requires a sorted list. Compare x to the middle element; recurse into the upper or lower half depending on the comparison. Much more efficient than linear search for large lists.
Example — Binary search for 19
In the sorted list 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 (16 elements), binary search locates 19 in 4 comparisons by repeatedly halving the search interval (midpoint 8→position 8, then 12, then 14, then 13), narrowing down to position 14 where the value 19 is found.
Bubble Sort
Makes multiple passes; each pass compares every adjacent pair and swaps them if out of order. After pass k, the k largest elements are in their correct final positions.
Insertion Sort
Builds the sorted list one element at a time: each new element is inserted into its correct position among the already-sorted elements before it (using a linear search to find that position).
4.2 The Growth of Functions
Big-O Notation — Definition
Let f and g be functions from the integers or reals to the reals. f(x) is O(g(x)) if there exist constants C and k such that:
Big-O definition |f(x)| ≤ C|g(x)| whenever x > k
Read: "f(x) is big-O of g(x)" or "g asymptotically dominates f." C and k are called witnesses to the relationship — only one pair is needed (though infinitely many valid pairs exist once one is found, since larger C or k also work).
Example — Showing x² is O(x³)... wait, showing a function IS big-O
Show 7x² is O(x³): When x>7, 7x² < x³. Take C=1, k=7 as witnesses.
Example — Showing n² is NOT O(n)
Suppose n² ≤ Cn for all n>k. Dividing both sides by n gives n≤C for all n>k — a contradiction (n grows without bound). So n² is not O(n).
Big-O of polynomials
If f(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ⋯ + a₁x + a₀ (with aₙ≠0), then f(x) is O(xⁿ) — the leading (highest-power) term dominates the polynomial's growth.
Important standard results
1+2+⋯+n is O(n²). n! is O(nⁿ). log(n!) is O(n log n).
Big-Omega Notation
f(x) is Ω(g(x)) if there are constants C, k such that |f(x)| ≥ C|g(x)| when x>k. Big-Omega gives a lower bound (Big-O gives an upper bound). f(x) is Ω(g(x)) iff g(x) is O(f(x)).
Big-Theta Notation
f(x) is Θ(g(x)) if f(x) is both O(g(x)) and Ω(g(x)) — equivalently, there exist C₁, C₂, k such that C₁g(x) < f(x) < C₂g(x) for x>k. We say f and g are "of the same order."
Combining functions
If f₁ is O(g₁) and f₂ is O(g₂), then (f₁+f₂) is O(max(|g₁|,|g₂|)), and (f₁f₂) is O(g₁g₂).
🎯 Exam Focus — Chapter 4
Big-O definition: |f(x)| ≤ C|g(x)| for x>k — memorize this exactly; almost every problem asks you to find witnesses C and k.
Only one pair of witnesses is needed to prove a big-O relationship, but that doesn't mean any C, k works — you must verify the inequality actually holds beyond your chosen k.
A polynomial's growth is always O(its highest-degree term) — drop lower-order terms and constants for Big-O purposes.
Big-O = upper bound, Big-Omega = lower bound, Big-Theta = both (tight bound / "same order"). Don't confuse the three.
Binary search cuts the search space in half each comparison — this is why it's dramatically faster than linear search for large lists (this connects directly to logarithmic time complexity, and to the divide-and-conquer recurrences in Chapter 7).
C₁|g(x)| ≤ |f(x)| ≤ C₂|g(x)| for all x > k (f is O(g) AND Ω(g))
Polynomial big-O
aₙxⁿ+⋯+a₀ is O(xⁿ) (leading term dominates)
Standard growth results
1+2+⋯+n is O(n²) | n! is O(nⁿ) | log(n!) is O(n log n)
Combining functions
f₁ O(g₁), f₂ O(g₂) ⟹ (f₁+f₂) is O(max(|g₁|,|g₂|)) and (f₁f₂) is O(g₁g₂)
Chapter 5 — Induction & Recursion
Sections 5.1–5.3: Mathematical Induction, Strong Induction and Well-Ordering, Recursive Definitions
Mathematical induction is a technique for proving that a property holds for all positive integers (or all integers from some starting point). This chapter also covers strong induction, the well-ordering property, and recursively defined functions.
5.1 Mathematical Induction
Principle of Mathematical Induction
To prove P(n) is true for all positive integers n:
Basis Step: Show P(1) is true.
Inductive Step: Show P(k)→P(k+1) is true for all positive integers k.
Common misunderstanding
In the inductive step, we do not assume P(k) is true for all k. We show that IF P(k) is true (the "inductive hypothesis"), THEN P(k+1) must also be true. Induction proofs don't always start at n=1 — the basis step can begin at any integer b.
Why it works
Mathematical induction is valid because of the well-ordering property: every nonempty subset of positive integers has a least element. (If P(n) failed for some n, the set of failures would have a least element m; m≠1 since P(1) holds; but then P(m−1) holds, forcing P(m) to hold too — contradiction.)
Example — Summation formula by induction
Prove 1+2+⋯+n = n(n+1)/2 for all positive integers n.
Prove a set with n elements has 2ⁿ subsets. Basis: n=0, the empty set has 2⁰=1 subset (itself). Inductive step: for T with k+1 elements, write T=S∪{a}. Each of the 2ᵏ subsets of S gives exactly two subsets of T (itself, and itself∪{a}), so T has 2·2ᵏ=2ᵏ⁺¹ subsets. ∎
5.2 Strong Induction and Well-Ordering
Strong Induction (a.k.a. "complete induction" or "second principle of induction")
Basis Step: Verify P(1) is true.
Inductive Step: Show [P(1)∧P(2)∧⋯∧P(k)] → P(k+1) holds for all positive integers k.
Important
Mathematical induction, strong induction, and the well-ordering property are all logically equivalent. You can always use strong induction in place of ordinary induction, but there's no need to if ordinary induction suffices.
Example — Postage stamps (strong induction)
Prove every amount of postage ≥12 cents can be formed from 4-cent and 5-cent stamps.
Basis: P(12),P(13),P(14),P(15) all directly verified (e.g., P(12)=3 fours). Inductive step: assume P(j) holds for 12≤j≤k (k≥15). Then P(k−3) holds (since k−3≥12); add a 4-cent stamp to form k+1 cents. ∎
Well-Ordering Property
Every nonempty set of nonnegative integers has a least element. A set is well ordered if every subset has a least element (e.g., N under ≤).
5.3 Recursively Defined Functions
Definition
A recursive (inductive) definition of a function has two parts: a Basis Step (specify f at 0) and a Recursive Step (give a rule for f(n+1) in terms of earlier values).
Example — Recursive function
f(0)=3, f(n+1)=2f(n)+3. Then f(1)=2(3)+3=9, f(2)=2(9)+3=21, f(3)=2(21)+3=45, f(4)=2(45)+3=93.
Always write out both steps explicitly: state P(n), verify the Basis Step numerically, then write "Assume P(k)" clearly before proving P(k+1) — graders look for this structure.
The inductive hypothesis is "P(k) is true" — a supposition, not a fact you already know for all k.
Use strong induction (rather than ordinary induction) whenever you need MORE than just the immediately preceding case to prove the next one (e.g., Fibonacci-style or "postage stamp" problems).
A recursive definition always needs a base case AND a recursive rule — an infinite loop results if either is missing.
📌 Chapter 5 — Formula Sheet
Mathematical Induction
[P(1) ∧ ∀k(P(k)→P(k+1))] → ∀n P(n)
Basis Step: show P(1). Inductive Step: assume P(k), show P(k+1).
Strong Induction
[P(1)∧P(2)∧⋯∧P(k)] → P(k+1), for all k
Use when P(k+1) may depend on more than just P(k).
Well-Ordering Property
Every nonempty set of nonnegative integers has a least element
Equivalent to both forms of induction above.
Recursive definition (general structure)
Basis Step: define f(0) | Recursive Step: define f(n+1) in terms of f(0),...,f(n)
Sum of first n positive integers (proved by induction)
Counting techniques let us determine how many ways something can happen without listing every possibility. This chapter covers the fundamental counting rules, the pigeonhole principle, and permutations and combinations (with and without repetition).
6.1 The Basics of Counting
The Product Rule
If a procedure has a sequence of two tasks, with n₁ ways to do the first and n₂ ways to do the second, there are n₁·n₂ ways to do the procedure.
Example — License plates
Three uppercase letters followed by three digits: 26·26·26·10·10·10 = 17,576,000 plates.
The Sum Rule
If a task can be done in one of n₁ ways OR one of n₂ ways (with no overlap), there are n₁+n₂ ways to do the task. In set terms: |A∪B|=|A|+|B| when A,B are disjoint.
The Subtraction Rule (Inclusion-Exclusion)
If a task can be done in n₁ ways or n₂ ways, the total is n₁+n₂ minus the ways common to both.
Example — Subtraction rule
Bit strings of length 8 starting with 1 OR ending in 00: 2⁷ + 2⁶ − 2⁵ = 128+64−32 = 160.
The Division Rule
There are n/d ways to do a task if it can be done via a procedure with n total ways, where exactly d of those n ways correspond to each single outcome.
Example — Circular seating
4 people around a circular table (rotations considered identical): 4!/4 = 6 distinct seatings.
Tree diagrams
Counting problems can be visualized with a tree, where branches represent choices and leaves represent outcomes.
6.2 The Pigeonhole Principle
Pigeonhole Principle
If k+1 or more objects are placed into k boxes, then at least one box contains two or more objects.
Generalized Pigeonhole Principle
If N objects are placed into k boxes, some box contains at least ⌈N/k⌉ objects.
Example — Cards of the same suit
How many cards guarantee at least 3 of the same suit? Using 4 boxes (suits), need ⌈N/4⌉≥3, so smallest N is 2·4+1=9.
Corollary: A function from a set with k+1 elements to a set with k elements is never one-to-one.
6.3 Permutations and Combinations
Definitions
A permutation is an ordered arrangement of objects. An r-permutation is an ordered arrangement of r elements from a set. A combination (r-combination) is an unordered selection of r elements — simply a subset of size r.
5-card hands from a 52-card deck: C(52,5) = 2,598,960.
Combinatorial proofs
A double counting proof shows both sides of an identity count the same objects in two different ways. A bijective proof exhibits a bijection between the two sets being counted.
Setting x=y=1 gives: Σ (j=0 to n) C(n,j) = 2ⁿ — this is also the total number of subsets of an n-element set, giving a second, combinatorial proof of that fact.
Pascal's Identity
C(n+1,k) = C(n,k−1) + C(n,k)
Pascal's Triangle
Row n consists of C(n,0), C(n,1), ..., C(n,n). By Pascal's Identity, each entry is the sum of the two entries diagonally above it in the previous row.
6.5 Generalized Permutations and Combinations
Permutations with repetition
The number of r-permutations of n objects with repetition allowed is nʳ.
Combinations with repetition
C(n+r−1, r) = C(n+r−1, n−1)
Modeled using "stars and bars": r stars (items chosen) separated by n−1 bars (dividing into n categories).
Summary Table — Combinations and Permutations With and Without Repetition
Type
Repetition allowed?
Formula
r-permutations
No
n!/(n−r)!
r-combinations
No
n!/[r!(n−r)!]
r-permutations
Yes
nʳ
r-combinations
Yes
(n+r−1)!/[r!(n−1)!]
🎯 Exam Focus — Chapter 6
Product rule = "AND" (sequential independent choices); Sum rule = "OR" (mutually exclusive alternatives). Most real problems combine both.
The single most useful table in this chapter is the four-formula summary (permutations/combinations, with/without repetition) — memorize which formula applies to which scenario.
Order matters → permutation. Order doesn't matter → combination. This is the first question to ask on every counting problem.
Generalized pigeonhole: ⌈N/k⌉ — remember to round UP (ceiling), not down.
The Binomial Theorem coefficient of xⁿ⁻ʲyʲ is C(n,j) — practice extracting a specific term's coefficient quickly.
Sections 8.1–8.3: Applications of Recurrence Relations, Solving Linear Recurrence Relations, Divide-and-Conquer
A recurrence relation expresses a sequence's terms in terms of earlier terms. This chapter shows how to set up recurrence relations (Fibonacci, Tower of Hanoi) and solve linear ones explicitly.
7.1 Applications of Recurrence Relations
Definition
A recurrence relation for {aₙ} expresses aₙ in terms of one or more previous terms, for n ≥ n₀. The initial conditions give the starting term(s).
Example — Rabbits and Fibonacci Numbers
A pair of rabbits breeds monthly once 2 months old; rabbits never die. Number of pairs after n months:
fₙ = fₙ₋₁ + fₙ₋₂ for n≥3, with f₁=1, f₂=1
Example — Tower of Hanoi
Moving n disks between pegs (never placing a larger disk on a smaller):
Hₙ = 2Hₙ₋₁ + 1, H₁=1
Solving iteratively: Hₙ = 2ⁿ⁻¹H₁ + 2ⁿ⁻²+⋯+2+1 = 2ⁿ − 1 (using the geometric series formula). For 64 disks (the "world ends" myth), 2⁶⁴−1 ≈ 500+ billion years at one move per day.
Example — Bit strings with no two consecutive 0s
aₙ = aₙ₋₁ + aₙ₋₂ for n≥3, with a₁=2, a₂=3. (This is the same recurrence as Fibonacci — aₙ=fₙ₊₂.) Solving: a₃=5, a₄=8, a₅=13.
7.2 Solving Linear Homogeneous Recurrence Relations
Definition
A linear homogeneous recurrence relation of degree k with constant coefficients: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ⋯ + cₖaₙ₋ₖ, where c₁,...,cₖ are real, cₖ≠0.
Solving by characteristic roots
Try aₙ=rⁿ. This gives the characteristic equation: rᵏ − c₁rᵏ⁻¹ − c₂rᵏ⁻² − ⋯ − cₖ = 0. The roots are the characteristic roots.
Theorem 1 — Degree-2, distinct roots
If r²−c₁r−c₂=0 has two distinct roots r₁,r₂, then every solution has the form:
Theorem 3 — Arbitrary degree, distinct roots
If the characteristic equation rᵏ−c₁rᵏ⁻¹−⋯−cₖ=0 has k distinct roots r₁,...,rₖ, then aₙ = α₁r₁ⁿ+α₂r₂ⁿ+⋯+αₖrₖⁿ.
Theorem 4 — Arbitrary degree, repeated roots allowed
With t distinct roots of multiplicities m₁,...,mₜ (Σmᵢ=k), the general solution includes a term αᵢ,ⱼnʲrᵢⁿ for each root rᵢ and each j from 0 to mᵢ−1.
Linear Nonhomogeneous Recurrence Relations
Form: aₙ = c₁aₙ₋₁+⋯+cₖaₙ₋ₖ + F(n), where F(n)≢0.
Theorem 5
If {aₙ⁽ᵖ⁾} is one particular solution, every solution has the form aₙ⁽ᵖ⁾ + aₙ⁽ʰ⁾, where aₙ⁽ʰ⁾ solves the associated homogeneous recurrence.
Example — Nonhomogeneous recurrence
aₙ = 3aₙ₋₁ + 2n. Associated homogeneous solution: aₙ⁽ʰ⁾=α3ⁿ. Trying a particular solution pₙ=cn+d: solving gives c=−1, d=−3/2, so aₙ⁽ᵖ⁾=−n−3/2. General solution: aₙ = −n − 3/2 + α3ⁿ (α determined by initial condition).
7.3 Divide-and-Conquer Algorithms and Recurrence Relations
Definition
A divide-and-conquer algorithm splits a problem into smaller instances of the same problem, solves them, then combines the results.
Divide-and-conquer recurrence
If a problem of size n splits into a subproblems each of size n/b, with g(n) extra operations to combine:
Setting up a recurrence relation (Rabbits, Tower of Hanoi, bit-string counting) is often the hardest part — always ask "how does the answer for n relate to the answer for smaller values?"
For linear homogeneous recurrences: write the characteristic equation, find its roots, then pick the correct general-solution form: distinct roots use rⁿ terms; a repeated root r₀ needs an EXTRA factor of n (i.e., n·r₀ⁿ) for the second linearly-independent solution.
Always use the initial conditions to solve for the constants (α₁, α₂, ...) — this is usually a small system of linear equations.
For divide-and-conquer, recognize the general form f(n)=a·f(n/b)+g(n) and be comfortable evaluating it by repeated substitution for a specific numeric example.
Sections 9.1, 9.3, 9.5, 9.6: Relations and Their Properties, Representing Relations, Equivalence Relations, Partial Orderings
A relation captures how elements of sets are connected. This chapter covers relation properties, matrix/digraph representations, equivalence relations and partitions, and partial orderings.
8.1 Relations and Their Properties
Definition
A binary relation R from A to B is a subset of A×B. A relation on a set A is a subset of A×A.
The number of relations on a set with n elements is 2n² (since A×A has n² elements, and each subset is a relation).
Properties of Relations
Property
Symbolic definition
Example (relations on the integers)
Reflexive
∀x[x∈A → (x,x)∈R]
R={(a,b)|a=b} is reflexive; R={(a,b)|a>b} is not (3≯3)
Symmetric
∀x∀y[(x,y)∈R → (y,x)∈R]
R={(a,b)|a=b or a=−b} is symmetric; R={(a,b)|a≤b} is not (3≤4 but 4≰3)
Antisymmetric
∀x∀y[(x,y)∈R ∧ (y,x)∈R → x=y]
R={(a,b)|a≤b} is antisymmetric; R={(a,b)|a=b or a=−b} is not (both (1,−1),(−1,1)∈R)
Transitive
∀x∀y∀z[(x,y)∈R ∧ (y,z)∈R → (x,z)∈R]
R={(a,b)|a≤b} is transitive; R={(a,b)|a=b+1} is not ((3,2),(4,3)∈R but (4,2)∉R)
Common mistake
Symmetric and antisymmetric are not opposites — a relation can be both (e.g., R={(a,a)}), or neither. Antisymmetric ≠ "not symmetric."
8.2 Representing Relations
Zero-one matrix representation
MR=[mᵢⱼ], where mᵢⱼ=1 if aᵢ is related to bⱼ, and 0 otherwise.
R is reflexive iff all diagonal entries of MR are 1. R is symmetric iff MR equals its own transpose (mᵢⱼ=mⱼᵢ). R is antisymmetric iff mᵢⱼ=0 or mⱼᵢ=0 whenever i≠j.
Digraph representation
A directed graph with vertices V and edges E (ordered pairs). An edge (a,a) is a loop.
Reading properties from a digraph
Property
Digraph condition
Reflexive
A loop at every vertex
Symmetric
If (x,y) is an edge, so is (y,x)
Antisymmetric
If (x,y) is an edge with x≠y, then (y,x) is NOT an edge
Transitive
If (x,y) and (y,z) are edges, so is (x,z)
Composition and powers
(x,z) ∈ S∘R if (x,y)∈R and (y,z)∈S for some y. Powers: R¹=R, Rⁿ⁺¹=Rⁿ∘R. Theorem: R is transitive iff Rⁿ⊆R for n=1,2,3,....
8.3 Equivalence Relations
Definition
A relation is an equivalence relation if it is reflexive, symmetric, AND transitive. Related elements are called equivalent (a∼b).
Example — Congruence modulo m
R={(a,b) | a≡b (mod m)} is an equivalence relation: reflexive (a−a=0 divisible by m), symmetric (a−b=km ⟹ b−a=−km), transitive (a−b=km, b−c=lm ⟹ a−c=(k+l)m).
Equivalence classes
[a]R = {s | (a,s)∈R} — all elements equivalent to a. Any b∈[a]R is a representative of the class.
Theorem 1
For an equivalence relation R: aRb ⟺ [a]=[b] ⟺ [a]∩[b]≠∅.
Partition
A partition of S is a collection of nonempty, pairwise disjoint subsets whose union is S.
Theorem 2 — Equivalence relations ↔ Partitions
The equivalence classes of an equivalence relation on S form a partition of S — and conversely, every partition of S defines a corresponding equivalence relation (two elements related iff they're in the same part).
8.4 Partial Orderings
Definition
A relation is a partial ordering if it is reflexive, antisymmetric, and transitive. A set with a partial ordering R is a poset, denoted (S,R).
Examples of posets
(Z, ≥): "greater than or equal" is reflexive, antisymmetric, transitive.
(Z⁺, |): the "divides" relation is a partial ordering.
(P(S), ⊆): the "subset" relation on a power set is a partial ordering.
🎯 Exam Focus — Chapter 8
To test all four properties (reflexive, symmetric, antisymmetric, transitive) on a given relation, check each definition directly against the relation's defining rule — don't just guess from examples.
Equivalence relation = reflexive + symmetric + transitive. Partial order = reflexive + ANTIsymmetric + transitive. The only difference is symmetric vs. antisymmetric — a very common exam distinction.
Equivalence classes always partition the set — no element is left out, and no element belongs to two different classes.
From a digraph: antisymmetric means no "round trips" between two DIFFERENT vertices (loops are fine).
📌 Chapter 8 — Formula Sheet
Reflexive
∀x[x∈A → (x,x)∈R]
Symmetric
∀x∀y[(x,y)∈R → (y,x)∈R]
Antisymmetric
∀x∀y[(x,y)∈R ∧ (y,x)∈R → x=y]
Transitive
∀x∀y∀z[(x,y)∈R ∧ (y,z)∈R → (x,z)∈R]
Matrix MR conditions
Reflexive: diagonal all 1s | Symmetric: mᵢⱼ=mⱼᵢ | Antisymmetric: mᵢⱼ=0 or mⱼᵢ=0 (i≠j)
Composition & powers
(x,z)∈S∘R if (x,y)∈R,(y,z)∈S for some y | R¹=R, Rⁿ⁺¹=Rⁿ∘R | R transitive ⟺ Rⁿ⊆R for all n
Sections 10.1–10.5: Graphs and Graph Models, Graph Terminology, Representing Graphs and Isomorphism, Connectivity, Euler and Hamilton Paths
Graphs model pairwise relationships between objects: computer networks, social networks, road maps, and more. This chapter covers the vocabulary of graph theory, how to represent graphs, connectivity, and the classic Euler and Hamilton path problems.
9.1 Graphs and Graph Models
Definition
A graph G=(V,E) consists of a nonempty set V of vertices and a set E of edges, each connecting one or two vertices (its endpoints).
Type
Edges
Multiple edges?
Loops?
Simple graph
Undirected
No
No
Multigraph
Undirected
Yes
No
Pseudograph
Undirected
Yes
Yes
Simple directed graph
Directed
No
No
Directed multigraph
Directed
Yes
—
Graph models
Used for computer networks, social networks (friendship, influence graphs), information networks (web graphs, citation networks), transportation networks, and software design (module dependency graphs, precedence graphs).
9.2 Graph Terminology
Key definitions
Two vertices are adjacent (neighbors) if an edge connects them. The neighborhood N(v) is the set of all neighbors of v. The degree deg(v) is the number of edges incident with v (a loop counts twice).
The Handshaking Theorem
For an undirected graph G=(V,E) with m edges:
2m = Σ (v∈V) deg(v)
Since 2m is even, an undirected graph always has an even number of vertices of odd degree (Theorem 2).
Example — Applying the Handshaking Theorem
A graph with 10 vertices, all of degree 6: 2m = 6×10=60, so m=30 edges. A graph can NOT have 5 vertices all of degree 3 — since 3×5=15 is odd, violating the theorem.
Directed graphsin-degree deg⁻(v): edges ending at v. out-degree deg⁺(v): edges starting at v. Theorem 3: Σdeg⁻(v) = Σdeg⁺(v) = number of edges.
Special simple graphsComplete graph Kn: one edge between every pair of n vertices. Cycle Cn: n vertices in a single loop. Wheel Wn: a cycle plus a central hub vertex connected to all. n-cube Qn: 2ⁿ vertices (bit strings of length n), edges between strings differing in one bit.
Bipartite graphs
V splits into V₁, V₂ with every edge connecting a vertex in V₁ to one in V₂ (no edges within V₁ or within V₂). Equivalently: the graph can be 2-colored with no two adjacent vertices sharing a color. Complete bipartite graph Km,n: every vertex in V₁ (size m) connects to every vertex in V₂ (size n).
Subgraphs and unions
A subgraph (W,F) has W⊆V, F⊆E. The union G₁∪G₂ has vertex set V₁∪V₂ and edge set E₁∪E₂.
9.3 Representing Graphs and Isomorphism
Adjacency matrix
AG=[aᵢⱼ], an n×n zero-one matrix with aᵢⱼ=1 iff vᵢ and vⱼ are adjacent. For a simple graph, AG is symmetric with 0s on the diagonal. For loops/multi-edges, the entry equals the number of connecting edges.
Incidence matrix
M=[mᵢⱼ], n×m (n vertices, m edges), where mᵢⱼ=1 if edge eⱼ is incident with vertex vᵢ.
Isomorphism
G₁=(V₁,E₁) and G₂=(V₂,E₂) are isomorphic if there is a bijection f:V₁→V₂ such that a,b are adjacent in G₁ iff f(a),f(b) are adjacent in G₂.
Graph invariants
Properties preserved by isomorphism, useful for proving graphs are NOT isomorphic: number of vertices, number of edges, and the degree sequence (list of vertex degrees in nonincreasing order). If two graphs differ in any invariant, they cannot be isomorphic.
9.4 Connectivity
Paths
A path of length n from u to v is a sequence of n edges traversing vertices x₀=u,...,xₙ=v. A circuit is a path that starts and ends at the same vertex (length>0). A path/circuit is simple if no edge repeats.
Connectedness
An undirected graph is connected if there is a path between every pair of vertices. A connected component is a maximal connected subgraph.
Directed graph connectivityStrongly connected: a path from a to b AND from b to a, for every pair a,b. Weakly connected: connected when edge directions are ignored.
Counting paths using adjacency matrices
The number of different paths of length r from vᵢ to vⱼ equals the (i,j) entry of Ar, where A is the adjacency matrix.
9.5 Euler and Hamilton Paths
Historical origin
The Seven Bridges of Königsberg problem, solved by Euler — considered the first theorem of graph theory.
Definitions
An Euler circuit is a simple circuit containing every edge of G. An Euler path is a simple path containing every edge (but not necessarily returning to the start).
Theorem — Necessary and Sufficient Conditions
A connected multigraph (≥2 vertices) has an Euler circuit iff every vertex has even degree. It has an Euler path (not circuit) iff it has exactly two vertices of odd degree (the path connects them).
Hamilton paths and circuits
A Hamilton path passes through every vertex exactly once. A Hamilton circuit is a Hamilton path that returns to the start. Unlike Euler circuits, no simple necessary-and-sufficient condition is known.
Sufficient conditions for Hamilton circuitsDirac's Theorem: if G is simple with n≥3 vertices and every vertex has degree ≥n/2, G has a Hamilton circuit. Ore's Theorem: if G is simple with n≥3 vertices and deg(u)+deg(v)≥n for every pair of nonadjacent vertices u,v, G has a Hamilton circuit.
Application
The Traveling Salesperson Problem (TSP) asks for the minimum-weight Hamilton circuit — a classic hard optimization problem.
🎯 Exam Focus — Chapter 9
The Handshaking Theorem (2m=Σdeg(v)) is used constantly — remember a loop contributes 2 to that vertex's degree.
To disprove isomorphism, find ONE invariant that differs (vertex count, edge count, or degree sequence) — much faster than trying every possible vertex correspondence.
Euler circuit ⟺ all even degrees. Euler path (not circuit) ⟺ exactly 2 odd-degree vertices. If a graph has more than 2 odd-degree vertices, NEITHER exists.
Hamilton path/circuit conditions are NOT as clean as Euler's — Dirac's and Ore's theorems give sufficient (not necessary) conditions; a graph can still have a Hamilton circuit even if it fails both tests.
Adjacency matrix of a simple graph is always symmetric with a zero diagonal; this is a quick sanity check.
📌 Chapter 9 — Formula Sheet
Handshaking Theorem
2m = Σ deg(v)
Corollary: every undirected graph has an even number of odd-degree vertices.
Same # vertices, same # edges, same degree sequence (necessary but not sufficient for isomorphism)
Connectivity
Connected: path between every pair | Strongly connected (directed): path a→b AND b→a for every pair
Paths of length r via adjacency matrix
(i,j) entry of Aʳ = number of paths of length r from vᵢ to vⱼ
Euler circuit condition
Connected AND every vertex has even degree
Euler path (non-circuit) condition
Connected AND exactly two vertices of odd degree
Hamilton path/circuit
Simple path/circuit passing through every VERTEX exactly once (no simple universal test — see Dirac/Ore below)
Dirac's Theorem
n≥3, deg(v)≥n/2 for all v ⟹ Hamilton circuit exists
Ore's Theorem
n≥3, deg(u)+deg(v)≥n for nonadjacent u,v ⟹ Hamilton circuit exists
Chapter 10 — Trees
Section 11.1: Introduction to Trees
A tree is a special kind of graph with no cycles — used to model hierarchies, file systems, organization charts, and chemical structures.
10.1 Introduction to Trees
Definition
A tree is a connected undirected graph with no simple circuits. A forest is a graph with no simple circuits that is not necessarily connected — each connected component of a forest is itself a tree.
Theorem — Unique path characterization
An undirected graph is a tree if and only if there is a unique simple path between every pair of its vertices.
Rooted trees
A rooted tree designates one vertex as the root, with every edge directed away from it. The same unrooted tree gives different rooted trees depending on the chosen root.
Rooted-tree vocabulary
If u→v is an edge, u is the parent of v, and v is a child of u. Vertices sharing a parent are siblings. The ancestors of v are all vertices on the path from the root to v (excluding v, including the root). The descendants of v are all vertices having v as an ancestor. A vertex with no children is a leaf; a vertex with children is an internal vertex. The subtree rooted at a is the subgraph of a and all its descendants.
m-ary trees
A rooted tree is m-ary if every internal vertex has at most m children; it is full m-ary if every internal vertex has exactly m children. An m-ary tree with m=2 is a binary tree.
Ordered rooted trees
Children of each internal vertex are ordered (drawn left to right). In a binary tree, the first child is the left child, the second is the right child; the corresponding subtrees are the left/right subtrees.
Theorem 2 — Edge count
A tree with n vertices has exactly n−1 edges.
Proof sketch (induction): basis n=1 (0 edges); inductive step: remove a leaf v and its edge from a (k+1)-vertex tree, leaving a k-vertex tree with k−1 edges by the inductive hypothesis, so the original tree has k edges.
Theorem 3 — Vertex count in full m-ary trees
A full m-ary tree with i internal vertices has n = mi + 1 vertices total.
Theorem 4 — Relating n, i, and leaves l (full m-ary tree)
Given
Internal vertices (i)
Leaves (l)
n vertices
i = (n−1)/m
l = [(m−1)n+1]/m
i internal vertices
—
l = (m−1)i + 1
l leaves
i = (l−1)/(m−1)
n = (ml−1)/(m−1)
Level and height
The level of a vertex v is the length of the unique path from the root to v (root is at level 0). The height of a rooted tree is the maximum level among all its vertices.
Balanced trees
An m-ary rooted tree of height h is balanced if all leaves are at level h or h−1.
🎯 Exam Focus — Chapter 10
Tree = connected + no simple circuits. Both conditions are required — a connected graph with a cycle is not a tree, and an acyclic disconnected graph is a forest, not a single tree.
n vertices ⟹ exactly n−1 edges — an extremely useful quick check.
Don't confuse "m-ary" (at most m children) with "full m-ary" (exactly m children) — theorem formulas apply specifically to FULL m-ary trees.
Level of the root is always 0 (not 1) — height = the largest level value in the tree.
Practice identifying parent/child/sibling/ancestor/descendant/leaf/internal-vertex from a drawn tree — this vocabulary shows up constantly in later applications (not covered in this deck) like tree traversal and spanning trees.
📌 Chapter 10 — Formula Sheet
Tree definition & unique path property
Tree = connected + no simple circuits ⟺ unique simple path between every pair of vertices
Edges in a tree
edges = n − 1 (n = number of vertices)
Vertices in a full m-ary tree (from internal vertices i)
n = mi + 1
Full m-ary tree relationships (Theorem 4)
From n vertices: i=(n−1)/m, l=[(m−1)n+1]/m | From i internal vertices: n=mi+1, l=(m−1)i+1
From l leaves: n=(ml−1)/(m−1), i=(l−1)/(m−1)
Level & height
Level(v) = length of path from root to v (root = level 0) | Height = max level in the tree
Balanced tree condition
All leaves at level h or h−1 (h = tree height)
🚀 Final Exam Review
The most important content from all 10 chapters, in one place
Most Important Definitions
Proposition: a declarative sentence that is true or false, not both.
Set operations, one-to-one/onto functions, and the four key summation formulas (Ch. 3).
The Big-O definition and how to find witnesses C, k (Ch. 4).
The two-step structure of induction proofs — basis + inductive step (Ch. 5).
The four permutation/combination formulas and when to use each (Ch. 6).
Solving a degree-2 linear homogeneous recurrence via its characteristic equation (Ch. 7).
The four relation properties, and equivalence relation vs. partial order (Ch. 8).
Handshaking Theorem, and the Euler circuit/path degree conditions (Ch. 9).
Tree = connected + acyclic; n vertices ⟹ n−1 edges (Ch. 10).
🧠 Quick Revision Checklist
Use this while studying — check off each item as you master it
I can build a truth table for any compound proposition and identify tautologies/contradictions.
I know all the logical equivalences (De Morgan's, distributive, absorption, etc.) by name.
I can translate English sentences into predicate logic with quantifiers, including nested quantifiers.
I can apply De Morgan's Laws for quantifiers to negate a quantified statement correctly.
I can name and apply each of the 8 rules of inference (modus ponens, modus tollens, syllogisms, etc.).
I can write a direct proof, a proof by contraposition, and a proof by contradiction for a simple statement.
I understand Boolean algebra identities and can find a sum-of-products expansion.
I can perform set operations (union, intersection, complement, difference) and prove set identities.
I can determine if a function is one-to-one, onto, or a bijection, and find an inverse when it exists.
I know the four summation formulas (Σk, Σk², Σk³, geometric series).
I can find witnesses C and k to prove a Big-O relationship, and I know the difference between O, Ω, and Θ.
I can write a complete induction proof (basis step + inductive step) for a summation or inequality.
I know when to use strong induction instead of ordinary induction.
I can distinguish permutations from combinations and apply the correct formula (with/without repetition).
I can use the Binomial Theorem to find a specific coefficient, and apply Pascal's Identity.
I can set up and solve a degree-2 linear homogeneous recurrence relation using characteristic roots.
I can test whether a relation is reflexive, symmetric, antisymmetric, and/or transitive.
I can find equivalence classes and describe the partition they form.
I can apply the Handshaking Theorem and determine if a graph has an Euler circuit/path.
I can identify tree properties (root, parent, child, leaf, internal vertex, height, level).
Note on source accuracy: This guide was built strictly from the content of the uploaded course slides (584 slides spanning Chapters 1, 12, 2, 3, 5, 6, 8, 9, 10, and 11, in the order taught). Every definition, law, formula, theorem, and worked example above was read directly from the slides or confirmed against the slide images — nothing was added from outside the material. The text in this deck extracted unusually cleanly (most formulas, truth tables, and proofs came through as readable text), and a small number of pages that were pure images (e.g., the Set Identities table, the P(n,r)/C(n,r) formulas, the Binomial Theorem, Pascal's Identity, the Big-O definition, and the permutation/combination summary table) were individually opened and visually confirmed against the original slide images before being included here.