Induction is a generalized conclusion coming from multiple examples.
In order to be rigorous, proofs by induction have a strict structure that is easy to follow.
This is one of the main tools to prove correctness in computer science (loop invariants, recursive functions, algorithmic complexity).
You will learn to prove by induction with many examples — sums, inequalities, set counting, and a strong-induction geometry example.
Python / SymPy — imports (run once)from sympy import symbols, Sum, simplify, factorial, log, oo, Rational
from functools import lru_cache
import math
k, n, i, j = symbols('k n i j', integer=True, positive=True)
2 / 13
Principle of Induction
The truth of an infinite sequence of propositions $p_i$ for $i = b, b+1, b+2, \dots, \infty$ is established if:
$p_b$ is true (base step)
$p_k \Rightarrow p_{k+1}$ (inductive step)
$b,\; b+1,\; b+2,\; \dots$
This works because $\mathbb{N}$ has the well-ordering property: every non-empty subset has a least element. So if $p_n$ failed somewhere, there would be a smallest failure $n_0 > b$, but then $p_{n_0 - 1}$ holds and by the inductive step $p_{n_0}$ must hold — contradiction.
Domino metaphor: if the first domino falls (base) and each falling domino knocks over the next (step), the whole chain falls.
3 / 13
Method
Inductive proofs always have the same three-step structure, making them easy to follow:
BSBase step — verify that $p_b$ is true (usually $b = 0$ or $1$).
IHInductive hypothesis — assume $p_i$ is true for all $b \le i \le k$.
Set example — a set of $n$ elements has $2^n$ subsets
BS$n = 0$: the empty set has only one subset — itself, $\varnothing$. So $|\mathcal{P}(\varnothing)| = 1 = 2^0$. ✓
IHAssume a set of $i$ elements has $2^i$ subsets, for all $i \leq k$.
ISConsider a set $S$ with $k + 1$ elements. Pick one element $e \in S$ and split the subsets of $S$ in two:
Subsets not containing $e$ — these are exactly the subsets of $S \setminus \{e\}$, of which there are $2^k$ by IH.
Subsets containing $e$ — add $e$ to each subset of $S \setminus \{e\}$: another $2^k$.
Total: $2 \cdot 2^k = 2^{k+1}$. $\square$
Python — empirical for small nfrom itertools import chain, combinations
def powerset(s):
s = list(s)
return list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))
for n in range(0, 8):
S = set(range(n))
assert len(powerset(S)) == 2 ** n
print("|P(S)| = 2^|S| verified for n in [0, 7] ✓")
Python — check & visualizeimport math
for n in range(4, 21):
assert 2**n < math.factorial(n)
print("2^n < n! on [4, 20] ✓")
for n in range(1, 11):
print(f"{n:>2}: 2^n = {2**n:>10} n! = {math.factorial(n):>10}")
SymPy — asymptotic growthfrom sympy import symbols, factorial, limit, oo
n = symbols('n', positive=True, integer=True)
print(limit(factorial(n) / 2**n, n, oo)) # oo
# factorial grows faster than exponential
7 / 13
Real example — $\ln(n) \leq \displaystyle\sum_{i=1}^{n} \dfrac{1}{i}$
BS$n = 1$: $\ln 1 = 0 \leq 1 = \dfrac{1}{1}$. ✓
IHAssume $\ln(j) \leq \displaystyle\sum_{i=1}^{j} \dfrac{1}{i}$ for all $j \leq k$.
Python — numerical checkimport math
for n in range(1, 1001):
H = sum(1/i for i in range(1, n+1)) # n-th harmonic number
assert math.log(n) <= H + 1e-12
print("ln(n) ≤ H_n on [1, 1000] ✓")
Equivalently $H_n = \sum_{i=1}^n 1/i$ behaves like $\ln(n) + \gamma$ for large $n$ — the Euler–Mascheroni constant.
8 / 13
Strong Induction
Same goal: establish $p_b, p_{b+1}, \dots, p_\infty$. The difference is in the inductive step:
BSVerify that $p_b$ is true.
IHAssume that $p_i$ is true for all $b \leq i \leq k$.
Strong induction uses the full history of previous cases, not just the immediate predecessor. It is essential when the recurrence reaches back several steps (e.g. $a_n = a_{n-1} + a_{n-2}$, or proofs that split the object into two smaller pieces of unknown size).
Equivalence: strong induction and (weak) induction are logically equivalent over $\mathbb{N}$. Strong induction is just more convenient when the natural argument refers to several smaller cases.
9 / 13
Geometry example — triangulating a polygon
Lemma: every simple polygon with at least four sides has an interior diagonal.
Theorem (by strong induction): a simple polygon with $n$ sides ($n \geq 3$) can be triangulated into exactly $n - 2$ triangles.
BS$n = 3$ (a triangle): $3 - 2 = 1$ triangle. ✓
IHAll simple polygons of size $i$ can be triangulated into $i - 2$ triangles, $\forall\,3 \leq i \leq k$.
ISConsider a polygon with $k + 1$ sides, $k \geq 3$, so $k + 1 \geq 4$.
By the lemma, it has an interior diagonal — call it $d$.
The diagonal $d$ separates the polygon into two smaller polygons with $a + 1$ and $(k + 1) - a + 1$ sides (for some $3 \leq a \leq k$).
By the strong IH, the two pieces yield $(a + 1) - 2$ and $(k + 1 - a + 1) - 2$ triangles respectively.
Total: $(a - 1) + (k - a) = k - 1 = (k + 1) - 2$ triangles. $\square$
10 / 13
Programming connection — recursion ↔ induction
Inductive proofs are most intuitive when applied to recursive definitions. Every recursive function corresponds to an inductive structure:
Base case of the function = base step of the induction.
Recursive call on smaller input = use of the inductive hypothesis.
Combining the recursive result = the inductive step.
Python — factorial as recursive (= inductive) definitionfrom functools import lru_cache
@lru_cache
def fact(n):
if n == 0: # BASE STEP
return 1
return n * fact(n-1) # INDUCTIVE STEP (uses fact(n-1) which is the IH)
print([fact(k) for k in range(7)]) # [1, 1, 2, 6, 24, 120, 720]
Python — Fibonacci needs STRONG induction (depends on 2 previous values)@lru_cache
def fib(n):
if n < 2: # BASE STEP for n = 0, 1
return n
return fib(n-1) + fib(n-2) # uses TWO previous IHs
print([fib(k) for k in range(10)]) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Loop invariants in algorithm analysis are proven by induction on the loop counter. This is how correctness proofs of algorithms (binary search, merge sort, …) work.
11 / 13
Common pitfalls
Forgetting the base step — a missing base step can let you "prove" a false statement. Example fallacy: "all horses are the same colour" — the trick is hidden in $n = 1 \to n = 2$.
Wrong starting index — if $b = 4$, you must verify $p_4$, not $p_1$. ($2^n < n!$ fails for $n = 1, 2, 3$.)
Misusing IH — the inductive hypothesis can only be used to replace the part you've isolated; you cannot assume the whole next case.
Off-by-one in sums — when going from $\sum_{i=1}^{k}$ to $\sum_{i=1}^{k+1}$, the extra term is $a_{k+1}$, not $a_k$.
Empirical ≠ proof — testing in Python on a million values is not a proof. Conjecture: $n^2 + n + 41$ is prime for all $n$? Holds for 40 values then fails!
Python — empirical evidence is not a prooffrom sympy import isprime
first_fail = next(n for n in range(1000) if not isprime(n*n + n + 41))
print(first_fail) # 40 (= 1681 = 41 * 41)
12 / 13
Summary
Both simple and strong induction are based on the well-ordering of discrete sets.
Each induction has three parts: base step, inductive hypothesis, inductive step.
Inductive proofs do not give clear insight into why the statement is true — they only confirm that it is.
They are most intuitively applied to recursive definitions, which is the bridge to algorithms and complexity proofs.
Python — key tools for this lessonimport math
from functools import lru_cache
from itertools import chain, combinations
from sympy import symbols, Sum, simplify, factorial, log, limit, oo, Rational, isprime