Mathematical induction

The mathematical method examines infinitely many cases to prove a general statement, but it does so by a finite chain of deductive reasoning involving the variable

[4] In 370 BC, Plato's Parmenides may have contained traces of an early example of an implicit inductive proof,[5] however, the earliest implicit proof by mathematical induction was written by al-Karaji around 1000 AD, who applied it to arithmetic sequences to prove the binomial theorem and properties of Pascal's triangle.

Whilst the original work was lost, it was later referenced by Al-Samawal al-Maghribi in his treatise al-Bahir fi'l-jabr (The Brilliant in Algebra) in around 1150 AD.

Katz says in his history of mathematics Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences.

Thus al-Karaji used such an argument to prove the result on the sums of integral cubes already known to Aryabhata [...] Al-Karaji did not, however, state a general result for arbitrary n. He stated his theorem for the particular integer 10 [...] His proof, nevertheless, was clearly designed to be extendable to any other integer.

Of course, this second component is not explicit since, in some sense, al-Karaji's argument is in reverse; this is, he starts from n = 10 and goes down to 1 rather than proceeding upward.

Nevertheless, his argument in al-Fakhri is the earliest extant proof of the sum formula for integral cubes.

[9]In India, early implicit proofs by mathematical induction appear in Bhaskara's "cyclic method".

Another similar case (contrary to what Vacca has written, as Freudenthal carefully showed)[11] 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.

[12][13] 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 modern formal treatment of the principle came only in the 19th century, with George Boole,[14] Augustus De Morgan, Charles Sanders Peirce,[15][16] Giuseppe Peano, and Richard Dedekind.

We give a proof by induction on n. Base case: Show that the statement holds for the smallest natural number n = 0.

Assume the induction hypothesis that for a particular k, the single case n = k holds, meaning P(k) is true:

In practice, proofs by induction are often structured differently, depending on the exact nature of the property to be proven.

Induction can be used to prove that any whole amount of dollars greater than or equal to 12 can be formed by a combination of such coins.

The proof that S(k) is true for all k ≥ 12 can then be achieved by induction on k as follows: Base case: Showing that S(k) holds for k = 12 is simple: take three 4-dollar coins.

, the above proof cannot be modified to replace the minimum amount of 12 dollar to any lower value m. For m = 11, the base case is actually false; for m = 10, the second case in the induction step (replacing three 5- by four 4-dollar coins) will not work; let alone for even lower m. It is sometimes desirable to prove a statement involving two natural numbers, n and m, by iterating the induction process.

The method of infinite descent is a variation of mathematical induction which was used by Pierre de Fermat.

Using mathematical induction on the statement P(n) defined as "Q(m) is false for all natural numbers m less than or equal to n", it follows that P(n) holds for all n, which means that Q(n) is false for every natural number n. If one wishes to prove that a property P holds for all natural numbers less than or equal to n, proving P satisfies the following conditions suffices:[18] The most common form of proof by mathematical induction requires proving in the induction step that

Prefix induction can simulate predecessor induction, but only at the cost of making the statement more syntactically complex (adding a bounded universal quantifier), so the interesting results relating prefix induction to polynomial-time computation depend on excluding unbounded quantifiers entirely, and limiting the alternation of bounded universal and existential quantifiers allowed in the statement.

However, there will be slight differences in the structure and the assumptions of the proof, starting with the extended base case.

[22][23] The induction step must be proved for all values of n. To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by mathematical induction that all horses are of the same color:[24] Base case: in a set of only one horse, there is only one color.

The axiom of structural induction for the natural numbers was first formulated by Peano, who used it to specify the natural numbers together with the following four other axioms: In first-order ZFC set theory, quantification over predicates is not allowed, but one can still express induction by quantification over sets:

Applied to a well-founded set, transfinite induction can be formulated as a single step.

To prove that a statement P(n) holds for each ordinal number: This form of induction, when applied to a set of ordinal numbers (which form a well-ordered and hence well-founded class), is called transfinite induction.

Suppose the following: It can then be proved that induction, given the above-listed axioms, implies the well-ordering principle.

Therefore, by the complete induction principle, P(n) holds for all natural numbers n; so S is empty, a contradiction.

Peano's axioms with the induction principle uniquely model the natural numbers.

[25] It is mistakenly printed in several books[25] and sources that the well-ordering principle is equivalent to the induction axiom.