Mathematical induction

Mathematical induction is a mathematical proof technique, most commonly used to establish a given statement for all natural numbers, although it can be used to prove statements about any well-ordered set. It is not to be confused with inductive reasoning.

CONTENT
A-C, D-K, L-P, Q-R, S-Z, See also

• Few contemporaries were as profoundly read in the history of mathematics as was De Morgan. No subject was too insignificant to receive his attention. ...In [his] article "Induction (Mathematics)," first printed in 1838, occurs, apparently for the first time, the name "mathematical induction"; it was adopted and popularized by I. Todhunter in his Algebra. The term "induction" had been used by John Wallis in 1656, in his Arithmetica infinitorum; he used the induction known to natural science. In 1686 Jacob Bernoulli criticised him for using a process which was not binding logically and then advanced in place of it the proof from n to n + 1. This is one of the several origins of the process of mathematical induction. From Wallis to De Morgan, the term "induction" was used occasionally in mathematics, and in a double sense, (1) to indicate incomplete inductions of the kind known in natural science, (2) for the proof from n to n + 1. De Morgan's "mathematical induction" assigns a distinct name for the latter process. The Germans employ more commonly the name "vollständige Induktion," which became current among them after the use of it by R. Dedekind in his Was sind und was sollen die Zahlen, 1887.
  • Florian Cajori, A History of Mathematics p.331

• One who extended the theory of equations somewhat further than Vieta was Albert Girard... Like Vieta this ingenious author applied algebra to geometry, and was the first who understood the use of negative roots in the solution of geometric problems. He spoke of imaginary quantities; inferred by induction that every equation has as many roots as there are units in the number expressing its degree; and first showed how to express the sums of their powers in terms of the coefficients.
  • Florian Cajori, A History of Mathematics p.156

• A more modern attempt to explain the fruitfulness of mathematical reasoning is that of Poincaré, who finds it all due to the principle of mathematical induction. This principle of mathematical induction is undoubtedly of wide application, though there are many regions even in arithmetic where it is difficult to see its application, e.g., the science of prime numbers, a science dealing entirely with non-recurring individuals. But the important thing to observe is that this principle of mathematical induction is entirely different from the induction that prevails in the physical sciences.
  • Morris R. Cohen, "The Present Situation in the Philosophy of Mathematics" (Sep 28, 1911) The Journal of Philosophy Psychology and Scientific Methods Vol. VIII, No. 20, p. 539

• It is absolutely certain that if a proposition is established by mathematical induction, it will never be disproved, i.e., if a general proposition is true of n + 1 whenever it is true of n, and also of 1, then no possible number can arise of which this proposition is not true, for the principle of mathematical induction is used in defining all finite integers. Whether, therefore, we agree with Russell and call the principle of mathematical induction a definition, or concede to Poincaré that it is a special axiom, a synthetic proposition a priori, the fact remains that reasoning from it is a purely deductive procedure.
  • Morris R. Cohen, "The Present Situation in the Philosophy of Mathematics" (Sep 28, 1911) The Journal of Philosophy Psychology and Scientific Methods Vol. VIII, No. 20, p. 539

• The propositions of arithmetic, the... operations, for instance, which play such a fundamental rôle even in the most simple calculations, must be demonstrated by deductive methods. What is the principle involved?
  Well, this principle has been variously called mathematical induction, and complete induction, and that of reasoning by recurrence. The latter is the only acceptable name, the others being misnomers. The term induction conveys an entirely erroneous idea of the method, for it does not imply systematic trials.
  • Tobias Dantzig, Number: The Language of Science (1930)

• It is significant that we owe the first explicit formulation of the principle of recurrence to the genius of Blaise Pascal... Pascal stated the principle in a tract called The Arithmetic Triangle which appeared in 1654. Yet... the gist of the tract was contained in the correspondence between Pascal and Fermat regarding a problem in gambling, the same correspondence which is now regarded as the nucleus from which developed the theory of probabilities.
  It surely is a fitting subject for mystic contemplation that the principle of reasoning by recurrence, which is so basic in pure mathematics, and the theory of probabilities, which is the basis of all deductive sciences, were both conceived while devising a scheme for the division of stakes in an unfinished match of two gamblers.
  • Tobias Dantzig, Number: The Language of Science (1930)

• Despite the age-long tyranny exercised by the Aristotelian logic... Of all argument forms, there is one which, viewed as the figure of the way in which the mind gains certainty that a specified property belonging, but not immediately by definition, to each element of a denumerable assemblage of elements does so belong, enjoys the distinction of being at once perhaps the most fascinating, and, in its mathematical bearings, doubtless the most important single form in modern logic. This form is that variously known as reasoning by recurrence, induction by connection (De Morgan), mathematical induction, complete induction, and Fermatian induction—so called by C. S. Peirce, according to whom this mode of proof was first employed by Fermat. Whether or not such priority is thus properly ascribed, it is certain that the argument form in question is unknown to the Aristotelian system, for this system allows apodictic certainty in case of deduction only, while it is the distinguishing mark of mathematical induction that it yields such certainty by the reverse process, a movement from the particular to the general, from the finite to the infinite.
  Of the various designations of this mode argument, "mathematical induction" is undoubtedly the most appropriate, for though one not be able to agree with Poincaré that the mode in question is characteristic of mathematics, it is peculiar to science, being indeed, as he has called it, "mathematical reasoning par excellence."
  • Cassius J. Keyser, "Induction, Mathematical," The Americana: A Universal Reference Library (1912) Vol. 11

