next up previous contents
Next: Recursive Definitions Up: Induction and Counting Previous: Induction   Contents

Strong Principle of Mathematical Induction

Proposition 8.3.1 (Strong Principle of Induction)   If $ P(n)$ is a statement about $ n$ for each $ n \in \mathbb{N}$, $ P(k_0)$ is true for some $ k_0 \in \mathbb{N}$ and the truth of $ P(k)$ is implied by the truth of $ P(k_0)$, $ P(k_0+1)$, $ \dots$, $ P(k-1)$ then $ P(n)$ is true for all $ n \in \mathbb{N}$ such that $ n \ge k_0$.

The proof is more or less as before.

Example 8.3.2 (Evolutionary Trees)   Suppose that every organism can mutate and produce $ 2$ new versions. Then $ n$ mutations are required to produce $ n+1$ end products.

Solution
Let $ P(n)$ be the statement ``$ n$ mutations are required to produce $ n+1$ end products''. $ P_0$ is clear. Consider a tree with $ k + 1$ end products. The first mutation (the root) produces 2 trees, say with $ k_1 + 1$ and $ k_2 + 1$ end products with $ k_1, k_2 < k$. Then $ k + 1 = k_1 + 1 + k_2 + 1$ so $ k = k_1 + k_2 + 1$. If both $ P(k_1)$ and $ P(k_2)$ are true then there are $ k_1$ mutations on the left and $ k_2$ on the right. So in total we have $ k_1 + k_2 + 1$ mutations in our tree and $ P(k)$ is true is $ P(k_1)$ and $ P(k_2)$ are true. Hence $ P(n)$ is true for all $ n \in \mathbb{N}_0$.

next up previous contents
Next: Recursive Definitions Up: Induction and Counting Previous: Induction   Contents
root 2002-06-10