Source: Section Notes 0, University of Michigan
Difficulty: Intermediate | Prerequisites: Basic set theory, familiarity with integers and divisibility.
Proof methods are the foundational toolkit for all of theoretical computer science. Before you can reason about algorithms, complexity, or computability, you need to be able to prove that statements are true (or false). This material sits right at the start of EECS 376 because every later topic, from Big-O analysis to undecidability, relies on at least one of these techniques. If you have taken a discrete maths course, most of this will be revision; if not, treat it as essential groundwork.
There are four standard proof techniques you will use throughout this course: induction (for statements about all positive integers), contradiction (assume the opposite, find something impossible), contrapositive (flip the direction of an implication), and the pigeonhole principle (more items than bins means at least one bin has two). Master the structure of each, and most EECS 376 proofs become a matter of recognising which one fits.
Proof by induction
A technique for proving a statement P(n) holds for every positive integer (or every nonnegative integer). You show a base case and an inductive step. Think of it as knocking over an infinite line of dominoes: prove the first one falls, then prove that any falling domino knocks over the next.
Base case
The starting point of an induction proof, where you verify P(n) directly for the smallest value of n (often n = 0 or n = 1).
Inductive step (inductive hypothesis)
The part of an induction proof where you assume P(k) is true for some arbitrary k and then show P(k + 1) follows. The assumption that P(k) holds is called the inductive hypothesis.
Proof by contradiction
A technique where you assume the statement you want to prove is false, then derive something impossible (a contradiction). Since the assumption leads to nonsense, the original statement must be true. In simple terms, you show that the world breaks if the statement is wrong.
Contrapositive
The contrapositive of an implication P ⇒ Q is ¬Q ⇒ ¬P. The two are logically equivalent, so proving the contrapositive is the same as proving the original. In simple terms, instead of proving "if it rains then the ground is wet", you prove "if the ground is dry then it did not rain".
Pigeonhole principle
If you place n items into m boxes and n > m, at least one box must contain more than one item. Think of it as: if 6 people sit in 5 chairs, somebody is sharing.
Induction proves a statement P(n) for every member of a countably infinite set (typically the positive or nonnegative integers). The recipe has two parts:
Base case. Show P(n) is true for the smallest relevant n.
Inductive step. Assume P(k) holds for an arbitrary k (the inductive hypothesis) and show that P(k + 1) follows.
Once both parts are done, P(n) is established for all n from the base case upward.
Claim. A set S with n elements has 2^n subsets.
Let P(n) be the statement "a set of size n has 2^n subsets".
Base case (n = 0). The empty set has exactly one subset (itself). 2^0 = 1. So P(0) holds.
Inductive step. Assume P(k) is true: any set of size k has 2^k subsets. Take a set S of size k + 1 and single out one element a.
Subsets of S that do not contain a are exactly the subsets of S \ {a}, a set of size k. By the inductive hypothesis there are 2^k of these.
Subsets of S that do contain a are formed by taking any subset of S \ {a} and adding a. There are again 2^k of these.
Total subsets: 2^k + 2^k = 2^(k+1). So P(k + 1) holds.
This completes the induction.
To prove a statement P, assume P is false and derive something logically impossible. Because the assumption leads to a contradiction, P must be true.
Claim. There are infinitely many prime numbers.
Assume for contradiction that there are only finitely many primes: p₁, p₂, ..., pₘ.
Construct q = 1 + (p₁ × p₂ × ... × pₘ).
q is an integer greater than 1, so it has at least one prime divisor p.
Can p be any pⱼ on the list? If pⱼ divides q and pⱼ divides the product p₁ × ... × pₘ, then pⱼ divides their difference, which is q − (p₁ × ... × pₘ) = 1. No prime divides 1, so p is not on the list.
This contradicts the assumption that the list contains every prime. Therefore, there are infinitely many primes.
To prove P ⇒ Q, you can instead prove ¬Q ⇒ ¬P. These are logically equivalent. This is useful when the negation of the conclusion gives you something concrete to work with.
Claim. Let a, b ∈ ℤ. If ab is odd, then a and b are both odd.
The contrapositive: if a or b is even, then ab is even.
Without loss of generality, suppose a is even. Then a = 2k for some integer k.
ab = 2kb, which is even.
The contrapositive is proved, so the original statement holds.
If n items are placed in m boxes and n > m, at least one box contains more than one item. Simple to state, surprisingly powerful in proofs.
Claim. Among any 6 people at a party, either 3 of them are mutual friends or 3 of them are mutual strangers.
Pick person A. Classify the other 5 people as "friend of A" or "stranger to A".
By the pigeonhole principle (5 people, 2 categories), one category has at least 3 people. Suppose A has at least 3 friends: B, C, D.
Case 1: B, C, D are all friends with each other. Then {B, C, D} is a group of 3 mutual friends.
Case 2: Exactly two of B, C, D are friends, say B and C. Then {A, B, C} is a group of 3 mutual friends (A is friends with both, and B and C are friends).
Case 3: None of B, C, D are friends with each other. Then {B, C, D} is a group of 3 mutual strangers.
All cases produce the required group. (If A has at least 3 strangers instead, the same reasoning applies with the roles swapped.)
Induction template
State P(n).
Prove P(base) directly.
Assume P(k) (the inductive hypothesis).
Prove P(k + 1) using the assumption.
Power set cardinality: |𝒫(S)| = 2^n where |S| = n.
Euclid's construction (contradiction proof for primes): q = 1 + p₁ × p₂ × ... × pₘ.
Contrapositive equivalence: (P ⇒ Q) ⟺ (¬Q ⇒ ¬P).
Pigeonhole bound: n items in m boxes, n > m ⇒ at least one box has ≥ 2 items.
Students often think the base case is optional or unimportant. It is essential: without it, the inductive step proves nothing. You can "prove" false statements if you skip the base case.
In proof by contradiction, students sometimes confuse "assume P is false" with "assume the negation of the conclusion". Contradiction assumes the entire statement is false, whereas contrapositive negates only the conclusion.
Students frequently confuse the contrapositive (¬Q ⇒ ¬P) with the converse (Q ⇒ P). The converse is not logically equivalent to the original implication.
With the pigeonhole principle, a common error is trying to use it when n ≤ m. The principle only guarantees a collision when you have strictly more items than boxes.
⚠️ Induction is the single most-used proof technique in EECS 376. Expect to write at least one induction proof on every exam.
⚠️ Proof by contradiction appears in major theorems later in the course (the halting problem, for instance). Know the structure cold.
⚠️ Contrapositive proofs are especially common in questions about divisibility and parity, and they often appear as "show that if ... then ..." problems.
⚠️ The pigeonhole principle shows up in combinatorics and graph theory arguments. The party problem (Proposition 1.4 in the notes) is a classic exam-style question.
True or false: In an induction proof, the base case can be any value of n you like. (True, provided you prove P(n) for all n from that value onward.)
Fill in the blank: The contrapositive of P ⇒ Q is ____. (¬Q ⇒ ¬P)
True or false: In proof by contradiction, you assume the statement you want to prove is true. (False. You assume it is false.)
Fill in the blank: If 10 socks are placed in 4 drawers, at least one drawer contains at least ____ socks. (3)
True or false: The converse of an implication is logically equivalent to the original. (False.)
Q: Prove by induction that the sum 1 + 2 + ... + n = n(n + 1)/2 for all positive integers n.
A: Base case: n = 1. The left side is 1, and the right side is 1(2)/2 = 1. They match. Inductive step: assume the formula holds for k, so 1 + 2 + ... + k = k(k + 1)/2. Adding (k + 1) to both sides gives k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is the formula with n = k + 1.
Q: Prove by contradiction that √2 is irrational.
A: Assume √2 = a/b where a and b are integers with no common factor. Then 2 = a²/b², so a² = 2b². This means a² is even, so a is even (write a = 2c). Substituting: 4c² = 2b², so b² = 2c², meaning b is also even. But then a and b share the factor 2, contradicting the assumption that they have no common factor.
Q: What is the contrapositive of "if n² is even, then n is even"?
A: If n is odd, then n² is odd.
Q: At a conference of 13 people, prove that at least two of them were born in the same month.
A: There are 12 months and 13 people. By the pigeonhole principle (13 > 12), at least two people must share a birth month.
Induction reappears throughout EECS 376 whenever you need to prove a property of a recursively defined structure (grammars, trees, recursive algorithms). Proof by contradiction is the engine behind major impossibility results later in the course, including the undecidability of the halting problem. The pigeonhole principle connects to graph theory (e.g. showing that a graph of n nodes with enough edges must contain a cycle) and to counting arguments in combinatorics.
Mathematical induction, strong induction, structural induction, base case, inductive hypothesis, inductive step, proof by contradiction, indirect proof, reductio ad absurdum, contrapositive, converse, inverse, logically equivalent, pigeonhole principle, Dirichlet's box principle, combinatorial argument, power set, prime numbers, Euclid's theorem, parity argument, EECS 376, discrete maths proofs, proof techniques