Well-ordering principle. Every non-empty subset $S \subseteq \mathbb{N}$ has a least element: $\exists m \in S,\;\forall n \in S,\;m \leq n$.
WOP is taken as an axiom of the natural numbers. It is equivalent to weak induction (next slide) and to strong induction (slide 16). Any one of the three can be taken as the foundational principle and the other two proved as theorems.
The set $S = \{n \in \mathbb{N} : n^2 \geq 20\}$ is non-empty (contains $5$). By WOP it has a least element. Computing: $4^2 = 16 < 20$ but $5^2 = 25 \geq 20$, so $\min S = 5$.
WOP fails on $\mathbb{Z}$: the set $\mathbb{Z}$ itself has no least element. It also fails on $\mathbb{Q}_{\geq 0}$: the interval $(0, 1) \cap \mathbb{Q}$ is non-empty and has no minimum. WOP is the defining property of $\mathbb{N}$ — it expresses the absence of an "infinite descent".
Rosen 8e §5.2; Halmos §17.
4 / 38
1.2 Weak induction (PWI)
Principle of weak induction. Let $P(n)$ be a predicate on $\mathbb{N}$. If
Base case: $P(0)$ holds, and
Inductive step: for every $k \in \mathbb{N}$, $P(k) \to P(k+1)$,
then $\forall n \in \mathbb{N},\, P(n)$.
The base may be shifted: if $P(n_0)$ holds and $\forall k \geq n_0,\, P(k) \to P(k+1)$, then $\forall n \geq n_0,\, P(n)$.
WOP $\Leftrightarrow$ PWI.
(WOP ⇒ PWI.) Suppose WOP and the two PWI hypotheses. Let $S = \{n : \neg P(n)\}$. If $S \neq \varnothing$, by WOP it has a minimum $m$; $m \neq 0$ (base), so $m - 1 \in \mathbb{N}$. By minimality, $P(m-1)$ holds; by the step, $P(m)$ holds — contradiction. (PWI ⇒ WOP.) Suppose PWI. Let $S \subseteq \mathbb{N}$ non-empty without minimum; we derive a contradiction by induction on $n$ that $n \notin S$ for every $n$ (so $S = \varnothing$). Base: $0 \notin S$ (else $0$ would be the minimum). Step: if no $k \leq n$ is in $S$ then $n+1 \notin S$ (else $n+1$ would be the minimum). By PWI, $\forall n, n \notin S$. $\square$
Rosen 8e §5.2 Theorem 1; Velleman 3e §6.4.
5 / 38
2. The induction template
To prove $\forall n \geq n_0,\, P(n)$ by induction:
Base case. Show $P(n_0)$ explicitly.
Inductive hypothesis (IH). Fix an arbitrary $k \geq n_0$ and assume $P(k)$.
Inductive step. Using IH, prove $P(k+1)$.
Conclude: by induction, $\forall n \geq n_0,\, P(n)$. $\square$
Skipping the base case is fatal: the step alone proves only "if $P(n_0)$, then $\forall n \geq n_0,\,P(n)$" — useless when $P(n_0)$ is false.
The next slides apply this template to 12 different examples: sums, inequalities, divisibility, sets, and geometry.
Rosen 8e §5.1; Velleman 3e §6.1.
6 / 38
3.1 Example — $\sum_{i=1}^{n} i = n(n+1)/2$
For every $n \geq 1$, $\;\displaystyle \sum_{i=1}^{n} i = \frac{n(n+1)}{2}.$
Base ($n = 1$). LHS $= 1$, RHS $= 1 \cdot 2 / 2 = 1$. ✓ Step. Assume $P(k)$: $\sum_{i=1}^k i = k(k+1)/2$. Then
$\sum_{i=1}^{k+1} i = \tfrac{k(k+1)}{2} + (k+1) = \tfrac{k(k+1) + 2(k+1)}{2} = \tfrac{(k+1)(k+2)}{2}.$ ✓ $\square$
Python — verificationdef somme_n(n):
return sum(range(1, n + 1))
for n in (1, 5, 10, 100):
print(f"sum(1..{n}) = {somme_n(n)}, formule = {n*(n+1)//2}")
For $\sum k^3$: base $n = 1$ is $1 = 1$. Step: using the identity $(k+1)^3 = \bigl(\tfrac{(k+1)(k+2)}{2}\bigr)^{\!2} - \bigl(\tfrac{k(k+1)}{2}\bigr)^{\!2}$ (verify by expansion), the formula propagates. $\square$
Curious identity: $\sum_{i=1}^{n} i^3 = \bigl(\sum_{i=1}^n i\bigr)^{2}$. The cumulative sum of cubes equals the square of the cumulative sum — a fact apparent in the Nicomachus's "cubes as concentric L-shapes" diagram.
Rosen 8e §5.1; Concrete Mathematics §2.4.
8 / 38
3.3 Examples — $\sum 2^k$ and $\sum k \cdot k!$
$\displaystyle \sum_{k=0}^{n} 2^k = 2^{n+1} - 1.$ (Geometric sum with ratio $2$.)
Trick. Notice that $k \cdot k! = (k+1)! - k!$ — so the sum telescopes:
$\sum_{k=1}^{n} \bigl[(k+1)! - k!\bigr] = (n+1)! - 1!$. This gives the same result without induction.
Concrete Mathematics §2.
9 / 38
4.1 Inequality — $2^n > n^2$ for $n \geq 5$
For every $n \geq 5$, $\;2^n > n^2$.
Base ($n = 5$). $2^5 = 32$, $5^2 = 25$; $32 > 25$. ✓ Step. Assume $2^k > k^2$ with $k \geq 5$. Then
$2^{k+1} = 2 \cdot 2^k > 2 k^2 = k^2 + k^2.$
It suffices to show $k^2 \geq 2k + 1$, i.e. $k^2 - 2k - 1 \geq 0$.
For $k \geq 5$: $k^2 - 2k - 1 \geq 25 - 10 - 1 = 14 > 0$. ✓
Hence $2^{k+1} > k^2 + (2k+1) = (k+1)^2$. By induction, $\forall n \geq 5,\;2^n > n^2$. $\square$
Bound is tight: at $n = 4$, $2^4 = 16 = 4^2$; at $n = 3$, $2^3 = 8 < 9 = 3^2$. Choosing the right $n_0$ matters.
Note $n^3 - n = n(n-1)(n+1)$ — product of three consecutive integers, which always contains a multiple of $2$ and a multiple of $3$. (Or direct induction.) $\square$
Rosen 8e §5.1 Ex. 5; Hardy & Wright §1.
12 / 38
6.1 Set example — $2^n$ subsets
For every $n \geq 0$, every set of $n$ elements has exactly $2^n$ subsets.
Base ($n = 0$). $\mathcal{P}(\varnothing) = \{\varnothing\}$, so $|\mathcal{P}(\varnothing)| = 1 = 2^0$. ✓ Step. Suppose every $k$-set has $2^k$ subsets. Let $|A| = k + 1$; pick $a \in A$ and let $B = A \setminus \{a\}$, $|B| = k$. Each subset of $A$ either contains $a$ or does not — the two classes are disjoint and each has $2^k$ subsets of $B$ (those not containing $a$) plus $2^k$ subsets of the form $S \cup \{a\}$ (containing $a$). Total: $2^k + 2^k = 2^{k+1}$. ✓ $\square$
Counting lines. $n$ points in general position (no three collinear) determine exactly $\binom{n}{2} = n(n-1)/2$ distinct lines.
Base $n = 2$: one line. Step: adding a new point $P$ to a set of $k$ points gives $k$ new lines (one to each existing point); the previous $\binom{k}{2}$ lines remain, so the total becomes $\binom{k}{2} + k = \binom{k+1}{2}$ (Pascal's identity). $\square$
Rosen 8e §5.1 Ex. 10.
13 / 38
7.1 Geometry — triangulating a convex $n$-gon
Every convex polygon with $n \geq 3$ vertices admits a triangulation by non-crossing diagonals, and every such triangulation uses exactly $n - 2$ triangles.
Base $n = 3$: a triangle is already triangulated into $3 - 2 = 1$ triangle. ✓
Step: a convex $(k+1)$-gon has at least one diagonal $d$ (for $k + 1 \geq 4$). Cutting along $d$ splits the polygon into two convex polygons sharing $d$, with $j_1$ and $j_2$ vertices where $j_1 + j_2 = (k+1) + 2$. Both $j_i \leq k$, so by IH each has $(j_i - 2)$ triangles, summing to $(k+1) + 2 - 4 = (k+1) - 2$. ✓ $\square$
Plane regions. $n$ lines in general position divide the plane into $1 + n + \binom{n}{2}$ regions.
Base $n = 0$: $1$ region. Step: a new line, in general position with the existing $k$ lines, crosses each of them in $1$ point, so it is divided into $k + 1$ arcs; each arc cuts an existing region into two. So $R_{k+1} = R_k + (k+1) = 1 + k + \binom{k}{2} + k + 1 = 1 + (k+1) + \binom{k+1}{2}$. ✓ $\square$
Rosen 8e §5.2 Ex. 12; Steiner's theorem (1826).
14 / 38
8. Two classical inductive inequalities
Bernoulli's inequality. For every $x > -1$ and every $n \geq 0$, $(1 + x)^n \geq 1 + nx$.
Base $n = 0$: $(1+x)^0 = 1 = 1 + 0$. ✓ Step:
$(1+x)^{k+1} = (1+x)(1+x)^k \geq (1+x)(1+kx)$ since $1 + x > 0$ and IH.
Expanding: $(1+x)(1+kx) = 1 + (k+1)x + kx^2 \geq 1 + (k+1)x$ since $kx^2 \geq 0$. ✓ $\square$
By induction on $m$: base $m = 0$ ($n = 1$): trivial. Base $m = 1$ ($n = 2$): $(a_1 + a_2)/2 \geq \sqrt{a_1 a_2}$ by $(a_1 - a_2)^2 \geq 0$ (re-arrange).
Step: assume for $n = 2^m$. Pair up $2^{m+1}$ numbers as $(a_1, a_2), \ldots, (a_{2^{m+1}-1}, a_{2^{m+1}})$. By the $n = 2$ case applied $2^m$ times, replace each pair by its arithmetic mean; the overall mean is unchanged, and the product is no larger. Apply IH to the $2^m$ pair-means. $\square$
Cauchy's proof of AM–GM; Bernoulli (1689).
15 / 38
9. Strong induction (course-of-values)
Principle of strong induction. If $P(n_0)$ holds and for every $k \geq n_0$
$\bigl(\forall j,\; n_0 \leq j \leq k \Rightarrow P(j)\bigr) \;\to\; P(k+1),$
then $\forall n \geq n_0,\; P(n)$.
The strong-step inductive hypothesis is generous: instead of just $P(k)$, we may use all $P(j)$ for $j \leq k$. This is needed when the recurrence reaches back more than one step.
(PSI ⇒ PWI.) The weak step is the special case of the strong step where only $j = k$ is used. (PWI ⇒ PSI.) Define $Q(n) :\equiv \bigl(\forall j \leq n,\, P(j)\bigr)$. Apply weak induction to $Q$: base $Q(n_0)$ is $P(n_0)$; step $Q(k) \to Q(k+1)$ is the strong step. By PWI, $\forall n, Q(n)$, so $\forall n, P(n)$. $\square$
Rosen 8e §5.2 Theorem 1; Velleman 3e §6.4.
16 / 38
10. Two key strong-induction examples
Existence of prime factorization. Every integer $n \geq 2$ is a product of primes.
Base $n = 2$: $2$ is prime. Strong step: suppose $P(j)$ for all $2 \leq j \leq k$. For $k + 1$: if it is prime, $P(k+1)$ holds trivially. Otherwise $k + 1 = ab$ with $2 \leq a, b \leq k$; by IH both are products of primes, so $k + 1 = a \cdot b$ is too. $\square$
Frobenius / postage stamps. Every postage $n \geq 12$ cents can be formed with $4$ and $5$ cent stamps.
"All horses have the same colour." A famous "proof": base $n = 1$ is trivial. Step: remove a horse from a group of $k+1$, the remaining $k$ have the same colour (IH); put it back, remove a different one — same colour. So all $k+1$ have the same colour. Where it breaks. At $k+1 = 2$, the two subsets of size $1$ are disjoint, so the "common colour" cannot be transmitted. The step is only valid for $k \geq 2$, but the base only gives $k = 1$.
Missing base case. "Theorem: $n = n + 1$ for all $n \in \mathbb{N}$." "Proof": step works algebraically ($k = k + 1 \Rightarrow k + 1 = k + 2$). But the base $0 = 1$ is false, so the chain never starts.
Bound creep. If the step requires $k \geq 3$, the conclusion is $\forall n \geq 3,\,P(n)$, not $\forall n \geq 0$. Always match the base and the step.
Hidden non-arbitrariness. Each application of the inductive step must work for an arbitrary $k$. A proof that secretly assumes "$k$ is large enough" is no proof at all.
Pólya's classical pedagogical examples; Velleman 3e §6.1.
Python — recursive implementationsdef fact(n): return 1 if n == 0 else n * fact(n - 1)
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)
def lucas(n): return 2 if n == 0 else 1 if n == 1 else lucas(n-1) + lucas(n-2)
print([fact(k) for k in range(7)]) # [1, 1, 2, 6, 24, 120, 720]
print([fib(k) for k in range(10)]) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Rosen 8e §5.3; Concrete Mathematics §1.1.
20 / 38
13. From recurrence to closed form
A linear homogeneous recurrence with constant coefficients of order $k$ is
$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}, \;\; c_k \neq 0, \; c_i \in \mathbb{R}.$
Its characteristic equation is $x^k = c_1 x^{k-1} + \cdots + c_k.$
If the characteristic equation has $k$ distinct real roots $r_1, \ldots, r_k$, then every solution has the form
$a_n = \alpha_1 r_1^n + \cdots + \alpha_k r_k^n,$
where $\alpha_i$ are determined by the $k$ initial values.
Each $r_i^n$ satisfies the recurrence (substitute and divide by $r_i^{n-k}$). Linearity preserves the property. The initial-value Vandermonde system has a unique solution since the $r_i$ are distinct. By induction the formula extends to all $n$. $\square$
Let $\varphi = (1+\sqrt 5)/2$ and $\psi = (1-\sqrt 5)/2$. Then for every $n \geq 0$:
$F_n = \dfrac{\varphi^n - \psi^n}{\sqrt 5}.$
The recurrence $F_n = F_{n-1} + F_{n-2}$ has characteristic equation $x^2 = x + 1$, i.e. $x^2 - x - 1 = 0$, with roots $\varphi, \psi$. So $F_n = \alpha \varphi^n + \beta \psi^n$ for some $\alpha, \beta$. Initial conditions:
$F_0 = 0 \Rightarrow \alpha + \beta = 0;\quad F_1 = 1 \Rightarrow \alpha\varphi + \beta\psi = 1.$
Solve: $\beta = -\alpha$, $\alpha(\varphi - \psi) = 1$, $\alpha\sqrt 5 = 1$, $\alpha = 1/\sqrt 5$, $\beta = -1/\sqrt 5$. $\square$
Since $|\psi| < 1$, $\psi^n \to 0$, so $F_n \sim \varphi^n / \sqrt 5$ — Fibonacci grows geometrically with ratio $\varphi \approx 1.618$. In fact, $F_n$ is the nearest integer to $\varphi^n / \sqrt 5$ for all $n \geq 0$.
Three pegs $A, B, C$; $n$ disks of decreasing size stacked on $A$. Move the entire stack to $C$, one disk at a time, never placing a bigger disk on a smaller one.
Let $H_n$ be the minimum number of moves. Then $H_n = 2^n - 1$.
Recurrence. To move $n$ disks $A \to C$: (i) move the top $n-1$ to $B$ via $C$, using $H_{n-1}$ moves; (ii) move the largest disk $A \to C$, $1$ move; (iii) move the $n-1$ from $B$ to $C$ via $A$, $H_{n-1}$ moves. Total: $H_n = 2 H_{n-1} + 1$, with $H_0 = 0$. Closed form by induction. Base: $H_0 = 0 = 2^0 - 1$. Step: $H_{k+1} = 2 H_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 1$. ✓ $\square$
Python — recursive solverdef hanoi(n, src='A', dst='C', via='B', moves=None):
if moves is None: moves = []
if n == 0: return moves
hanoi(n - 1, src, via, dst, moves)
moves.append(f"{src} → {dst}")
hanoi(n - 1, via, dst, src, moves)
return moves
m = hanoi(3)
print(len(m), m) # 7 ['A → C', 'A → B', 'C → B', 'A → C', 'B → A', 'B → C', 'A → C']
With $64$ disks (Brahma legend), at one move per second the puzzle requires $2^{64} - 1 \approx 5.85 \times 10^{17}$ seconds $\approx 585$ billion years — longer than the age of the universe.
Rosen 8e §8.1 Ex. 2; Lucas (1883).
23 / 38
16. Recursively defined sets
To define a set $S$ recursively:
Specify base elements: $b_1, b_2, \ldots \in S$.
Specify construction rules: "if $x_1, \ldots, x_k \in S$ then $f(x_1, \ldots, x_k) \in S$".
Implicit closure: $S$ contains nothing else — only what is forced by 1 and 2.
The natural numbers. Peano: $0 \in \mathbb{N}$; if $n \in \mathbb{N}$ then $S(n) \in \mathbb{N}$ (successor). The set of binary strings $\Sigma^*$ on $\Sigma = \{0, 1\}$. $\varepsilon \in \Sigma^*$ (empty string); if $w \in \Sigma^*$ then $w0 \in \Sigma^*$ and $w1 \in \Sigma^*$. Palindromes. $\varepsilon$ and every single character $a$ are palindromes; if $w$ is a palindrome and $a$ a character, then $awa$ is a palindrome. Well-formed propositional formulas. Every variable $p_i$ is a wff; if $\varphi, \psi$ are wffs, so are $\neg\varphi$, $(\varphi \wedge \psi)$, $(\varphi \vee \psi)$, $(\varphi \to \psi)$, $(\varphi \leftrightarrow \psi)$ (Lesson 2).
Rosen 8e §5.3; Halmos §13.
24 / 38
17. Recursively defined structures
Lists. A list is either nil (the empty list) or cons(x, L) where $x$ is an element and $L$ is a list. (Same as Lisp's (x . L).)
Binary trees. A binary tree is either a leaf, or a node(L, R) where $L$ and $R$ are binary trees. Internal nodes have two children; leaves have none.
For all strings $w_1, w_2$, $\;(w_1 \cdot w_2)^R = w_2^R \cdot w_1^R$ (reverse swaps the order!).
Induction on $w_1$. Base $w_1 = \varepsilon$: $(w_2)^R = w_2^R = w_2^R \cdot \varepsilon = w_2^R \cdot w_1^R$. ✓
Step $w_1 = a w_1'$: $(aw_1' \cdot w_2)^R = (a(w_1' \cdot w_2))^R = (w_1' \cdot w_2)^R \cdot a \overset{IH}{=} (w_2^R \cdot w_1'^R) \cdot a = w_2^R \cdot (w_1'^R \cdot a) = w_2^R \cdot (aw_1')^R = w_2^R \cdot w_1^R$. ✓ $\square$
Rosen 8e §5.3 Theorem 1; Hopcroft–Ullman §1.
27 / 38
20. Memoization & dynamic programming
The naive Fibonacci recursion fib(n) = fib(n-1) + fib(n-2) recomputes the same subproblems exponentially many times: $\Theta(\varphi^n)$ calls. Storing previously computed values transforms the complexity from $\Theta(\varphi^n)$ to $\Theta(n)$.
Python — three variantsimport functools, time
def fib_naive(n):
return n if n < 2 else fib_naive(n-1) + fib_naive(n-2)
@functools.lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n-1) + fib_memo(n-2)
def fib_iter(n):
a, b = 0, 1
for _ in range(n): a, b = b, a + b
return a
# Benchmark on n = 30
for f in (fib_naive, fib_memo, fib_iter):
t = time.time(); v = f(30); print(f"{f.__name__:10s} = {v} ({time.time()-t:.3f}s)")
General lesson. If a recursive function has overlapping sub-problems and an optimal substructure, memoization (top-down) or dynamic programming (bottom-up) turns exponential into polynomial.
Rosen 8e §8.1; CLRS, Introduction to Algorithms, ch. 15.
28 / 38
21. Tail recursion ↔ iteration
A function is tail-recursive if every recursive call is its last action — there is nothing left to do once the recursive call returns. Such a call can be replaced by a jump, eliminating the stack frame and giving constant-space iteration.
Factorial — naive vs tail-recursive.
Pythondef fact(n): # NOT tail-recursive
if n == 0: return 1
return n * fact(n - 1) # multiplication after the call
def fact_tail(n, acc=1): # tail-recursive
if n == 0: return acc
return fact_tail(n - 1, n * acc) # call is the last action
# Python doesn't optimise tail calls, but the equivalent iteration is:
def fact_iter(n):
acc = 1
for k in range(1, n + 1):
acc *= k
return acc
Functional languages (Scheme, Haskell, OCaml, Scala) guarantee tail-call optimisation. Python explicitly does not. For deeply recursive algorithms on Python use an iterative form or sys.setrecursionlimit cautiously.
Abelson & Sussman, SICP, §1.2.
29 / 38
22. Mutual recursion
Two functions are mutually recursive when each calls the other in its definition. Correctness still follows by induction on a common measure (e.g. the size of the input).
Parity by mutual recursion.
Pythondef even(n):
return True if n == 0 else odd(n - 1)
def odd(n):
return False if n == 0 else even(n - 1)
print([even(k) for k in range(6)]) # [True, False, True, False, True, False]
Hofstadter female–male sequences.
$F(0) = 1, \; M(0) = 0;$ $F(n) = n - M(F(n-1)),\; M(n) = n - F(M(n-1)).$
Pythonfrom functools import lru_cache
@lru_cache(maxsize=None)
def F(n): return 1 if n == 0 else n - M(F(n - 1))
@lru_cache(maxsize=None)
def M(n): return 0 if n == 0 else n - F(M(n - 1))
print([F(k) for k in range(10)]) # [1, 1, 2, 2, 3, 3, 4, 5, 5, 6]
print([M(k) for k in range(10)]) # [0, 0, 1, 2, 2, 3, 4, 4, 5, 6]
Hofstadter, Gödel, Escher, Bach, 1979.
30 / 38
23. Fixed points and fractals
A fixed point of a function $f$ is an element $x$ with $f(x) = x$. Recursive structures often arise as fixed points of set-valued functions, e.g. the smallest $S$ such that $f(S) \subseteq S$.
Cantor set. Start with $C_0 = [0, 1]$. At step $n$, $C_n$ is the union of $2^n$ closed intervals of length $3^{-n}$ each. The Cantor set $C = \bigcap_n C_n$ is the fixed point of the contraction $C \mapsto (C/3) \cup ((C + 2)/3)$.
Sierpinski triangle. Start with an equilateral triangle $T_0$. Replace $T_n$ by three half-size copies, one at each vertex: $T_{n+1} = T_n/2 \cup (T_n/2 + v_1) \cup (T_n/2 + v_2)$ — the union of three contracted copies of itself.
Python — Cantor set as nested intervalsdef cantor(n, a=0.0, b=1.0):
if n == 0:
return [(a, b)]
third = (b - a) / 3
return cantor(n - 1, a, a + third) + cantor(n - 1, b - third, b)
for k in range(4):
print(f"Level {k}: {cantor(k)}")
Fractals are the prototypical example of a "structure equal to a union of smaller copies of itself" — a recursive definition made geometric.
A recursive function's correctness is exactly an induction proof on the recursion measure (typically the input size).
Worked example — proof of correctness of factorial
Pythondef fact(n):
if n == 0:
return 1
return n * fact(n - 1)
For every $n \geq 0$, fact(n) returns $n!$.
Induction on $n$. Base $n = 0$: the code returns $1 = 0!$. Step: assume fact(k) returns $k!$. For input $n = k + 1$, the recursive call fact(k) returns $k!$ by IH; the function returns $(k+1) \cdot k! = (k+1)!$. ✓ $\square$
Worked example — loop invariant for the iterative factorial
Pythondef fact_iter(n):
acc = 1
for k in range(1, n + 1): # invariant: after this iteration, acc == k!
acc *= k
return acc
The loop invariant "after the $k$-th iteration, acc == k!" is proved by induction on $k$ — the iterative version is the loop-form of the recursive proof.
CLRS §2.1; SICP §1.
33 / 38
26. Common recursion pitfalls
Forgetting the base case. The function recurses forever; in Python, you get a RecursionError: maximum recursion depth exceeded.
Wrong base case. A subtle bug: $f(0) = 0$ instead of $f(0) = 1$ in factorial — all values become zero.
Non-decreasing recursion. The recursive call must reduce the argument (or some well-founded measure). Recursing on $f(n)$ with $f(n) = f(n)$ or $f(n+1)$ never terminates.
Exponential blow-up by overlapping sub-problems. Naive Fibonacci is $\Theta(\varphi^n)$. Always check whether memoization saves work.
Stack overflow. Python defaults to a recursion limit of ~1000. Deep recursion needs iteration or an explicit stack.
Rosen 8e §5.4; SICP §1.
34 / 38
27. Strategy — induction vs recursion
Situation
Tool
Prove $\forall n \geq n_0,\,P(n)$ where the step only uses $P(k)$
Weak induction (§2)
Prove $\forall n,\,P(n)$ where the step needs $P(k-1), P(k-2),\ldots$
Strong induction (§9)
Prove $\forall x \in S,\,P(x)$ for an inductively defined set
Structural induction (§18)
Compute a sequence defined by recurrence
Closed form via characteristic equation (§13)
Recursive algorithm with overlapping subproblems
Memoization / DP (§20)
Recursive algorithm with tail call
Tail recursion ↔ iteration (§21)
Recurrence $T(n) = a T(n/b) + n^d$
Master theorem (§24)
Self-similar geometry
Fixed-point / fractal recursion (§23)
35 / 38
28. Python / SymPy toolbox
Python — importsimport functools, sys
from sympy import Function, symbols, rsolve, Sum, simplify
n = symbols('n', integer=True, nonnegative=True)
a = Function('a')
Fixed points and fractals (Cantor set, Sierpinski).
Mergesort + master theorem with the three cases.
Correctness of recursive algorithms = induction on the input size.
37 / 38
Bibliography
K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §§5.1–5.4 (induction, recursive definitions, recursive algorithms), §8.1–8.2 (recurrence relations).
D. J. Velleman. How To Prove It, 3rd ed., Cambridge UP, 2019 — ch. 6 (mathematical induction).
R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics, 2nd ed., Addison-Wesley, 1994 — ch. 1 (recurrent problems), ch. 7 (generating functions).
H. Abelson & G. J. Sussman. Structure and Interpretation of Computer Programs, 2nd ed., MIT Press, 1996 — §§1.2, 2.2 (recursion, structural recursion).
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, 4th ed., MIT Press, 2022 — ch. 4 (recurrences, master theorem), ch. 15 (dynamic programming).
D. E. Knuth. The Art of Computer Programming, vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997 — §§2.3 (trees), §1.2 (induction).
D. R. Hofstadter. Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979 — mutual recursion, fixed points.
É. Lucas. Récréations mathématiques, 1883 — Tower of Hanoi.
J. Binet (1843). Mémoire sur l'intégration des équations linéaires aux différences finies — Binet's formula.
B. Mandelbrot. The Fractal Geometry of Nature, W. H. Freeman, 1982.