Difficulty: Introductory | Prerequisites: Basic set notation, familiarity with summation notation, comfort with algebraic manipulation.
This material covers the two proof techniques you will use most often in EECS 376 and across theoretical computer science: proof by induction and proof by contradiction. Induction is the workhorse for showing that a property holds for every natural number (or every size of input), and contradiction is the standard tool for impossibility results, such as proving a number is irrational. If you are shaky on either technique, nearly every later topic in the course (complexity classes, undecidability, reductions) will feel harder than it needs to.
Proof by induction proves a statement for all natural numbers by checking a base case and then showing that truth at n forces truth at n + 1. Proof by contradiction assumes the opposite of what you want to prove, then derives a logical impossibility, which means the original statement must be true. Both are foundational tools you will reach for repeatedly in this course.
Proof by induction (mathematical induction)
A proof technique for statements of the form "for all natural numbers n >= n_0, P(n) holds." You prove a base case (P(n_0) is true), then prove the inductive step: assuming P(n) is true for some arbitrary n, show P(n + 1) must also be true.
Think of it as a chain of dominoes: knock the first one over (base case), and show that each domino knocks over the next (inductive step).
Base case
The starting point of an inductive proof, where you directly verify the statement for the smallest value of n. Without this, the inductive step has nothing to build on.
In simple terms, this is the first domino you actually push.
Inductive hypothesis
The assumption, within the inductive step, that the statement P(n) holds for some particular n. You then use this assumption to derive P(n + 1).
In simple terms, this is the "suppose it works for n" part of the argument.
Inductive step
The part of the proof where you show that P(n) being true forces P(n + 1) to be true. This is where the real mathematical work happens.
Proof by contradiction
A proof technique where you assume the negation of what you want to prove, then derive a logical contradiction. Since a contradiction cannot be true, the original assumption must be false, so the desired statement must hold.
Think of it as: "suppose the opposite were true, here is why that is impossible, therefore the original claim stands."
Binomial coefficient
Written C(n, k) or "n choose k." Counts the number of ways to choose k items from a set of n items, regardless of order. Defined as n! / (k!(n - k)!).
In simple terms, it answers "how many ways can I pick k things from n things?"
Pascal's identity (the hint)
The relation C(n + 1, k) = C(n, k - 1) + C(n, k) for 1 <= k <= n. Each entry in Pascal's triangle is the sum of the two entries directly above it. This identity is the key algebraic tool in Problem 1's inductive step.
For all positive integers n, the sum of all binomial coefficients C(n, k) for k = 0 to n equals 2^n. In notation: sum_{k=0}^{n} C(n, k) = 2^n.
Compute the left side: C(1, 0) + C(1, 1) = 1 + 1 = 2.
Compute the right side: 2^1 = 2.
Both sides match. The statement holds for n = 1.
Inductive hypothesis: assume sum_{k=0}^{n} C(n, k) = 2^n holds for some particular n.
Goal: show sum_{k=0}^{n+1} C(n+1, k) = 2^{n+1}.
How the algebra works, step by step:
Peel off the first and last terms: the sum becomes C(n+1, 0) + C(n+1, n+1) + sum_{k=1}^{n} C(n+1, k). Both boundary terms equal 1.
Apply Pascal's identity to every remaining term: C(n+1, k) = C(n, k-1) + C(n, k). This splits the middle sum into two sums over C(n, -).
Re-index and recombine: the two sums each telescope into sum_{k=0}^{n} C(n, k).
Apply the inductive hypothesis to each: each sum equals 2^n.
Add: 2^n + 2^n = 2 * 2^n = 2^{n+1}.
Step 2 is where Pascal's identity does the heavy lifting, converting (n+1)-level binomial coefficients into n-level ones so the inductive hypothesis applies.
Step 4 is where the inductive hypothesis is actually invoked, twice.
Without both moves, you cannot close the gap between n and n + 1.
The square root of 2 is irrational (it cannot be expressed as a ratio of two integers).
Assume the opposite: suppose sqrt(2) is rational, so sqrt(2) = a/b for some integers a, b with no common divisors (the fraction is in lowest terms).
Square both sides: 2 = a^2 / b^2, which gives 2b^2 = a^2.
Deduce a is even: since a^2 = 2b^2, a^2 is even. An odd number squared is odd (check: (2m+1)^2 = 4m^2 + 4m + 1), so a itself must be even. Write a = 2m.
Deduce b is even: substituting a = 2m gives 2b^2 = 4m^2, so b^2 = 2m^2. By the same reasoning, b is also even.
Arrive at contradiction: both a and b are even, meaning they share the factor 2. But we assumed they have no common divisors. Contradiction.
Conclude: the assumption that sqrt(2) is rational must be false. Therefore sqrt(2) is irrational.
The "lowest terms" assumption is essential. Without it, you cannot reach a contradiction, because two even numbers can share a factor of 2 without issue unless you have already stipulated they do not.
The parity argument (odd squared is odd, even squared is even) is the engine of the proof. It gets used twice, once for a and once for b.
Binomial coefficient:
C(n, k) = n! / (k!(n - k)!)
Binomial theorem (the identity proved in Problem 1):
sum_{k=0}^{n} C(n, k) = 2^n
This is a special case of the binomial theorem with x = y = 1: (1 + 1)^n = sum C(n,k) * 1^k * 1^{n-k} = 2^n.
Pascal's identity:
C(n+1, k) = C(n, k-1) + C(n, k), for 1 <= k <= n
Parity of squares:
If a is even, a^2 is even.
If a is odd, a^2 is odd. (Because (2m+1)^2 = 4m^2 + 4m + 1, which is odd.)
Induction underpins the correctness proofs for recursive algorithms. Any time you write a recursive function and need to argue it produces the right answer, you are doing induction, whether you call it that or not. Proof by contradiction is the backbone of security and cryptography arguments: showing that breaking a system would require solving a problem known to be impossible (or computationally infeasible).
Students often skip the base case or treat it as a formality. It is not. Without a verified base case, the inductive step proves nothing. You can "prove" false statements by induction if you omit the base case.
Students sometimes confuse the inductive hypothesis with what they are trying to prove. The hypothesis is an assumption you make (P(n) is true); the goal is to derive P(n+1) from it. You are not assuming what you are proving.
In proof by contradiction, students sometimes forget to state clearly what they are assuming. If you do not write down the negation explicitly, the contradiction at the end has nothing to contradict.
A common error in the sqrt(2) proof is forgetting the "lowest terms" stipulation. Without it, both a and b being even is not a contradiction, it just means you can simplify the fraction further.
⚠️ Induction problems appear on nearly every EECS 376 exam. Expect to prove summation identities, properties of recursive structures, or bounds on running time.
⚠️ You must state the base case, inductive hypothesis, and inductive step as separate, labelled parts. Exams typically deduct marks for missing labels.
⚠️ Proof by contradiction is the standard approach whenever you need to show something is impossible (e.g. a number is irrational, a language is undecidable). Recognising when to reach for it is half the battle.
⚠️ Pascal's identity is a frequently tested algebraic tool. Be comfortable applying it both left-to-right and right-to-left.
True or false: in a proof by induction, you can choose any value for the base case, even n = 1000. Answer: True, as long as the statement is meant to hold for n >= 1000 and the inductive step covers all larger n.
Fill in the blank: Pascal's identity states C(n+1, k) = C(n, ___) + C(n, k). Answer: k - 1.
True or false: in the sqrt(2) irrationality proof, if we did not assume the fraction a/b was in lowest terms, the proof would still work. Answer: False. The contradiction depends on a and b sharing no common divisors.
True or false: the inductive hypothesis is the thing you are trying to prove. Answer: False. The inductive hypothesis is an assumption; you are trying to prove the inductive step using it.
Q: Prove by induction that 1 + 2 + 3 + ... + n = n(n+1)/2 for all n >= 1. What are the three labelled parts of your proof?
A: Base case (n = 1, check 1 = 1*2/2 = 1). Inductive hypothesis (assume the formula holds for some n). Inductive step (show 1 + 2 + ... + n + (n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2). The three parts are: base case, inductive hypothesis, inductive step.
Q: In the proof that sqrt(2) is irrational, why is the assumption that a/b is in lowest terms necessary?
A: Because the contradiction arises from showing a and b are both even (share a factor of 2). If we had not required that a and b share no common divisors, both being even would not be a contradiction, it would just mean we could simplify the fraction.
Q: Where exactly in the HW0 induction proof is Pascal's identity used, and where is the inductive hypothesis used?
A: Pascal's identity is used going from step (1) to step (2), to rewrite C(n+1, k) as C(n, k-1) + C(n, k). The inductive hypothesis is used going from step (5) to step (6), replacing each sum of C(n, k) with 2^n.
Q: Suppose you attempt a proof by contradiction and cannot derive a contradiction. What does that tell you?
A: It does not tell you the statement is false. It tells you that this particular approach did not work. The statement might still be true but require a different proof strategy, or it might be false and provable by counterexample.
Induction connects directly to recursion and recursive algorithm design. When you prove an algorithm correct using a loop invariant, you are doing a form of induction. Proof by contradiction connects to the later EECS 376 topics of undecidability and reductions: showing that a language is undecidable typically involves assuming a decider exists and deriving a contradiction. The binomial theorem itself reappears in probability (binomial distributions) and combinatorics.
mathematical induction, proof by contradiction, indirect proof, reductio ad absurdum, base case, inductive step, inductive hypothesis, Pascal's identity, Pascal's triangle, binomial coefficient, n choose k, binomial theorem, irrationality of sqrt(2), parity argument, even and odd integers, EECS 376, foundations of computer science, University of Michigan