Induction is how you prove something holds for every case in a sequence or structure. You establish a starting point (the base case), assume the statement holds up to some point, then show it must hold for the next. The three variants, mathematical, strong, and structural, differ in how much you get to assume and what kind of object you are reasoning about.
Difficulty: Intermediate | Prerequisites: basic logic, familiarity with propositions and predicates
Induction sits at the heart of discrete mathematics and theoretical computer science. Nearly every proof about algorithms, data structures, or recursion relies on some form of it. If you are taking a foundations or discrete maths course, you will use induction more than almost any other proof technique. The three variants covered here, mathematical induction, strong induction, and structural induction, each apply to slightly different situations, but they share the same logic: establish a foothold, then show the pattern extends.
Basis step (base case)
The initial case you prove directly, without assuming anything. In mathematical induction this is usually P(1). Think of it as the first domino you push over by hand.
Inductive hypothesis
The assumption you get to make during the inductive step. In ordinary induction you assume P(k); in strong induction you assume P(j) for all j from 1 up to k.
Inductive step
The argument that, given the inductive hypothesis, P(k+1) must also hold. This is the core of every induction proof: the part that keeps the chain going.
Mathematical induction (weak induction)
The standard form. Prove P(1), assume P(k), derive P(k+1). In simple terms, you only lean on the immediately preceding case.
Strong induction (complete induction)
A variant where the inductive hypothesis lets you assume P(j) for every j from 1 to k, not just the single case P(k). Useful when proving P(k+1) requires reaching back to earlier cases, not only the one just before.
Structural induction
Induction over recursively defined structures (trees, strings, formulas) rather than integers. The base case covers the simplest elements in the recursive definition; the inductive step shows that if the property holds for the sub-parts, it holds for anything built from them.
Recursively defined function
A function whose value at n is defined in terms of its values at smaller inputs, plus a base case. Think of it as a recipe that refers to its own earlier results.
Used to prove a proposition P(n) for all positive integers n.
State P(n) clearly
Basis step: Prove P(1) is true
Inductive hypothesis: Assume P(k) is true for an arbitrary positive integer k
Inductive step: Using the assumption that P(k) holds, show that P(k+1) must hold
The logic is sequential: each case depends only on the one directly before it. If you can prove the first case and show that any case implies the next, every case is covered.
Same goal as mathematical induction, but with a more powerful hypothesis.
State P(n)
Basis steps: Prove P(1), P(2), and as many initial cases as the inductive step requires
Inductive hypothesis: Assume P(j) holds for every j with 1 ≤ j ≤ k, where k ≥ 2
Inductive step: Using the full hypothesis (all cases up to k), show P(k+1) holds
Strong induction is helpful when proving P(k+1) requires reaching back further than just P(k). A common example is proving properties of binary representations or recursive algorithms where the input may be split into pieces of unequal size.
Used for recursively defined structures (trees, strings, well-formed formulas) rather than integers.
Basis step: Show the property holds for every element specified in the base case of the recursive definition
Recursive step: Assume the property holds for the sub-components used to build a new element. Show it holds for the new element itself
This is the natural proof technique whenever a data structure is defined recursively. If you are asked to prove something about binary trees, parse trees, or recursively defined sets, structural induction is almost certainly what you need.
A function defined by giving its value at the smallest input and a rule for computing later values from earlier ones.
Basis step: Specify the value of the function at 0 (or at the smallest input)
Recursive step: Define f(n) in terms of f at smaller arguments
Example: the number of vertices in a binary tree T is n(T) = n(T₁) + n(T₂) + 1, where T₁ and T₂ are the left and right subtrees. The base case is n(T) = 0 for an empty tree.
Students often think the inductive hypothesis is something you need to prove. It is not. You assume it, then use it to prove the inductive step.
Forgetting the base case is the most common structural error. Without it, the entire proof is invalid, even if the inductive step is flawless.
Students sometimes confuse strong induction with mathematical induction. The difference is scope of the hypothesis: strong induction assumes P(j) for all j up to k, not just P(k).
Structural induction is not limited to trees. It applies to any recursively defined structure, including strings, formulas, and lists.
⚠️ Exams frequently ask you to perform a full induction proof. Know the three-step template cold: state P(n), prove the base case, state the hypothesis, prove the inductive step.
⚠️ Be ready to choose the right variant. If the problem involves integers and P(k+1) only needs P(k), use mathematical induction. If it needs earlier cases, use strong induction. If it involves a recursive structure, use structural induction.
⚠️ Recursive function definitions often appear alongside induction proofs. You may be asked to define a function recursively and then prove a property about it by induction.
True or false: In mathematical induction, the inductive hypothesis assumes P(j) for all j from 1 to k. (False: that is strong induction. Mathematical induction assumes only P(k).)
Fill in the blank: The ______ step is what you prove directly, without assuming anything. (basis / base)
True or false: Structural induction can only be used on binary trees. (False: it applies to any recursively defined structure.)
Fill in the blank: In a recursively defined function, the base step specifies the value at ______. (0, or the smallest input)
True or false: If the inductive step is correct but the base case is missing, the proof is still valid. (False: both are required.)
Q: What are the three steps of mathematical induction?
A: (1) Basis step: prove P(1). (2) Inductive hypothesis: assume P(k). (3) Inductive step: prove P(k+1) using the hypothesis.
Q: When should you use strong induction instead of ordinary mathematical induction?
A: When proving P(k+1) requires assuming P(j) for multiple values of j up to k, not just P(k) alone.
Q: What distinguishes structural induction from mathematical induction?
A: Structural induction works on recursively defined objects (trees, strings, formulas) rather than on positive integers. The base case covers the base elements of the recursive definition, and the inductive step shows the property transfers through the recursive construction.
Q: Give the recursive definition for the number of vertices in a binary tree.
A: n(T) = n(T₁) + n(T₂) + 1, with base case n(T) = 0 for an empty tree. T₁ and T₂ are the left and right subtrees.
Q: In strong induction, what does the inductive hypothesis assume?
A: That P(j) holds for all j satisfying 1 ≤ j ≤ k, where k ≥ 2.
Induction connects directly to recursion in programming: every recursive function has a base case and a recursive case, mirroring the structure of an induction proof. This also ties into algorithm correctness proofs (loop invariants are a close cousin) and to counting arguments where you build a formula and then prove it by induction.
mathematical induction, strong induction, complete induction, structural induction, proof by induction, inductive step, base case, basis step, inductive hypothesis, recursion, recursive definition, recursive functions, binary tree vertices, P(n), P(k+1), discrete mathematics, CS 101, foundations of computer science