Principles of Induction

Simple Induction

Principle

To prove $\forall n \in \mathbb{N}. P(n)$:

1. Base case: Prove $P(0)$
2. Inductive step: Prove that for arbitrary $n \in \mathbb{N}$, $P(n) \Rightarrow P(n+1)$

If both hold, then by the principle of mathematical induction, $P(n)$ is true for all $n \in \mathbb{N}$.

Why It Works

Induction is justified by the well-ordering of $\mathbb{N}$.

Suppose $P(0)$ holds and $P(n) \Rightarrow P(n+1)$ for all $n$, but some $k$ fails $P(k)$.

Let $S = \{n \in \mathbb{N} : \neg P(n)\}$. By assumption, $S \neq \emptyset$.

By well-ordering, $S$ has a least element $m$.

Since $P(0)$ holds, $m > 0$.

Thus $m - 1 \in \mathbb{N}$ and $m - 1 \notin S$, so $P(m-1)$ holds.

By the inductive step, $P(m)$ holds. Contradiction.

Example: Sum Formula

Statement: $\displaystyle\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$ for all $n \in \mathbb{N}$.

Base case ($n = 0$): Empty sum = 0. And $\frac{0 \cdot (-1)}{2} = 0$.

Inductive step: Assume $\displaystyle\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$.

Then: $\sum_{i=0}^{n} i = \frac{n(n-1)}{2} + n = \frac{n(n-1) + 2n}{2} = \frac{n(n+1)}{2}$

This is $\frac{(n+1)(n)}{2}$, establishing $P(n+1)$.

Induction from a Basis

Principle

To prove $\forall n \geq k. P(n)$ for some fixed $k$:

1. Base case: Prove $P(k)$
2. Inductive step: Prove $P(n) \Rightarrow P(n+1)$ for arbitrary $n \geq k$

When to Use

When the property $P(n)$ is only meaningful or true for $n \geq k$.

Example

Statement: $2^n > n^2$ for all $n \geq 5$.

Base case ($n = 5$): $2^5 = 32 > 25 = 5^2$.

Inductive step: Assume $2^n > n^2$ for $n \geq 5$.

Then $2^{n+1} = 2 \cdot 2^n > 2n^2$.

For $n \geq 5$: $2n^2 - (n+1)^2 = 2n^2 - n^2 - 2n - 1 = n^2 - 2n - 1 \geq 25 - 10 - 1 = 14 > 0$.

So $2n^2 > (n+1)^2$, giving $2^{n+1} > (n+1)^2$.

Strong Induction

Principle

To prove $\forall n \in \mathbb{N}. P(n)$:

1. Inductive step: Prove that for arbitrary $n$: $\left(\forall m < n. P(m)\right) \Rightarrow P(n)$

No explicit base case needed: when $n = 0$, the hypothesis "$\forall m < 0. P(m)$" is vacuously true.

When to Use

When proving $P(n)$ requires multiple previous cases, not just $P(n-1)$.

Example: Fibonacci

The Fibonacci sequence: $F_0 = 0$, $F_1 = 1$, $F_{n+1} = F_n + F_{n-1}$.

Statement: $F_n < 2^n$ for all $n \in \mathbb{N}$.

Strong induction:

Assume $\forall m < n. F_m < 2^m$.

If $n \leq 1$: $F_0 = 0 < 1 = 2^0$ and $F_1 = 1 < 2 = 2^1$.

For $n \geq 2$: $F_n = F_{n-1} + F_{n-2} < 2^{n-1} + 2^{n-2} = \frac{3}{4} \cdot 2^n < 2^n$

Common Pitfalls

Wrong Inductive Hypothesis

Trap: Assuming $P(n-1)$ when $P(n-2)$ is also needed.

This happens in Fibonacci-style recurrences. Use strong induction instead.

Forgetting the Base Case

Trap: Proving $P(n) \Rightarrow P(n+1)$ without checking $P$ holds somewhere.

Assuming What You Prove

Trap: The inductive step must assume $P(n)$ and derive $P(n+1)$.

Do not assume $P(n+1)$.

Inductive Step Fails for Small $n$

Trap: Check the inductive step works for the transition from base case.

Example of Failure

False claim: All horses are the same colour.

“Proof” by induction on herd size $n$:

• Base ($n = 1$): Trivial.
• Inductive step: If all horses in a herd of $n$ have the same colour, then in a herd of $n+1$:
  • First $n$ horses have same colour (by IH)
  • Last $n$ horses have same colour (by IH)
  • Therefore all $n+1$ horses have same colour.

Error: When $n = 1$, there is no overlap between “first $n$” and “last $n$” (both are single horses). The argument fails.

---

Summary

• Simple induction: prove $P(0)$, then $P(n) \Rightarrow P(n+1)$
• Induction from basis: $P(k)$, then $P(n) \Rightarrow P(n+1)$ for $n \geq k$
• Strong induction: $(\forall m < n. P(m)) \Rightarrow P(n)$
• Strong induction needed for recurrences depending on multiple predecessors