Mathematical induction is a method of proof by which a statement about a variable can be demonstrated to be true for all integer values of that variable greater than or equal to a specified integer (usually 0 or 1).
An example of such a statement is:
- The number of possible pairings of n distinct objects is (for any positive integer n).
A proof by induction proceeds as follows:
- The statement is proved for the first possible value of n (usually 0 or 1, but other "starting values" are possible).
- The statement is assumed to be true for some fixed, but unspecified, value n and this assumption is used to prove that the statement is true for (the latter statement is simply the original statement with n replaced by ).
- The statement is then concluded to be true for all relevant values of n (all nonnegative values or all positive values, depending).
That the conclusion in step 3 above follows from steps 1 and 2 is the principle of mathematical induction.
More formally, given a proposition about the integer-valued variable n that is to be proved for , the following must be proved.
The conclusion is then
- for .
Early implicit traces of mathematical induction can 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 one 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.
The earliest 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, Pascal's triangle, and the sum formula for integral cubes. The sum formula for integral cubes is the (true) proposition that every integer can be expressed by the sum of cubed natural numbers. It is a particular case of what is referred to as Waring's Problem. His proof was the first to make use of the two basic components of an inductive proof. First, he notes the truth of the statement for n = 1. That is, 1 is the sum of a single cube because 1 = 13. Secondly, he derives the truth for n = k from that of n = k − 1. For example, when n = 2, it is true that 2 = 13 + 13. When n = 3, it is true that 3 = 13 + 13 + 13. The truth of the statement can be extrapolated in this way without limit. Of course, as n grows larger, some of the sums of 13 can be rewritten as the cubes of other natural numbers: for example when n=8 then 8 = 23 = [13 × 8]. 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."
Shortly afterwards, Ibn al-Haytham (Alhazen) used the inductive method to prove the sum of fourth powers, and by extension, the sum of any integral powers. He only stated it for particular integers, but his proof for those integers was by induction and generalizable. Ibn Yahyā al-Maghribī al-Samaw'al came closest to a modern proof by mathematical induction in pre-modern times, which he used to extend the proof of the binomial theorem and Pascal's triangle previously given by al-Karaji. Al-Samaw'al's inductive argument was only a short step from the full inductive proof of the general binomial theorem. Earliest rigorous use of induction and illustrations of proofs using it was made by Gersonides.
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. An 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 inductive 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, Giuseppe Peano and above all with Richard Dedekind.
- Combinatorial proof
- Recursion (computer science)
- Structural induction
- Cajori (1918), p. 197
"The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite."
- Katz (1998), p. 255:
"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.
- Katz (1998), p. 255:
"Al-Karaji's argumen includes in essence the two basic components of a modern argument by induction, namely the truth of the statement for n = 1 (1 = 13) and the deriving of the truth for n = k from that of n = k − 1. 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."
- O'Connor, John J.; Robertson, Edmund F., "Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji", MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Karaji.html .
"Al-Karaji also uses a form of mathematical induction in his arguments, although he certainly does not give a rigorous exposition of the principle."
- Victor J. Katz (1995), p. 165–169.
"The central idea in ibn al-Haytham's proof of the sum formulas was the derivation of the equation [...] Naturally, he did not state this result in general form. He only stated it for particular integers, [...] but his proof for each of those k is by induction on n and is immediately generalizable to any value of k."
- Katz (1998), pp. 255–259.
- Katz (1998), p. 259:
"Like the proofs of al-Karaji and ibn al-Haytham, al-Samaw'al's argument contains the two basic components of an inductive proof. He begins with a value for which the result is known, here n = 2, and then uses the result for a given integer to derive the result for the next. Although al-Samaw'al did not have any way of stating, and therefore proving, the general binomial theorem, to modern readers there is only a short step from al-Samaw'al's argument to a full inductive proof of the binomial theorem."
- Rabinovitch, Nachum. L. Rabbi Levi Ben Gershon and the origins of mathmatical induction,Archive for History of Exact Sciences, 6, 237–248 (1970).
- "It is sometimes required to prove a theorm which shall be true whenever a certain quantity n which it involves shall be an integer or whole number and the method of proof is usually of the following kind. 1st. The theorem is proved to be true when n = 1. 2ndly. It is proved that if the theorem is true when n is a given whole number, it will be true if n is the next greater integer. Hence the theorem is true universally. . .. This species of argument may be termed a continued sorites" (Boole circa 1849 Elementary Treatise on Logic not mathematical pages 40–41 reprinted in Grattain-Guinness, Ivor and Bornet, Gérard (1997), George Boole: Selected Manuscripts on Logic and its Philosophy, Birkhäuser Verlag, Berlin, ISBN 3-7643-5456-9
- Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. ISBN 0-201-89683-4. (Section 1.2.1: Mathematical Induction, pp. 11–21.)
- Kolmogorov, Andrey N. (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 0-486-61226-0. (Section 3.8: Transfinite induction, pp. 28–29.)
- Franklin, J. (1996). Proof in Mathematics: An Introduction. Sydney: Quakers Hill Press. ISBN 1-876192-00-3. (Ch. 8.)
- Acerbi, F. (2000). "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences 55: 57–76. doi:10.1007/s004070000020.
- Bussey, W. H. (1917). "The Origin of Mathematical Induction". The American Mathematical Monthly 24 (5): 199–207. doi:10.2307/2974308. http://links.jstor.org/sici?sici=0002-9890%28191705%2924%3A5%3C199%3ATOOMI%3E2.0.CO%3B2-Y.
- Cajori, Florian (1918). "Origin of the Name "Mathematical Induction"". The American Mathematical Monthly 25 (5): 197–201. doi:10.2307/2972638. http://links.jstor.org/sici?sici=0002-9890%28191805%2925%3A5%3C197%3AOOTN%22I%3E2.0.CO%3B2-2.
- "Could the Greeks Have Used Mathematical Induction? Did They Use It?". Physis XXXI: 253–265. 1994.
- Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Induction". Archives Internationales d'Histiore des Sciences 6: 17–37.
- Katz, Victor J. (1998). History of Mathematics: An Introduction. Addison-Wesley. ISBN 0321016181.
- Rabinovitch, Nachum L. (1970). "Rabi Levi Ben Gershon and the Origins of Mathematical Induction". Archive for the History of Exact Science 6: 237–248. doi:10.1007/BF00327237.
- Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Sciences 9: 1–12. doi:10.1007/BF00348537.
- Ungure, S. (1991). "Greek Mathematics and Mathematical Induction". Physis XXVIII: 273–289.
- Ungure, S. (1994). "Fowling after Induction". Physis XXXI: 267–272.
- Vacca, G. (1909). "Maurolycus, the First Discoverer of the Principle of Mathematical Induction". Bulletin of the American Mathematical Society 16: 70–73. doi:10.1090/S0002-9904-1909-01860-9.
- Yadegari, Mohammad (1978). "The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis 69 (2): 259–262. doi:10.1086/352009. http://links.jstor.org/sici?sici=0021-1753%28197806%2969%3A2%3C259%3ATUOMIB%3E2.0.CO%3B2-B.