• This procedure is the demonstration by recurrence. We first establish a theorem for n = 1; then we show that if it is true of n - 1, it is true of n, and thence conclude that it is true for all the whole numbers. ..Here then we have the mathematical reasoning par excellence, and we must examine it more closely.
  ...The essential characteristic of reasoning by recurrence is that it contains, condensed, so to speak, in a single formula, an infinity of syllogisms.
  ...to arrive at the smallest theorem [we] can not dispense with the aid of reasoning by recurrence, for this is an instrument which enables us to pass from the finite to the infinite.
  This instrument is always useful, for, allowing us to overleap at a bound as many stages as we wish, it spares us verifications, long, irksome and monotonous, which would quickly become impracticable. But it becomes indispensable as soon as we aim at the general theorem...
  In this domain of arithmetic,.. the mathematical infinite already plays a preponderant rôle, and without it there would be no science, because there would be nothing general.
  • Henri Poincaré, Science and Hypothesis (1901) Ch. I. On the Nature of Mathematical Reasoning, Tr. (1905) George Bruce Halstead pp.10-12

• We can not... escape the conclusion that the rule of reasoning by recurrence is irreducible to the principle of contradiction. ...Neither can this rule come to us from experience... This rule, inaccessible to analytic demonstration and to experience, is the veritable type of the synthetic a priori judgment. On the other hand, we can not think of seeing in it a convention, as in some of the postulates of geometry. ...it is only the affirmation of the power of the mind which knows itself capable of conceiving the indefinite repetition of the same act when once this act is possible. The mind has a direct intuition of this power, and experience can only give occasion for using it and thereby becoming conscious of it.
  • Henri Poincaré, Science and Hypothesis (1901) Ch. I. Tr. (1905) George Bruce Halsted p.13

• But, one will say, if raw experience can not legitimatize reasoning by recurrence, is it so of experiment aided by induction? We see successively that a theorem is true of the number 1, of the number 2, of the number 3 and so on; the law is evident, we say, and it has the same warranty as every physical law based on observations, whose number is very great but limited. But there is an essential difference. Induction applied to the physical sciences is always uncertain, because it rests on the belief in a general order of the universe, an order outside of us. Mathematical induction, that is, demonstration by recurrence, on the contrary, imposes itself necessarily, because it is only the affirmation of a property of the mind itself.
  • Henri Poincaré, Science and Hypothesis (1901) Ch. I. Tr. (1905) George Bruce Halsted pp.13-14

• We could call it "proof from n to n + 1" or still simpler "passage to the next integer." Unfortunately, the accepted technical term is "mathematical induction." This name results from a random circumstance. ...Now, in many cases... the assertion is found experimentally, and so the proof appears as a mathematical complement to induction; this explains the name.
  • George Pólya, How to Sove It (1945)

• Dedekind proves mathematical induction, while Peano regards it as an axiom. This gives Dedekind an apparent superiority, which must be examined. ...not because of any logical superiority, it seems simpler to begin with mathematical induction. And it should be observed that, in Peano's method, it is only when theorems are to be proved concerning any number that mathematical induction is required. The elementary Arithmetic of our childhood, which discusses only particular numbers, is wholly independent of mathematical induction; though to prove that this is so for every particular number would itself require mathematical induction. In Dedekind's method, on the other hand, propositions concerning particular numbers, like general propositions, demand the consideration of chains. Thus there is, in Peano's method, a distinct advantage of simplicity, and a clearer separation between the particular and the general propositions of Arithmetic. But from a purely logical point of view, the two methods seem equally sound; and it is to be remembered that, with the logical theory of cardinals, both Peano's and Dedekind's axioms become demonstrable.
  • Bertrand Russell,The Principles of Mathematics (1903) Vol. 1 p.248

• Mathematical induction, which is purely ordinal... may be stated as follows: A series generated by a one-one relation, and having a first term, is such that any property, belonging to the first term and to the successor of any possessor of the property, belongs to every term of the series.
  • Bertrand Russell,The Principles of Mathematics (1903) Vol. 1 p.371

• The use of mathematical induction in demonstrations was, in the past, something of a mystery. There seemed no reasonable doubt that it was a valid method of proof, but no one quite knew why it was valid. Some believed it to be really a case of induction, in the sense in which that word is used in logic. Poincaré considered it to be a principle of the utmost importance, by means of which an infinite number of syllogisms could be condensed into one argument. We now know that all such views are mistaken, and that mathematical induction is a definition, not a principle.
  • Bertrand Russell, Introduction to Mathematical Philosophy (1919) p. 27

