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:

1. The statement is proved for the first possible value of n (usually 0 or 1, but other "starting values" are possible).
2. 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 ).
3. 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.

1. 2. The conclusion is then

1. for .

## History

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 nk − 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.