next up previous contents
Next: Strong Principle of Mathematical Up: Induction and Counting Previous: The Pigeonhole Principle   Contents

Induction

Recall the well-ordering axiom for $ \mathbb{N}_0$: that every non-empty subset of $ \mathbb{N}_0$ has a least element. This may be stated equivalently as: ``there is no infinite descending chain in $ \mathbb{N}_0$''. We also recall the (weak) principle of induction from before.

Proposition 8.2.1 (Principle of Induction)   Let $ P(n)$ be a statement about $ n$ for each $ n \in \mathbb{N}$. Suppose $ P(k_0)$ is true for some $ k_0 \in \mathbb{N}$ and $ P(k)$ true implies that $ P(k+1)$ is true for each $ k \in \mathbb{N}$. Then $ P(n)$ is true for all $ n \in \mathbb{N}_0$ such that $ n \ge k_0$.

The favourite example is the Tower of Hanoi. We have $ n$ rings of increasing radius and 3 vertical rods ($ A$, $ B$ and $ C$) on which the rings fit. The rings are initially stacked in order of size on rod $ A$. The challenge is to move the rings from $ A$ to $ B$ so that a larger ring is never placed on top of a smaller one. We write the number of moves required to move $ n$ rings as $ T_n$ and claim that $ T_n = 2^n - 1$ for $ n \in \mathbb{N}_0$. We note that $ T_0 = 0 = 2^0 - 1$, so the result is true for $ n=0$. We take $ k > 0$ and suppose we have $ k$ rings. Now the only way to move the largest ring is to move the other $ k - 1$ rings onto $ C$ (in $ T_{k-1}$ moves). We then put the largest ring on rod $ B$ (in $ 1$ move) and move the $ k - 1$ smaller rings on top of it (in $ T_{k-1}$ moves again). Assume that $ T_{k-1} = 2^{k-1} - 1$. Then $ T_k = 2 T_{k-1} + 1
= 2^k - 1$. Hence the result is proven by the principle of induction.
next up previous contents
Next: Strong Principle of Mathematical Up: Induction and Counting Previous: The Pigeonhole Principle   Contents
root 2002-06-10