Induction & Recursive Definitions

10 slides for a 1h30 lecture

Discrete Mathematics — Session 3

Pr. El Hadiq Zouhair

Part I · 60 minutes

Mathematical Induction

Well-ordering · Weak induction · Examples · Strong induction

§1 · ~7 min

Well-ordering principle (WOP)

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 (slide 3) and to strong induction (slide 8).

$S = \{n \in \mathbb{N} : n^2 \geq 20\}$ is non-empty (contains $5$). By WOP, $\min S$ exists. Computing: $4^2 = 16 < 20$ but $5^2 = 25 \geq 20$, so $\min S = 5$.
WOP fails on $\mathbb{Z}$: $\mathbb{Z}$ itself has no minimum. It also fails on $\mathbb{Q}_{\geq 0}$: the interval $(0, 1) \cap \mathbb{Q}$ has no minimum.
WOP is the defining property of $\mathbb{N}$ — it expresses the absence of an infinite descending chain.
2 / 11
§2 · ~10 min

Principle of weak induction

Let $P(n)$ be a predicate on $\mathbb{N}$. If
  1. Base case: $P(0)$ holds, and
  2. Inductive step: for every $k \in \mathbb{N}$, $\;P(k) \to P(k+1)$,
then $\forall n \in \mathbb{N},\, P(n)$.
WOP $\;\Leftrightarrow\;$ PWI  (both directions proved by minimal-counter-example arguments).
(WOP ⇒ PWI). Let $S = \{n : \neg P(n)\}$. If $S \neq \varnothing$, by WOP it has a minimum $m$; since $P(0)$, $m \geq 1$ and $m - 1 \in \mathbb{N}$. By minimality, $P(m-1)$; by step, $P(m)$ — contradiction. $\square$
(PWI ⇒ WOP). Let $S$ non-empty without minimum. Let $Q(n) :\equiv \forall j \leq n,\, j \notin S$. Base $Q(0)$: $0 \notin S$ else $0 = \min S$. Step: similar. By PWI, $\forall n,\,Q(n)$, so $S = \varnothing$. $\square$
3 / 11
§3 · ~5 min

The induction template

To prove $\forall n \geq n_0,\, P(n)$:

  1. Base case. Verify $P(n_0)$ explicitly.
  2. Inductive hypothesis (IH). Fix arbitrary $k \geq n_0$, assume $P(k)$.
  3. 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 the conditional statement "if $P(n_0)$, then $\forall n,\,P(n)$" — useless when $P(n_0)$ is false. (See the "all horses" counter-example.)
The next slides apply this template to three different categories of examples: sum formulas, divisibility, set counting.
4 / 11
§4 · ~12 min

Sum formulas — three examples

For every $n \geq 1$, $\displaystyle \sum_{i=1}^{n} i = \frac{n(n+1)}{2},\;\;\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6},\;\;\sum_{i=1}^{n} i^3 = \Bigl(\frac{n(n+1)}{2}\Bigr)^{\!2}.$
For $\sum i$. Base $n = 1$: $1 = 1 \cdot 2/2$. ✓
Step: $\sum_{i=1}^{k+1} i = \tfrac{k(k+1)}{2} + (k+1) = \tfrac{(k+1)(k+2)}{2}.$ ✓ $\square$
For $\sum i^2$. Base $n = 1$: $1 = 1\cdot 2\cdot 3 / 6$. Step: $\sum_{i=1}^{k+1} i^2 = \tfrac{k(k+1)(2k+1)}{6} + (k+1)^2 = \tfrac{(k+1)(k+2)(2k+3)}{6}.$ ✓ $\square$
Curious identity: $\sum_{i=1}^{n} i^3 = \bigl(\sum_{i=1}^n i\bigr)^{2}$ — cumulative sum of cubes = square of cumulative sum. Visible in Nicomachus's "concentric L-shapes" picture (1st century AD).
5 / 11
§5 · ~8 min

Divisibility — $3 \mid (n^3 + 2n)$

