Introduction to Proofs and Proof Strategies

Mathematical induction is a proof technique often used to prove that a statement P(n) that depends on a variable n is valid for every natural number. Equivalently, one may think of P(n) as representing an infinite sequence of statements, one for every natural number n: P(1), P(2), P(3), …. When dealing with infinitely many statements, there is no way we can prove them all by proving each statement individually. Induction is a tool we can often use to bypass this difficulty. Mathematical induction is an extremely powerful proof technique. It is not restricted to specific areas of mathematics and thus can be used to prove statements in algebra, geometry, number theory, analysis, etc. Moreover, induction is a useful tool at all levels of mathematics. It is used to prove elementary statements about numbers as well as advanced statements in, say, topology and modern algebra.