• Many years ago I published in the Formulaire de Mathématique of Professor Peano an account of the first discovery of mathematical induction as due to the Italian Maurolycus. But this paper seems to have had only a small diffusion. ...the most original of his works is the treatise on arithmetic "Arithmeticorum libri duo" written in the year 1557 and printed in Venice in the year 1575 in the collection "D. Francisci Maurolyci Opuscula mathematica."
  In the Prolegomena to this work he points out that neither in Euclid nor in any other Greek or Latin writer (among them he enumerates Iamblichus, Nicomachus, Boetius) is there, to his knowledge, a treatment of the polygonal and polyhedral numbers, and he reproaches Jordanus for having been content with a useless repetition of what was written by Euclid.
  "Nos igitur [he says] conabimur ea, quae super hisce numerariis formis nobis occurrunt, exponere: multa interim faciliori via demonstrantes, et ab aliis authoribus aut neglecta, aut non animadversa supplentes."
  This new and easy way is nothing else than the principle of mathematical induction. This principle is used at the beginning of the work only in the demonstration of very simple propositions, but in the course of the treatise is applied to the more complicated theorems in a systematic way.
  ...Was Pascal unaware of the book of Maurolycus? In his Traité du triangle arithmétique printed perhaps in the year 1657, he never mentions Maurolycus, notwithstanding that, in my opinion, this treatise is only an application of the method discovered by Maurolycus. But Pascal, shortly after, being engaged in the polemic concerning the cycloid, in the well known letter, "Lettre de Dettonville à Carcavi" had to demonstrate a proposition concerning the triangular and pyramidal numbers. He says then:"Cela Est Aisé Par Maurolic."It is strange to point out that not even the name of Maurolycus has been included in the Table analytique of the old edition of the works of Pascal, and more strange that the editors of the new edition of the "Oeuvres" of Pascal in a very incomplete historical note before the reimpression of the Traité du triangle arithmétique never mention the name of one of the greatest European mathematicians of the sixteenth century.
  • G. Vacca, "Maurolycus the First Discoverer of the Principle of Mathematical Induction" (Nov, 1909) p. 70, Bulletin of the American Mathematical Society Vol. 16 (Oct, 1909 - July, 1910) Note: Vacca cites Traité du triangle arithmétique (Vol. 3 pp. 435-444)

• In his address to the Mathematical Section at the British Association Meeting of 1869 at Exeter, Professor J. J. Sylvester laid much stress upon the employment of inductive philosophy in mathematics. He said that he was aware that many who had not gone deeply into the principles of mathematical science believed that inductive philosophy, or the method of evolving new truths by induction, was reserved for the experimental sciences, and that the methods of investigation in mathematical science might all be classified as deductive. He went on to say that this opinion is not a correct one, and that many valuable results are obtained in mathematical science by induction, or reasoning from particulars to generals, which could not otherwise be obtained so easily. Although making a distinction between mathematical induction and the induction used in natural philosophy, De Morgan, in his article in the 'Penny Cyclopædia' on this subject, states that an instance of mathematical induction occurs in every equation of differences and in every recurring series. Taking the definition of induction as given by Dr. Whateley, namely, "a kind of argument which infers respecting a whole class what has been ascertained respecting one or more individuals of that class," it will be evident to any experimenter in chemical or physical science who is also acquainted with the use of induction in mathematical science, that mathematical induction is of a higher and more perfect kind than the induction used in the physical sciences, especially when it assumes the form of successive induction as De Morgan calls it, and as it is employed in recurring series.
  It is this high class of reasoning which is involved in the construction of series that recur according to a given law, that makes the use of recurring series so valuable in unitation.
  • W. H. Walenn, "On Negative and Fractional Unitates," The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science (1873) pp. 36-37

• M. Poincaré finds the answer to these questions in the so-called 'mathematical induction' which proceeds from the particular to the more general, but at the same time does so by steps of the highest degree of certitude. In this process he sees the creative force of mathematics, which leads to real proofs and not mere sterile verifications. The illustrations used to make the thought clear are taken from the beginnings of arithmetic, where mathematical thought has remained least elaborated and uncomplicated by the difficult questions related to the notion of space. In successive instances it is shown how more general results are obtained from fundamental definitions and from previous results by means of mathematical induction. In each case the advance is made by virtue of that "power of the mind which knows that it can conceive of the indefinite repetition of the same act as soon as this act is at all possible. The mind has a direct intuition of this power and experience gives only the opportunity to use it and to become conscious of it."
  The conviction that the method of mathematical induction is valid our author regards as truly an à priori synthetic judgment; the mind can not tolerate nor conceive its contradictory and could not even draw any theoretic consequences from the assumption of the contradictory. No arithmetic could be built up, rejecting the axiom of mathematical induction, as the non-Euclidean geometries have been built up, rejecting the postulate of Euclid.
  • J. W. A. Young, "Poincare's Science and Hypothesis" (Dec. 16, 1904) a book review in Science Vol. XX (Jul-Dec, 1904)

• Mathematics
• History of mathematics

Wikipedia has an article about:

Mathematical induction

• Bertrand Russell, Introduction to Mathematical Philosophy (1920)