For every $n \geq 0$, $\;3 \mid (n^3 + 2n)$.
Base ($n = 0$). $0^3 + 2 \cdot 0 = 0$ and $3 \mid 0$. ✓
Step. Assume $k^3 + 2k = 3m$ for some $m \in \mathbb{Z}$. Then $$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3(k^2 + k + 1) = 3(m + k^2 + k + 1),$$ divisible by $3$. ✓ $\square$
Two more by the same recipe:
$\;7 \mid (8^n - 1)$  (use $8^{k+1} - 1 = 8(8^k - 1) + 7$).
$\;6 \mid (n^3 - n)$  (note $n^3 - n = n(n-1)(n+1)$ is a product of three consecutive integers).
6 / 11
§6 · ~8 min

Counting — a set of $n$ elements has $2^n$ subsets

For every $n \geq 0$, if $|A| = n$ then $|\mathcal{P}(A)| = 2^n$.
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$. Every subset of $A$ either:
  • excludes $a$: $S \subseteq B$ — $2^k$ choices (by IH);
  • contains $a$: $S \setminus \{a\} \subseteq B$ — $2^k$ choices.
These classes are disjoint and exhaustive, giving $|\mathcal{P}(A)| = 2^k + 2^k = 2^{k+1}$. ✓ $\square$
Pascal-style restatement: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ — partition the subsets by size $k$. This is the row-sum identity of Pascal's triangle.
7 / 11
§7 · ~6 min

Strong induction (PSI)

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 IH is generous: instead of just $P(k)$, we may use every previously proved $P(j)$. Needed when the recurrence reaches back more than one step.

PSI $\;\Leftrightarrow\;$ PWI.
(PSI ⇒ PWI). The weak step is the special case of the strong step using only $j = k$.
(PWI ⇒ PSI). Define $Q(n) :\equiv \forall j \leq n,\, P(j)$. Then $Q(n_0) = P(n_0)$ (base) and $Q(k) \to Q(k+1)$ via the strong step. PWI on $Q$. $\square$
8 / 11
§7 bis · ~6 min

Three strong-induction theorems

1. Prime factorization. Every integer $n \geq 2$ is a product of primes.
Base $n = 2$: prime. Step: if $k+1$ is prime, done. Else $k + 1 = ab$, $2 \leq a, b \leq k$; by IH both are products of primes. $\square$
2. Postage stamps (Frobenius). Every $n \geq 12$ cents is $4a + 5b$ with $a, b \in \mathbb{N}$.
Bases $n = 12, 13, 14, 15$ — explicit. Step: for $k + 1 \geq 16$, $k - 3 \geq 12$, by IH $k - 3 = 4a + 5b$; so $k + 1 = 4(a+1) + 5b$. $\square$
3. Fibonacci bound. $F_n \leq \varphi^{n-1}$ where $\varphi = (1+\sqrt 5)/2$.
Bases $F_1, F_2$ explicit. Step: $F_{k+1} = F_k + F_{k-1} \leq \varphi^{k-1} + \varphi^{k-2} = \varphi^{k-2}(\varphi + 1) = \varphi^{k}$  (using $\varphi^2 = \varphi + 1$). $\square$
9 / 11
Part II · 30 minutes

Recursive Definitions

Base + recursive case · Factorial · Fibonacci · Lucas · Ackermann

§8 · ~15 min

Recursive functions — definition & examples

A recursive definition of $f : \mathbb{N} \to X$ specifies:
  1. Base case(s): value(s) for the smallest argument(s).
  2. Recursive case: $f(n)$ from one or more earlier values $f(n-1), f(n-2), \ldots$
Well-definedness is justified by induction on $n$ — proving correctness is doing induction.

Factorial

$f(0) = 1$, $\;f(n) = n \cdot f(n-1)$  ⇒  $f(n) = n!$

Python def fact(n): if n == 0: return 1 return n * fact(n - 1)

Fibonacci

$F_0 = 0, F_1 = 1, \;F_n = F_{n-1} + F_{n-2}$

Python def fib(n): if n < 2: return n return fib(n-1) + fib(n-2)

Lucas: $L_0 = 2, L_1 = 1, L_n = L_{n-1} + L_{n-2}$ — sequence $2, 1, 3, 4, 7, 11, 18, 29, \ldots$    Ackermann: $A(0,n) = n+1;\; A(m,0) = A(m-1,1);\; A(m,n) = A(m-1, A(m,n-1))$ — grows faster than any primitive recursive function.

10 / 11
00:00