Difficulty: Intermediate | Prerequisites: Familiarity with basic set notation, binomial coefficients, and the definition of rational vs. irrational numbers.
Proof techniques are the core toolkit of EECS 376 and of theoretical computer science more broadly. Before you can reason about whether problems are solvable, how fast algorithms run, or what a machine can compute, you need to be able to prove things rigorously. This unit covers two of the most common proof methods: mathematical induction (for statements about all integers above some threshold) and proof by contradiction (for showing something cannot exist or cannot be true). If you are comfortable writing these two proof types cleanly, you have the foundation for nearly every argument in the rest of the course.
Induction lets you prove a statement holds for every integer n above some base case: prove it for the base, then show that if it holds for n it must hold for n + 1. Proof by contradiction assumes the opposite of what you want to prove and derives a logical impossibility, which forces the original claim to be true. Both appear constantly in EECS 376 problem sets and exams.
Mathematical induction
A proof technique for statements of the form "for all integers n >= n₀, P(n) is true." You prove the base case P(n₀), then prove that P(n) implies P(n + 1). Think of it as toppling an infinite line of dominoes: knock the first one over, and show each domino knocks over the next.
Base case
The smallest value of n for which you verify the statement directly. In simple terms, this is your starting domino.
Inductive hypothesis
The assumption, within an induction proof, that P(n) holds for some arbitrary n. You then use this assumption to derive P(n + 1). In simple terms, this is the "suppose it works for n" step.
Inductive step
The argument showing that if P(n) is true, then P(n + 1) must also be true. This is where the actual mathematical work happens.
Binomial coefficient
Written C(n, k) or "n choose k," it counts the number of ways to choose k items from a set of n items. Formally: C(n, k) = n! / (k!(n - k)!). Think of it as the number of distinct committees of size k you can form from n people.
Pascal's identity
The relation C(n, k) = C(n - 1, k - 1) + C(n - 1, k), valid for 0 < k < n. This is the rule behind Pascal's triangle: each entry is the sum of the two entries above it.
Proof by contradiction
A proof technique where you assume the negation of what you want to prove and show that this assumption leads to a logical contradiction. The contradiction forces the original statement to be true.
Irrational number
A real number that cannot be expressed as a ratio a/b of two integers. Classic examples include the square root of 2 and the square root of 19. In simple terms, its decimal expansion goes on forever without repeating.
Lowest terms (reduced form)
A fraction a/b where a and b share no common divisors other than 1. This is the standard starting assumption in irrationality proofs: if a/b exists, we can always reduce it to lowest terms.
Claim: State precisely what you are proving, including the range of n.
Base case: Verify the claim for the smallest valid n by direct computation.
Inductive hypothesis: Assume the claim holds for some arbitrary integer n (within the valid range).
Inductive step: Using the hypothesis, prove the claim for n + 1.
Conclusion: By the principle of mathematical induction, the claim holds for all n in the stated range.
Claim: For any integer n > 1, the sum from k = 1 to n - 1 of C(n, k) equals 2ⁿ - 2.
Why 2ⁿ - 2? The binomial theorem says the sum from k = 0 to n of C(n, k) equals 2ⁿ. Subtracting the k = 0 term (which is 1) and the k = n term (which is also 1) leaves 2ⁿ - 2. The induction proof below does not rely on knowing this, but it helps to see why the result is plausible.
Base case (n = 2):
Sum from k = 1 to 1 of C(2, k) = C(2, 1) = 2.
2² - 2 = 2. Checks out.
Inductive hypothesis: Assume the sum from k = 1 to n - 1 of C(n, k) = 2ⁿ - 2 for some n >= 2.
Inductive step (prove for n + 1):
Write the sum from k = 1 to n of C(n + 1, k).
Apply Pascal's identity: C(n + 1, k) = C(n, k - 1) + C(n, k).
Split into two sums: the sum of C(n, k - 1) from k = 1 to n, plus the sum of C(n, k) from k = 1 to n.
Re-index the first sum (substitute j = k - 1) to get the sum of C(n, j) from j = 0 to n - 1.
Separate the j = 0 term: C(n, 0) = 1, plus the sum from j = 1 to n - 1 of C(n, j).
In the second sum, separate the k = n term: sum from k = 1 to n - 1 of C(n, k), plus C(n, n) = 1.
Apply the inductive hypothesis to both inner sums (each equals 2ⁿ - 2).
Result: (1 + 2ⁿ - 2) + (2ⁿ - 2 + 1) = 2(2ⁿ) - 2 = 2ⁿ⁺¹ - 2.
Key move: Pascal's identity is what connects C(n + 1, k) back to things involving C(n, ·), which is where the inductive hypothesis lives. Without it, you have no bridge from n + 1 back to n.
Assume the negation: State the opposite of what you want to prove.
Derive consequences: Use valid logical and mathematical steps to work out what must follow from the assumption.
Reach a contradiction: Show that the consequences conflict with each other or with a known fact.
Conclude: Since the assumption leads to impossibility, the original claim must be true.
Claim: √19 is irrational.
Proof:
Assume for contradiction that √19 is rational. Then √19 = a/b for some integers a, b, with a/b in lowest terms (so a and b share no common divisors).
Square both sides: 19 = a²/b², so 19b² = a².
This means a² is a multiple of 19. Because 19 is prime, a itself must be a multiple of 19. (If a's prime factorisation did not include 19, then a²'s wouldn't either.)
Write a = 19m for some integer m. Substituting: 19b² = (19m)² = 361m², so b² = 19m².
By the same argument, b must also be a multiple of 19.
But now both a and b are multiples of 19, contradicting the assumption that a/b is in lowest terms.
Therefore √19 is irrational.
Why 19 being prime matters: The argument hinges on the fact that if p is prime and p divides a², then p divides a. This is a consequence of the fundamental theorem of arithmetic (unique prime factorisation). The same proof structure works for √p for any prime p. It also works for √n whenever n is not a perfect square, though the argument needs a slight adjustment when n has repeated prime factors.
Pascal's identity:
C(n, k) = C(n - 1, k - 1) + C(n - 1, k), for 0 < k < n.
Binomial theorem (background):
Sum from k = 0 to n of C(n, k) = 2ⁿ. This is the special case of (1 + x)ⁿ = sum of C(n, k) x^k, evaluated at x = 1.
Result proved by induction:
Sum from k = 1 to n - 1 of C(n, k) = 2ⁿ - 2. Equivalently, remove the k = 0 and k = n endpoints from the full binomial sum.
Irrationality argument core step:
If p is prime and p divides a², then p divides a. This follows from the uniqueness of prime factorisation.
Induction underpins the correctness proofs for recursive algorithms and data structures. When you prove that a sorting algorithm works, or that a tree traversal visits every node, you are running an induction argument. Proof by contradiction is the backbone of impossibility results in computer science, including the proof that the halting problem is undecidable, one of the central results you will encounter later in EECS 376.
Students often start induction at n = 1 without checking whether the claim is even stated for n = 1. Always read the problem: the base case here is n = 2, not n = 1.
Students sometimes "prove" the inductive step by assuming what they are trying to show. The inductive hypothesis is about n, and you must derive the statement for n + 1 from it, not assume n + 1 directly.
In contradiction proofs, students sometimes reach a statement that looks wrong but is not a genuine logical contradiction. A contradiction must be of the form "X and not X" simultaneously (e.g. a and b share no common factor, yet both are divisible by 19).
Students sometimes forget to state that the fraction is in lowest terms before beginning the irrationality argument. Without this assumption, there is no contradiction to reach.
⚠️ Induction proofs are among the most commonly tested items in EECS 376. Expect at least one on every exam.
⚠️ The re-indexing trick (shifting the summation variable) appears in many induction problems involving sums. Practise it until it feels mechanical.
⚠️ Irrationality proofs by contradiction follow a near-identical template for any prime p. If you can do √19, you can do √p for any prime.
⚠️ Graders look for explicit labelling of the base case, inductive hypothesis, and inductive step. Missing any one of these labels can cost marks even if the mathematics is correct.
True or false: In an induction proof, the base case must always be n = 0 or n = 1.
False. The base case is whatever the smallest value in the claim's range is. Here it was n = 2.
Fill in the blank: Pascal's identity states that C(n, k) = C(n - 1, ___) + C(n - 1, ___).
k - 1; k.
True or false: To prove √19 is irrational, you must show that 19 is prime.
True, because the key step (p divides a² implies p divides a) relies on primality.
Fill in the blank: In a proof by contradiction, you begin by assuming the ___ of the statement you want to prove.
negation (or "opposite").
True or false: If you successfully complete the inductive step but forget the base case, your proof is complete.
False. Both the base case and the inductive step are required.
Q: Prove by induction that the sum from i = 1 to n of i = n(n + 1)/2.
A: Base case n = 1: sum = 1 = 1(2)/2. Inductive step: assume the sum to n equals n(n + 1)/2. Then the sum to n + 1 equals n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, completing the proof.
Q: Prove that √7 is irrational.
A: Assume √7 = a/b in lowest terms. Then 7b² = a², so a is a multiple of 7 (since 7 is prime). Write a = 7m, giving b² = 7m², so b is also a multiple of 7. This contradicts lowest terms.
Q: In the binomial coefficient induction proof, why is the base case n = 2 rather than n = 1?
A: When n = 1, the sum runs from k = 1 to k = 0, which is an empty sum (equals 0). The formula gives 2¹ - 2 = 0, so it holds vacuously. However the problem specifies n > 1, so n = 2 is the natural base case where something non-trivial happens.
Q: What goes wrong if you try to prove √4 is irrational using the same contradiction template?
A: You would get a² = 4b², so a = 2m, giving b² = m². This means a/b = 2m/b, but the argument does not force b to share a factor with a. In fact √4 = 2 is rational, so no contradiction arises. The template works only when the number under the radical is not a perfect square.
Induction connects directly to the analysis of recursive algorithms: proving a recurrence relation correct is an induction proof. It also ties to strong induction, which you will use later in EECS 376 when a single predecessor is not enough (e.g. proving properties of context-free grammars). Proof by contradiction is the engine behind diagonalisation arguments, which appear in the undecidability unit. The "assume a/b in lowest terms" move reappears whenever you need to reason about the structure of rational numbers in number theory or cryptography.
Mathematical induction, strong induction, proof by contradiction, indirect proof, reductio ad absurdum, binomial coefficient, n choose k, Pascal's identity, Pascal's triangle, binomial theorem, irrational number, rational number, lowest terms, reduced fraction, coprime, prime factorisation, fundamental theorem of arithmetic, EECS 376, foundations of computer science, University of Michigan