    Next: Recursive Definitions Up: Induction and Counting Previous: Induction   Contents

# Strong Principle of Mathematical Induction

Proposition 8.3.1 (Strong Principle of Induction)   If is a statement about for each , is true for some and the truth of is implied by the truth of , , , then is true for all such that .

The proof is more or less as before.

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

Solution
Let be the statement mutations are required to produce end products''. is clear. Consider a tree with end products. The first mutation (the root) produces 2 trees, say with and end products with . Then so . If both and are true then there are mutations on the left and on the right. So in total we have mutations in our tree and is true is and are true. Hence is true for all .    Next: Recursive Definitions Up: Induction and Counting Previous: Induction   Contents
root 2002-06-10