Difficulty: Intermediate | Prerequisites: Comfort with basic logic (AND, OR, NOT, implications), familiarity with mathematical notation, some exposure to sets and functions.
This material sits right at the start of EECS 376 and underpins everything that follows. Proof techniques are the language you will use to argue correctness of algorithms, and induction is the workhorse for reasoning about recursive structures and loop invariants. If you have taken a discrete maths course (EECS 203 or equivalent), this is a focused refresher. If you skipped that, treat this as essential groundwork: nothing in the rest of the course makes sense without it.
There are three core proof strategies (direct, contrapositive, contradiction) and two flavours of induction (standard and strong). Direct proof assumes the hypothesis and derives the conclusion; contrapositive flips and negates both sides; contradiction assumes the opposite and finds an impossibility. Induction proves a base case, then shows the step from k to k + 1 (or, for strong induction, from all cases up to k).
Direct proof
A proof of an implication P ⟹ Q that assumes P is true and derives Q through a chain of logical steps. In simple terms, you start from what you are given and work forward until you reach what you need to show.
Proof by contrapositive
A proof of P ⟹ Q that instead proves the logically equivalent statement ¬Q ⟹ ¬P. Think of it as: rather than showing "if it rained, the ground is wet," you show "if the ground is dry, it did not rain."
Proof by contradiction
A proof that assumes the statement you want to prove is false, then derives a logical impossibility. The contradiction forces the original statement to be true. In simple terms, you say "suppose this were wrong" and show that the world breaks.
Mathematical induction (weak/standard induction)
A proof technique for statements P(n) over the positive integers. You show P(1) holds (base case) and that P(k) ⟹ P(k + 1) for any k (inductive step). Think of it as a row of dominoes: knock over the first one, and each one knocks over the next.
Strong induction
A variant of induction where the inductive step assumes P(1) ∧ P(2) ∧ … ∧ P(k) (all cases up to k) to prove P(k + 1). In simple terms, you get to lean on every previous case, not just the one immediately before.
Base case
The starting point of an induction proof, where you verify the statement holds for the smallest value (typically n = 1). This is what gets the chain going.
Inductive hypothesis
The assumption, within the inductive step, that P(k) is true (standard induction) or that P(1) through P(k) are all true (strong induction). You treat this as a given and use it to prove the next case.
Inductive step
The part of an induction proof where you show that the truth of previous cases implies the truth of the next case, P(k + 1). This is where the real work happens.
Direct proof – proving P ⟹ Q
Assume P is true.
Derive a chain of logical consequences that ends at Q.
Example: "If n is even, then n² is even." Assume n = 2k for some integer k. Then n² = 4k² = 2(2k²), which is even.
Proof by contrapositive – also proving P ⟹ Q
Instead of P ⟹ Q, prove the equivalent ¬Q ⟹ ¬P.
Useful when the negation of the conclusion gives you something concrete to work with.
Example: "If n² is even, then n is even." Proving this directly is awkward. Instead, assume n is odd (¬Q). Then n = 2k + 1, so n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd (¬P). Done.
Proof by contradiction – proving any statement P
Assume ¬P (the opposite of what you want).
Derive a logical impossibility (e.g. a number that is both even and odd, or a fraction in lowest terms that is not).
The impossibility means ¬P cannot hold, so P must be true.
Classic example: proving √2 is irrational. Assume √2 = a/b in lowest terms, then show both a and b must be even, contradicting "lowest terms."
Choosing a technique
Direct proof: try this first. If the hypothesis hands you something useful, follow it forward.
Contrapositive: use when the conclusion's negation is easier to work with than the hypothesis.
Contradiction: use when the statement has no obvious hypothesis/conclusion structure, or when "suppose not" immediately gives you something strong to exploit (like a rational representation of an irrational number).
Standard (weak) induction
Used to prove a statement P(n) for all positive integers n (or all n ≥ some starting value).
Base case: Show P(1) is true (or P(n₀) for your chosen starting value).
Inductive step: Assume P(k) is true for an arbitrary positive integer k (this is the inductive hypothesis). Show that P(k + 1) follows.
Once both pieces are in place, the conclusion is that P(n) holds for every n in the domain.
Example from the worksheet: proving the sum of the first i terms of a geometric sequence equals S_i = a₁(1 − rⁱ) / (1 − r).
Base case (i = 1): S₁ = a₁. The formula gives a₁(1 − r) / (1 − r) = a₁. Checks out.
Inductive step: Assume S_k = a₁(1 − rᵏ) / (1 − r). Then S_{k+1} = S_k + a₁rᵏ = a₁(1 − rᵏ) / (1 − r) + a₁rᵏ. Combining over a common denominator gives a₁(1 − rᵏ⁺¹) / (1 − r).
Strong induction
The structure is the same, but the inductive hypothesis is more powerful.
Base case: Same as standard induction.
Inductive step: Assume P(1), P(2), …, P(k) are all true. Show P(k + 1) follows.
This is useful when proving P(k + 1) requires appealing to a case earlier than k (e.g. P(k − 3) or some arbitrary P(j) with j < k + 1).
Example from the worksheet: the stone-splitting problem. A pile of n stones is split into individual stones through a series of binary splits. The claim is that the sum of pairwise products of each split always equals n(n − 1)/2, regardless of how you split.
Base case (n = 1): no splits needed, sum of products = 0 = 1(0)/2.
Inductive step: Assume the claim holds for all pile sizes 1 through k. A pile of k + 1 is first split into two piles of size a and b where a + b = k + 1. The first split contributes a · b. By the strong inductive hypothesis, the remaining splits on the pile of a contribute a(a − 1)/2 and those on the pile of b contribute b(b − 1)/2. Total = ab + a(a − 1)/2 + b(b − 1)/2, which simplifies to (k + 1)k/2.
When to use strong vs. standard
If the step from k to k + 1 depends only on the case k, standard induction suffices. If it could depend on any earlier case, use strong induction. Strong induction is never weaker than standard, it just gives you more to work with.
Proving the converse instead of the original. Students often prove Q ⟹ P when asked to prove P ⟹ Q. The worksheet's faulty proof (b) does exactly this: it proves "if n is even then n² is even" when the claim is "if n² is even then n is even." Always check the direction of the implication before you start writing.
One example is not a proof. Showing that a statement holds for n = 1, 2, 3 does not prove it for all n. The worksheet's faulty proof (c) demonstrates this: checking a few cases and asserting "the pattern will continue" is not induction. You need the explicit inductive step.
Forgetting that the proof must cover all cases. Faulty proof (a) finds one prime greater than 2 that is odd and declares there are no even primes greater than 2. A single counterexample can disprove, but a single example cannot prove a universal statement.
Reusing the same variable for two different quantities. Faulty proof (e) lets n = 2k and m = 2k, implicitly assuming n = m. The fix is to use different variables: n = 2j and m = 2k.
Proving a statement is true without proving it is the strongest possible. Faulty proof (d) shows 37 is prime and less than 41, but never shows there is no prime between 37 and 41 (there is not, but the proof must address it).
⚠️ Expect "identify the error in this proof" questions. The worksheet devotes an entire section to faulty proofs. Know the common mistakes cold: proving the converse, arguing from examples, reusing variables, incomplete case coverage.
⚠️ Induction proofs appear throughout the course, not just in the first unit. Algorithm correctness arguments (loop invariants, recursive correctness) lean on induction. If the base case / inductive step pattern is not automatic for you, drill it now.
⚠️ Know when to reach for strong induction. If the problem involves splitting, recursion to a non-adjacent subproblem, or any step that needs an earlier case besides k, that is the signal.
⚠️ Proof by contradiction is the standard technique for irrationality proofs (√2, √7, etc.). Be able to reproduce the template from memory: assume rational in lowest terms, derive that both numerator and denominator share a factor, contradiction.
True or false: To prove P ⟹ Q by contrapositive, you assume P is false and derive that Q is false. (False. You assume ¬Q and derive ¬P.)
True or false: In a proof by contradiction, if you reach a contradiction, the assumption you started with must be false. (True.)
Fill in the blank: In standard induction, the inductive step proves P(k) → ____. (P(k + 1).)
True or false: Strong induction and standard induction can prove different sets of theorems; some results require strong induction and cannot be proved with standard. (False. They are logically equivalent in power, but strong induction is sometimes more convenient.)
True or false: Checking that a formula holds for n = 1, 2, 3, 4, 5 constitutes a valid proof by induction. (False. You need the general inductive step, not a finite list of examples.)
Q: A proposed proof of "there is no even prime greater than 2" argues: 3 is prime, greater than 2, and odd, so there is no even prime greater than 2. What is wrong?
A: The proof gives one example of an odd prime and concludes a universal statement. To prove the claim, you need to argue that any even number greater than 2 is divisible by 2 and therefore not prime (except 2 itself). One example proves nothing about all cases.
Q: A proposed proof of "if n² is even then n is even" begins by assuming n is even and deriving that n² is even. What is the error?
A: The proof proves the converse (if n is even then n² is even), not the original claim. A correct approach uses the contrapositive: assume n is odd, then show n² is odd.
Q: Prove by contradiction that √7 is irrational.
A: Assume √7 = a/b where a and b are integers with no common factor. Then 7b² = a², so a² is divisible by 7, which means a is divisible by 7 (since 7 is prime). Write a = 7c. Then 7b² = 49c², so b² = 7c², meaning b is also divisible by 7. This contradicts a/b being in lowest terms. Therefore √7 is irrational.
Q: In an induction proof of the geometric series formula S_i = a₁(1 − rⁱ)/(1 − r), what is the base case and what must the inductive step show?
A: Base case: verify S₁ = a₁ matches the formula, i.e. a₁(1 − r)/(1 − r) = a₁. Inductive step: assume S_k = a₁(1 − rᵏ)/(1 − r) and show S_{k+1} = S_k + a₁rᵏ simplifies to a₁(1 − rᵏ⁺¹)/(1 − r).
Q: In the proof that the sum of two even integers is even, a student writes n = 2k and m = 2k. What is the mistake, and how do you fix it?
A: Using the same variable k for both n and m implicitly assumes n = m. The fix: let n = 2j and m = 2k for possibly different integers j and k. Then n + m = 2j + 2k = 2(j + k), which is even.
This connects to algorithm correctness, which you will encounter next: proving a sorting algorithm or a graph algorithm works typically requires an induction argument (often on the number of iterations or the size of the input). Proof by contradiction reappears in computability theory when showing certain problems are undecidable. The asymptotic notation covered in Part 2 of these notes relies on the same logical rigour: proving that one function is O(another) is a direct proof exercise with explicit constants.
direct proof, proof by contrapositive, contrapositive proof, proof by contradiction, indirect proof, reductio ad absurdum, mathematical induction, weak induction, standard induction, strong induction, complete induction, base case, inductive step, inductive hypothesis, domino argument, EECS 376, foundations of computer science, UMich, discrete mathematics, proof techniques, proof methods, faulty proofs, proof errors, geometric series induction, stone splitting problem, √7 irrational proof