Mathematical induction

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a property P(n) holds for every natural number n, i.e. for n = 0, 1, 2, 3, and so on. Metaphors can be informally used to understand the concept of mathematical induction, such as the metaphor of falling dominoes or climbing a ladder: The method of induction requires two cases to be proved. The first case, called the base case (or, sometimes, the basis), proves that the property holds for the number 0. The second case, called the induction step, proves that, if the property holds for one natural number n, then it holds for the next natural number n + 1. These two steps establish the property P(n) for every natural number n = 0, 1, 2, 3, ... The base step need not begin with zero. Often it begins with the number one, and it can begin with any natural number, establishing the truth of the property for all natural numbers greater than or equal to the starting number. The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction, in some form, is the foundation of all correctness proofs for computer programs. Although its name may suggest otherwise, mathematical induction should not be misconstrued as a form of inductive reasoning as used in philosophy (also see Problem of induction). Mathematical induction is an inference rule used in formal proofs. Proofs by mathematical induction are, in fact, examples of deductive reasoning. In 370 BC, Plato's Parmenides may have contained an early example of an implicit inductive proof. The earliest implicit traces of mathematical induction may be found in Euclid's proof that the number of primes is infinite and in Bhaskara's 'cyclic method'. An opposite iterated technique, counting down rather than up, is found in the Sorites paradox, where it was argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap. An implicit proof by mathematical induction for arithmetic sequences was introduced in the al-Fakhri written by al-Karaji around 1000 AD, who used it to prove the binomial theorem and properties of Pascal's triangle. None of these ancient mathematicians, however, explicitly stated the induction hypothesis. Another similar case (contrary to what Vacca has written, as Freudenthal carefully showed) was that of Francesco Maurolico in his Arithmeticorum libri duo (1575), who used the technique to prove that the sum of the first n odd integers is n2. The first explicit formulation of the principle of induction was given by Pascal in his Traité du triangle arithmétique (1665). Another Frenchman, Fermat, made ample use of a related principle, indirect proof by infinite descent. The induction hypothesis was also employed by the Swiss Jakob Bernoulli, and from then on it became more or less well known. The modern rigorous and systematic treatment of the principle came only in the 19th century, with George Boole, Augustus de Morgan, Charles Sanders Peirce, Giuseppe Peano, and Richard Dedekind. The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps: