Difficulty: Intermediate to Hard. Prerequisites: Chapters 1–4 (logic, proofs, number theory).
Chapter 5 teaches you how to prove statements about all positive integers (induction) and how to define functions and algorithms that call themselves (recursion). Chapter 6 is about counting: how many ways can something happen? These two chapters together carry 4 questions on the final, and counting is widely considered the hardest topic in the course.
Mathematical induction
A proof technique for showing P(n) holds for all positive integers n. You prove a base case, then prove that P(k) implies P(k+1). Think of it as proving you can climb every rung of a ladder: show you can reach the first rung, then show that from any rung you can reach the next.
Strong induction
Like ordinary induction, but the induction step assumes P(1) ∧ P(2) ∧ … ∧ P(k) to prove P(k+1). Useful when the result at step k+1 depends on more than just step k.
Recursively defined function
A function defined by specifying f(0) (the base case) and a rule for computing f(x) from f values at smaller arguments.
Recursive algorithm
An algorithm that solves a problem by reducing it to a smaller version of itself.
Program correctness
A program is correct if it produces the right output for every input. Proving correctness means showing partial correctness (if it terminates, the answer is right) and termination (it always finishes).
Product rule
If task 1 has n_1 outcomes and task 2 has n_2 outcomes for each outcome of task 1, the combined procedure has n_1 × n_2 outcomes.
Sum rule
If a task can be done in n_1 ways or n_2 different (non-overlapping) ways, it can be done in n_1 + n_2 ways.
Subtraction rule (inclusion-exclusion for two sets)
|A ∪ B| = |A| + |B| - |A ∩ B|.
Permutation
An ordered arrangement of objects. nPr = n! / (n - r)!.
Combination
An unordered selection. nCr = n! / ((n - r)! · r!).
Pigeonhole principle
If you put k+1 objects into k boxes, at least one box has 2 or more objects.
Basis step: verify P(1) is true (or whatever the starting value is).
Induction step: assume P(k) is true (the induction hypothesis), then prove P(k+1).
The combination of these two steps proves P(n) for all n ≥ 1 by the principle of mathematical induction.
Basis step: verify P(1) is true.
Induction step: assume P(1) ∧ P(2) ∧ … ∧ P(k) are all true, then prove P(k+1).
Strong induction is logically equivalent to ordinary induction but is sometimes easier to apply, particularly when the recursive structure of a problem depends on multiple prior cases (e.g. Fibonacci-type recurrences).
Basis step: specify f(0) (or the starting value).
Recursive step: give a rule for computing f(x) from f at smaller arguments.
Example: the Fibonacci sequence. F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n ≥ 2.
Basis step: specify an initial collection of elements in S.
Recursive step: provide a rule for adding new elements from existing ones.
Proving results about recursively defined sets uses structural induction.
An algorithm is recursive if it solves a problem by reducing it to a smaller instance of the same problem. Recursive algorithms can be proven correct using induction.
Partial correctness: p{S}q means that if the initial assertion p holds and the program S terminates, then the final assertion q holds.
Rules of inference for programs:
Composition rule: from p{S1}q and q{S2}r, conclude p{S1; S2}r.
If-conditional: from (p ∧ condition){S}q and (p ∧ ¬condition) → q, conclude p{if condition then S}q.
If-else: from (p ∧ condition){S1}q and (p ∧ ¬condition){S2}q, conclude p{if condition then S1 else S2}q.
Loop invariant: from (p ∧ condition){S}p, conclude p{while condition S}(¬condition ∧ p). The assertion p is the loop invariant: it is true before the loop, preserved by every iteration, and still true when the loop exits.
Counting is the highest-difficulty topic in the course. The source guide devotes the most space to it, and it took up 3 pages on the second midterm.
For most counting problems: draw a line for each task, write what the task is above the line and how many ways to do it below, then multiply. This handles about 80% of problems.
Product rule: n_1 × n_2 ways when two independent tasks must both be completed.
Example: a licence plate with 3 letters then 4 digits (first nonzero) = 26³ × 9 × 10³ = 158,184,000.
Sum rule: n_1 + n_2 ways when a task can be done in one of two non-overlapping ways.
Subtraction rule: |A ∪ B| = |A| + |B| - |A ∩ B|. Use this when two counting methods overlap.
Example: 8-bit strings starting with 1 or ending with 00. |A| = 2⁷ = 128, |B| = 2⁶ = 64, |A ∩ B| = 2⁵ = 32. Answer: 128 + 64 - 32 = 160.
Division rule: if a process can be done n ways but each outcome is counted d times, the distinct count is n/d.
Basic: k+1 objects in k boxes means at least one box has ≥ 2 objects.
Generalised: N objects in k boxes means at least one box has ≥ ⌈N/k⌉ objects.
Permutations (order matters): nPr = n! / (n - r)!
Combinations (order does not matter): nCr = n! / ((n - r)! · r!)
nCr = nC(n - r). This symmetry is useful for simplifying calculations.
Division rule for repeated objects: if all n objects are distinct except m identical ones, divide n! by m!.
Choose r ordered items from n with replacement: n^r.
Choose r unordered items from n categories with replacement: (n + r - 1)Cr. Visualise r stars placed among n - 1 bars (dividers).
Distinguishable objects into distinguishable bins: n! / (n_1! · n_2! · … · n_k!) where n_i is the count in each bin.
Indistinguishable objects into distinguishable bins: same as combinations with repetition (stars and bars).
Distinguishable objects into indistinguishable bins: involves Stirling numbers (unlikely on the exam).
Indistinguishable objects into indistinguishable bins: enumerate by hand.
Binomial theorem: (x + y)^n = ∑(j=0 to n) nCj · x^(n-j) · y^j.
Pascal's identity: (n+1)Ck = nCk + nC(k-1).
Vandermonde's identity: (m+n)Cr = ∑(k=0 to r) mC(r-k) · nCk.
Students confuse ordinary induction with strong induction. Use strong induction when the induction step needs more than just P(k) to prove P(k+1).
In counting, the most common error is failing to recognise whether order matters (permutation vs combination).
Stars and bars only applies when objects are indistinguishable. If objects are distinct, you need a different formula.
Students forget the subtraction rule and double-count overlapping cases.
⚠️ Induction, strong induction and recursion carry 4 questions combined on the final.
⚠️ Counting took up 3 pages on the second midterm. Expect heavy coverage.
⚠️ Know when to use permutations vs combinations vs stars and bars. The exam typically tests your ability to identify the right tool.
⚠️ Loop invariants are a common exam question in program correctness.
True or false: in ordinary induction, the induction step assumes P(1) through P(k).
Fill in the blank: nCr = n! / ( ___ · ___ ).
True or false: 10 objects in 3 boxes guarantees at least one box has ≥ 4 objects.
How many ways can you choose 3 items from 5 with replacement (order does not matter)?
True or false: nCr = nC(n - r).
Answers: 1. False (that is strong induction). 2. (n - r)! and r!. 3. True (⌈10/3⌉ = 4). 4. (5 + 3 - 1)C3 = 7C3 = 35. 5. True.
Q: Prove by induction that ∑(k=1 to n) k = n(n+1)/2.
A: Base case: n = 1, ∑ = 1 = 1(2)/2 = 1. Induction step: assume the formula holds for n = m. Then ∑(k=1 to m+1) k = m(m+1)/2 + (m+1) = (m+1)(m+2)/2, which is the formula for n = m+1.
Q: How many 4-letter strings can be formed from {A, B, C} if repetition is allowed?
A: Order matters, repetition allowed: 3⁴ = 81.
Q: How many ways can 10 identical cookies be distributed among 4 children?
A: Stars and bars: (4 + 10 - 1)C10 = 13C10 = 286.
Q: State the loop invariant rule of inference.
A: From (p ∧ condition){S}p, conclude p{while condition S}(¬condition ∧ p).
Induction is the proof engine behind recursive algorithm analysis. Counting is the direct foundation for Chapter 7 (Discrete Probability), where you compute probabilities as |event| / |sample space|. Binomial coefficients reappear in Bernoulli trials.
CS 18200, CS 182, Purdue, discrete math, mathematical induction, strong induction, basis step, induction step, recursion, recursive function, Fibonacci, structural induction, program correctness, partial correctness, loop invariant, Hoare triple, counting, product rule, sum rule, subtraction rule, inclusion-exclusion, pigeonhole principle, permutation, combination, nPr, nCr, factorial, stars and bars, combinations with repetition, binomial coefficient, binomial theorem, Pascal's identity, Vandermonde identity, Stirling numbers