In mathematics, induction is a technique for proving certain types of mathematical statements. The induction principle can be illustrated by arranging a series of dominoes in a line. Suppose two facts are known about this line of dominoes.

1. The first domino is knocked over.
2. If one domino is knocked over, then the next domino is always knocked over.

What can be concluded from these statements? If the first domino is knocked over, then the second domino is knocked over, which knocks over the third, fourth, fifth, and so on, until eventually all of the dominoes fall.

Induction is a simple but powerful idea when applied to mathematical statements about positive integers. For example, consider the following statement: n² ≥ n for all positive integers, n. To prove that this statement is true using induction, it is necessary to prove two parts: first, that the statement is true for n...