Mathematical Induction Provides a Tool for Proving Large Problems by Proceeding through the Solution of Smaller Increments

views updated

Mathematical Induction Provides a Tool for Proving Large Problems by Proceeding through the Solution of Smaller Increments

Overview

The development of mathematical induction was one of the great forward steps in mathematics. An elegant principle that played a large part in the continuing evolution of mathematical logic, and affected the development of other mathematical disciplines, including algebra and analytic geometry, mathematical induction is related to the nonmathematical process called inductive reasoning. As opposed to deductive reasoning, by which a large general truth is taken as the starting point from which smaller, more specific truths are derived, induction provided a tool for moving from the specific to the general, from small individual truths to larger overall ones. By the process of induction, the truth of an entire mathematical proposition is proved one step at a time, with each step being used as a building block toward proving the next step, with the ultimate goal of proving the entire proposition. The nature of mathematical induction is such that it offers effective proofs of certain propositions while at the same time eliminating the need to prove every example of a proposition. While many feel that induction was perceived as long ago as ancient Greece, the method was not clearly expressed until 1575, when Sicilian mathematician Francisco Maurolico (1494-1575) used the method to prove a theorem. Maurolico's approach did not have a name: that waited for English mathematician John Wallis (1616-1703), who described the method as induction in his 1655 book Arithmetica Infinitorum (Infinitesimal Arithmetic). Nearly a decade later, with the posthumous publication of Blaise Pascal's (1623-1662) Traite du Triangle Arithmetique (Treatise On the Arithmetic of Triangles), mathematical induction became widely known as an effective and indispensable mathematical tool.

Background

Deductive reasoning was one of the great advances in human knowledge. By the process of deduction a large truth serves as a starting point from which smaller and more specific truths are logically derived. But deductive reasoning was not applicable to all areas of knowledge. In mathematics, particularly, large truths—or proofs—were often elusive, approachable only fitfully, in increments.

But as mathematics became a more and more important and precise tool, much thought and investigation was applied to the task of proving large theorems. That thought, research, and experimentation led to the development of mathematical induction, also known as the induction principle.

Some scholars see evidence of mathematical induction in the works of Greek mathematicians including Pappas (c. 260-?), whose works collected most of the Greek mathematical work that has survived to the present. Because Pappas was primarily a collector of mathematical ideas, rather than an originator of them, it is likely that his work with induction was derived from earlier thinkers.

Other evidence of early inductive reasoning can be found in works of both Islamic and Talmudic scholars, particularly Levi ben Gerson (1288?-1344?). In referring to his approach to solving complex problems, Levi ben Gerson wrote that he pursued a mathematical process of "rising step-by-step without end." That step-by-step approach is the very essence of induction, although that essence would not be formalized for another 250 years.

Part of the problem faced by Levi ben Gerson was his reliance on words rather than symbols when presenting his insights into algebra. By the 1500s mathematics was in a state a rapid evolution, with new insights and methodologies being developed at a steady pace, and the science itself becoming a more purely symbolic activity.

Italian (Sicilian) Francisco Maurolico, a Benedictine monk and also the head of the Sicilian mint, applied himself through most of the 1500s to collecting and translating the world's mathematical knowledge. He also wrote original treatises on mathematics, including the Arithmeticorum Libri Duo (Two Mathematics Books), in which he used the inductive principle to prove a theorem.

Put simply, mathematical induction reduces a mathematical proposition or theorem to simple statements that can be proved, each statement serving as a step toward the solution of the larger proposition. When searching, for example, for properties of whole numbers, mathematical induction solves for the simplest example of a whole number's property, which is of course the number 1. The next step is to select a random whole number, represented as k. If you can prove that the statement that was true for 1 is also true for the number k, you have also proved that is true for the number k+1.

By proving those two statements, you have induced that the statement is true for all whole numbers, or n.

Maurolico's principle attracted some attention but remained nameless until the work of English mathematician John Wallis. Considered by many to be the most important English mathematician before Isaac Newton (1642-1727), Wallis made many large contributions to both mathematics and science, including helping to found England's Royal Society (the most prestigious of all scientific bodies) and formulating for the first time the law of conservation of momentum. He also engaged in many bitter scientific and mathematical quarrels.

It is perhaps as a writer on mathematics that Wallis made the largest of his contributions. He was obsessed with the history of mathematics and devoted to preserving that history for the modern world. Among his many books was Arithmetica Infinitorum, published in 1656. In that book, among many examples of mathematical properties, including infinite series and anticipations of integral calculus, Wallis recapitulated mathematical induction, referring to it as per modum inductonis (by the method of induction) and gave the procedure the name by which it is still known.

For mathematical induction to become well known, however, it would require almost another decade and the 1665 publication another book, which, ironically had been written before Wallis's volume.

This was Blaise Pascal's Traite du Triangle Arithmetique (Treatise on the Triangle), one of the key mathematical treatises of its time. Pascal was the son of a mathematician, although his father initially opposed the child's early interest in mathematics. Pascal's genius quickly became obvious and his father relented; the boy immersed himself in mathematics. Pascal's interest went beyond the theoretical: by the time was 19 he had invented an early version of the mechanical calculator. Only the excessive cost of manufacturing his calculator kept the machines from becoming successful.

While Pascal's brilliance led him into many fields of research and reflection, including religious philosophy, it was in pure mathematics that he made his largest contributions, laying the groundwork (along with Pierre de Fermat [1601-1675]) for the modern science of probability, as well as insights into calculus and geometry.

His "Treatise on the Triangle" focused on the properties of a triangle composed of numbers, but also on other mathematical ideas and concepts. Among them was his approach to proving propositions for which there are infinitely many cases. He informed his readers that faced with such a proposition they should initially prove that the proposition is true for the first case. Following that, they should prove the proposition for a given (or random) case. With those two proofs, the proposition is solved for the next case, and for an infinite number of other cases.

Using induction, Pascal provided a method for solving the binomial theorem, which was essential for solving problems in which two quantities vary independently. The success of Pascal's book, along with the name Wallis gave to the process, insured that Maurolico's induction principle became widely known, and continues to serve mathematics to this day.

Impact

Mathematical induction, the ability to prove for all cases of a numerical property, was a major step forward in the transition of mathematics from the purely practical—counting—to the more theoretical. Rather than being restricted to concrete items, mathematics was able to deal with variables, with unknowns, with relationships among variables and unknowns, with infinite series of properties. These abilities vastly extended the reach of mathematics, both in relation to calculations and equations related to the real world, and to more purely theoretical pursuits. The ability to solve for all cases of a proposition yielded a mathematical tool that in turn helped mathematicians determine many of the properties of numbers in sequence. The induction principle also offered an important, and still-used, tool for both the devising and also the solving of complex codes.

KEITH FERRELL