Iteration, not induction
Abstract:The main purpose of this note is to present and justify proof via iteration as an intuitive, creative and empowering method that is often available and preferable as an alternative to proofs via either mathematical induction or the well-ordering principle. The method of iteration depends only on the fact that any strictly decreasing sequence of positive integers must terminate in finitely many steps. Four examples are presented using the method of iteration. These examples concern the factorization of integers or polynomials into products of primes, the calculation of quotients and remainders via the division algorithm (and, hence, of greatest common divisors via the Euclidean Algorithm) and the rank of matrices via elementary row and column operations. We also justify the method of proof by iteration by showing that its validity is a logical consequence of the method of mathematical induction. Various parts of this material would be suitable for courses on Precalculus, Discrete Mathematics, Abstract Algebra or Matrix Theory/Linear Algebra.
Document Type: Research Article
Affiliations: Department of Mathematics, University of Tennessee, Knoxville, TN 37996-1300, USA
Publication date: January 1, 2009