Difficulty: Intermediate | Prerequisites: Basic logic, familiarity with recurrence relations
Mathematical induction proves that a statement holds for all natural numbers by establishing a base case and showing the statement carries forward. Weak induction assumes the result for one predecessor; strong induction assumes it for all predecessors. The number and choice of base cases depends on how far back the inductive step reaches. Separately, recursion has limits: problems requiring infinite precision (such as irrational exponentiation) cannot be solved recursively, and a full binary tree requires every internal node to have exactly two children.
Weak induction (simple induction)
A proof technique with three parts: a base case, an inductive hypothesis that assumes P(k), and an inductive step that proves P(k+1). In simple terms, you prove the first domino falls and that each domino knocks over the next.
Strong induction (complete induction)
A variant of induction where the inductive hypothesis assumes P(j) for all j up to k (not just P(k) alone), then proves P(k+1). Think of it as assuming every domino before the current one has already fallen. You need strong induction when the inductive step depends on more than one previous case.
Base case
The starting point of an induction proof: an explicit verification that the statement holds for the smallest value(s). Without it, the chain of reasoning has nothing to start from.
Inductive hypothesis
The assumption you make partway through the proof: that the statement is true for some arbitrary value k (weak) or for all values up to k (strong). This is assumed, not proved, within the inductive step.
Inductive step
The argument that, given the inductive hypothesis, the statement must also hold for k+1. This is where the actual logical work happens.
Full binary tree
A binary tree in which every node has either zero children (a leaf) or exactly two children. A node with only one child violates the definition. Think of it as: no half-branching allowed.
Recursion (in computing)
A method of solving a problem by reducing it to smaller instances of the same problem, with one or more base cases that terminate the process. Not every problem can be solved recursively; the reduction must reach a base case in finitely many steps.
Every induction proof has the same skeleton:
Base case: verify the statement for the smallest input(s)
Inductive hypothesis: assume the statement holds for some value(s)
Inductive step: prove the statement holds for the next value, using the hypothesis
The order matters. In an exam, label each part clearly.
Use weak induction when the inductive step only needs P(k) to prove P(k+1). Use strong induction when the step needs P(k) and P(k-1), or more generally P(j) for all j <= k.
The tell-tale sign you need strong induction: the recurrence or problem looks back more than one step. If proving something about step k+1 requires information about step k-1 as well as step k, weak induction is not enough.
Worked example (region colouring): Given n lines in 2D space, show the regions can be 2-coloured so no two adjacent regions share a colour.
Base case (labelled 1 in the quiz): one line creates two regions; colour one red, one black
Inductive hypothesis (labelled 2): assume the colouring works for n lines
Inductive step (labelled 3): add one more line; invert all colours on one side of the new line, giving a valid colouring for n+1 lines
If P(n) implies P(2n), and you want to prove P(2^k) for all k in the natural numbers (including 0), you start at k = 0, which gives P(2^0) = P(1). Starting at P(0) would not help because doubling 0 stays at 0.
Alice climbs a staircase starting at step 0. At each step, she can move up 1 or 2 steps. The number of ways to reach step n is P(n) = f_(n+1), where f_i is the ith Fibonacci number (f_1 = 1, f_2 = 1, f_i = f_(i-1) + f_(i-2)).
This requires strong induction because step k+1 can be reached from step k or step k-1, so the inductive step needs both P(k) and P(k-1).
Base cases: P(0) = 1 = f_1, P(1) = 1 = f_2
Inductive hypothesis: assume P(k-1) = f_k and P(k) = f_(k+1)
Inductive step: P(k+1) = P(k-1) + P(k) = f_k + f_(k+1) = f_(k+2)
Claim: any order of n >= 8 chicken nuggets can be formed from boxes of 3 and 5.
The inductive step for C(n) uses either C(n-3) or C(n-5). The furthest lookback is 5 steps, but some of those intermediate values overlap. You need three consecutive base cases: C(8), C(9), C(10). From those three, the step can always reach back to at least one verified case.
Why three? Because the step reaches back by 3 or 5. Starting from C(11), C(11-3) = C(8) is covered. C(12-3) = C(9), covered. C(13-3) = C(10), covered. C(14-3) = C(11), which was just proved. The chain is unbroken.
A full binary tree requires that every internal node has exactly two children. A node with only one child breaks the definition. This is distinct from a complete binary tree (all levels full except possibly the last, filled left to right) and a perfect binary tree (all internal nodes have two children and all leaves are at the same depth).
Recursion works when the problem can be broken into strictly smaller sub-problems that reach a base case in finitely many steps. It fails when this is not possible.
Problems solvable by recursion:
Searching an array (binary search halves the problem each step)
Determining that an element is not in a sorted array (same binary search approach)
Computing the nth Fibonacci number (defined recursively by nature)
Problems not solvable by recursion:
Computing an irrational power of a number, because the exponent has infinite precision and the recursion would never terminate
Induction underpins the correctness proofs for recursive algorithms, loop invariants, and protocol verification. Strong induction in particular appears whenever a system's next state depends on multiple previous states, which is common in dynamic programming. The full binary tree definition matters in data structures such as Huffman coding trees and expression trees used in compilers.
Students often use weak induction when the problem requires strong induction. If the inductive step references P(k-1) or earlier, you need strong induction.
Students sometimes forget to prove enough base cases. When the inductive step reaches back m steps, you need m consecutive base cases so the chain has no gap.
A common error is confusing a full binary tree with a complete binary tree. Full means every node has 0 or 2 children. Complete means all levels are filled except possibly the last (filled left to right). These are different properties.
Students sometimes assume recursion can solve any problem. It cannot. The recursion must terminate, which means the problem must reduce to a base case in finitely many steps.
⚠️ Expect to label the base case, inductive hypothesis, and inductive step in a given proof. Know which is which.
⚠️ Be ready to decide between weak and strong induction. The deciding factor is how many previous cases the inductive step needs.
⚠️ Base case selection questions are common: given a recurrence that looks back by 3 and by 5, you need to reason about how many base cases are required and which ones.
⚠️ The staircase/Fibonacci connection is a classic strong induction problem. Know the proof cold.
⚠️ Know the definition of a full binary tree and be able to identify whether a given tree satisfies it by checking every internal node.
True or False: Strong induction assumes P(k) for exactly one value of k. (False, it assumes P(j) for all j <= k.)
Fill in the blank: If P(n) implies P(2n) and the naturals include 0, the base case needed to prove P(2^k) for all k is ______. (P(1), because 2^0 = 1.)
True or False: A binary tree where the root has two children, the left child has two children, and the right child has one child is a full binary tree. (False, the right child violates the full property.)
True or False: Computing an irrational power of a number can be done with recursion. (False, it requires infinite precision.)
Fill in the blank: The number of ways to reach step n on a staircase (1 or 2 steps at a time, starting from step 0) equals the ______ Fibonacci number. ((n+1)th.)
Q: Prove by induction that T(n) = 4 * 3^n + 1 satisfies T(n) = 3T(n-1) - 2 with T(0) = 5.
A: Base case: T(0) = 4 * 3^0 + 1 = 5. Correct. Inductive hypothesis: assume T(k) = 4 * 3^k + 1. Inductive step: T(k+1) = 3T(k) - 2 = 3(4 * 3^k + 1) - 2 = 4 * 3^(k+1) + 3 - 2 = 4 * 3^(k+1) + 1.
Q: A proof shows (1) P(1) and P(2) are true, and (2) for all integers n, if P(n) and P(n+1) then P(n+2). What type of induction is this?
A: Strong induction, because there are multiple base cases and the inductive step assumes the statement for two consecutive values.
Q: You want to prove that any integer n >= 12 can be written as 4a + 5b for non-negative integers a, b. The inductive step uses C(n-4). How many base cases do you need and which ones?
A: Four base cases: C(12), C(13), C(14), C(15). The step reaches back 4, so you need 4 consecutive verified values before the chain can sustain itself.
Q: Is the following tree full? Root has children A and B. A has children C and D. B has child E only. C and D are leaves. E is a leaf.
A: No. Node B has only one child (E), which violates the full binary tree requirement that every internal node has exactly 0 or 2 children.
Q: Can you use recursion to determine whether an element x is absent from a sorted array A? Explain.
A: Yes. Binary search recursively halves the search space. If the middle element is x, return found. If x is less than the middle, recurse on the left half; if greater, recurse on the right half. If the sub-array is empty, x is not present. The recursion terminates because the array shrinks at each step.
Induction is the standard method for verifying closed-form solutions found by backwards substitution (see the companion notes on recurrence relations). Strong induction connects to dynamic programming, where solving a problem depends on solutions to multiple smaller sub-problems. The Fibonacci staircase problem is a classic example that bridges recursion, recurrences, and induction in one problem. Binary tree definitions reappear throughout data structures and algorithms courses, particularly in heap construction, Huffman coding, and syntax tree parsing.
Mathematical induction, weak induction, simple induction, strong induction, complete induction, base case, inductive hypothesis, inductive step, proof by induction, Fibonacci numbers, staircase problem, climbing stairs recursion, chicken nugget theorem, Frobenius, full binary tree, proper binary tree, strictly binary tree, complete binary tree, perfect binary tree, recursion, recursive algorithm, binary search, limits of recursion, irrational power, CS182, foundations of computer science, Purdue CS182