What is principle of mathematical induction? Explain with the help of an example.
Principle of Mathematical Induction (PMI): Let p(n) be a predicate involving a natural number n. Suppose the following two conditions hold:
- p(m) is true for some m ∈ N;
- If p(k) is true, then p(k+1) is true, where k(≥m) is any natural number. Then p(n) is true for every n ≥ m.
Looking at the two conditions in the principle, can you make out why it works? (As a hint, put m = 1 in our example above.)