# Full text of "The Origin of Mathematical Induction"

## See other formats

STOP Early Journal Content on JSTOR, Free to Anyone in the World This article is one of nearly 500,000 scholarly works digitized and made freely available to everyone in the world by JSTOR. Known as the Early Journal Content, this set of works include research articles, news, letters, and other writings published in more than 200 of the oldest leading academic journals. The works date from the mid-seventeenth to the early twentieth centuries. We encourage people to read and share the Early Journal Content openly and to tell others that this resource exists. People may post this content online or redistribute in any way for non-commercial purposes. Read more about Early Journal Content at http://about.jstor.org/participate-jstor/individuals/early- journal-content . JSTOR is a digital library of academic journals, books, and primary source objects. JSTOR helps people discover, use, and build upon a wide range of content through a powerful research and teaching platform, and preserves this content for future generations. JSTOR is part of ITHAKA, a not-for-profit organization that also includes Ithaka S+R and Portico. For more information about JSTOR, please contact support@jstor.org. The American Mathematical Monthly OFFICIAL JOURNAL OF THE MATHEMATICAL ASSOCIATION OF AMERICA Volume XXIV May, 1917 Number 5 THE ORIGIN OF MATHEMATICAL INDUCTION.* By W. H. BUSSEY, University of Minnesota. Introduction. A criticism often made of mathematics as a subject of study in our high schools and colleges is that it involves nothing of observation, experiment, and induction as these terms are understood in the natural sciences. Whether or not the old and well-developed branches of mathematics as taught in our schools have been made into such well-organized deductive disciplines that this criticism is just, it is true that the work of the original investigators who have developed mathe- matical science has involved a great deal of observation, experiment, and induc- tion; induction being, according to the Century Dictionary, "the process of drawing a general conclusion from particular cases." Observation and experi- ment in mathematics do not involve costly and complicated apparatus as often in physics, astronomy, and the other sciences, pencil and paper being all that is ordinarily necessary, but they are just as truly observation and experiment. In the natural sciences a law arrived at by observation and experiment has to be verified by subsequent experiment by the same or other observers, either directly by repetition of the same experiment or indirectly by testing some logical consequence of the law in question. But in mathematics it is often possible to give rigorous demonstrations of theorems arrived at by ordinary induction. One method of clinching an argument by ordinary induction is what has been called mathematical induction. A more significant name and one that is being used more and more is complete induction. It is not a method of discovery but a method of proving rigorously that which has already been discovered. It is one of the most fruitful methods in all mathematics. It has * Read before the Minnesota Section of the Association at its second meeting, April 9, 1917. 199 200 THE ORIGIN OF MATHEMATICAL INDUCTION. applications in widely differing branches of mathematics, in algebra, trigonom- etry, calculus, theory of probability, theory of groups, etc. In American college algebras it is used in proving divisibility theorems like x n — y n is divisible by x — y for all positive integral values of n; in proving the binomial theorem for positive integral exponents; and in proving given formulas for the summation of series, like l 3 + 2 3 + 3 3 + h n 3 = \n\n + l) 2 . A theorem provable by complete induction involves a statement about an integer, usually denoted by n, which is to be proved true for all values of the integer. The proof is in two parts. The first part proves that the theorem is true in a special case, that is for a special value of the integer n involved in the theorem. The second part of the proof is what has been called the argument from nton+1. It is the argument which justifies one in drawing a general con- clusion from the special cases verified. For this reason it may properly be called the induction argument. The method is too well known to need any further explanation here. If one assumes that the reader understands the method it is not necessary every time to write out explicitly the argument by which the two parts of the proof taken together establish the theorem in question for all values of n. It is necessary only to exhibit both parts of the proof. Indeed it is quite customary for writers of mathematical books to give only the argument from n to n + 1 and to leave the rest to be supplied by the reader. Maukolycus's Use of Complete Induction. Cantor in his Vorlesungen iiber Geschichte der Mathematik 1 says that Pascal was the originator of the method of complete induction. 2 But he has corrected this statement in a brief note in the Zeitschrift fur Mathematischen und Natur- wissenschaftlichen Unterricht? In this note he says that he has been informed by G. Vacca that Maurolycus 4 described and used the method in his arithmetic which was published in 1575. I quote from Cantor: " Ich wurde durch Herrn G. Vacca darauf aufmerksam gemacht dass schon Maurolycus in seiner Arithmetik von 1575 die Methode genau geschildert und von ihr Gebrauch gemacht hat. Aus Maurolycus aber entnahm sie erst Pascal. Daruber kann nicht der leiseste Zweifel obwalten da Pascal sich 1659 fur den Satz 2 [«fe±a]_,.^ ausdriicklich auf Maurolycus beruft welcher gerade diesen Satz mittels voll- standiger Induktion bewiesen hat." 5 1 Vol. II, p. 749. 2 W. W. R. Ball's History of Mathematics has nothing to say about the origin of complete induction. 3 Vol. XXXIII (1902), p. 536. 4 D. Francisci Maurolyci, Abbatis Messanensis, Mathematici Celeberrimi, Arithmeticorum Libri Duo. Venice, 1575. 8 The theorem referred to is equivalent to twice the nth triangular number minus n equals n*. See page 202 of this paper. THE ORIGIN OP MATHEMATICAL INDUCTION. 201 Maurolyeus in Book I of Ms arithmetic begins with the definitions of different kinds of numbers, namely, even, odd, triangular, square, numeri parte altera longiores, etc. By definition the nth triangular number is the sum of the integers from 1 to n inclusive and the nth numerus parte altera longior is n(n — 1). He arranges them in a table as follows: Integers Even Odd Triangular Square N. P. A. L. 1 1 1 1 1 2 2 3 3 4 2 3 4 5 6 9 6 4 6 7 10 16 12 5 8 9 15 25 20 6 10 11 21 36 30 7 12 13 28 49 42 n E T S L I have added at the bottom of each column a symbol for the nth number of that column which I find convenient in explaining the work of Maurolyeus. Numbers in the same row Maurolyeus calls collateral numbers. A number in one row is said by him to precede any number in the following row and to follow any number in the preceding row; e. g., he calls 15 the triangular number following the even number 6. I quote a number of Maurolycus's theorems for reference. In some cases I give the proofs as given by him. The numbering of the theorems is his. Proposition IV. "The odd numbers are obtained from unity by successive additions of 2." (Maurolyeus uses this in Proposition VI in the form 0„ + 2 = O n +i, i- e., the nth. odd number plus 2 equals the next odd number.) Proposition VI. "Every integer plus the preceding integer equals the col- lateral odd number." [In symbols this is n + (n — 1) = O n .] Maurolycus's proof, freely translated, is this : "The integer 2 added to unity makes the integer 3 but when added to 3 it makes an amount greater by 2 and this (by virtue of Proposition IV) is the next odd integer, namely 5. Again since the integer 3 added to 2 makes 5, which is the collateral odd integer, when it is added to 4 the result will be greater by 2, that is (by virtue of Proposition IV), it will be the next odd integer which is 7. And in like manner to infinity as the proposition states." This is not a very clear statement of a proof by mathematical induction but the idea is there. Maurolycus's ideas might be put more clearly as follows : The theorem is true by inspection in the case of the first two integers 1 and 2, i. e., 2 + 1 = 3 which is the odd integer collateral to 2. This is the first part of the induction proof. Maurolyeus then takes up the special cases 3 + 2 = 5 and 4+3=7 and in doing so he shows by his repeated use of Proposition IV that 1 Numeri Parte Altera Longiores. 202 THE OHIGIN OF MATHEMATICAL INDUCTION. the other part of the mathematical induction proof was in his mind. His Proposi- tion IV furnishes the argument from n to n + 1. In modern notation it would be put in this way: If n + (n — 1) = On (i- e., if any integer plus the preceding one equals the collateral odd integer), the result of adding 1 + 1 to the left side and 2 to the right side is (n + 1) + n = 0„ + 2. But by Prop. IV, 0„ + 2 = 0„+i. Therefore (» + 1) + n = 0„ + i. This argument from n to n + 1 seems to have been in Maurolycus's mind. But if this were the only example of complete induction in his work it might not be a conclusive proof that he understood the method. Proposition XV is a much more convincing case. But before giving an account of it I wish to state several other of his theorems for reference and to discuss the proposition which Cantor says Pascal got from Maurolycus. Proposition VIII. "Every triangular number doubled equals the following numerus parte altera longior." (In symbols this is 2T n = £ B +-iO Proposition X. " Every numerus parte altera longior plus its collateral integer equals the collateral square number." (In symbols, L n + n = S n .) Proposition XL "Every triangular number plus the preceding triangular number equals the collateral square number." (In symbols, T n + T„-i = S n .) This proposition, although stated somewhat differently by Cantor, is the one which Cantor says Pascal got from Maurolycus and which he says Maurolycus proved by complete induction. For since a triangular number is equal to the sum of the natural numbers in order, T n -\ = T n — n, and it follows that T n + T n -i = 2T„ — n; or, since by the formula for the sum of an arithmetic progression 1 the nth triangular number is [n(n + l)]/2, the equation T n + T n -i = S„ is equivalent to [»JE±i)]_ B = s , = which is the form that Cantor gives. But Cantor is wrong in saying that this theorem was proved by Maurolycus by complete induction. For Maurolycus's proof (in modern notation) is this: By definition T n = Tn-i + n. Therefore T n + T n -\, the left-hand member of the relation to be proved, is equal to 2Tn-i + n which equals L n + n (by Proposition VIII), and this equals S B (by Proposition X). Proposition XIII. "Every square number plus the following odd number equals the following square number." (In symbols, *S„ + n +i = $n+i.) Proposition XV. "The sum of the first n odd integers is equal to the nth square number." 2 (In symbols, 0\ + 2 + 3 + ••• + n = S n .) Mauroly- cus's proof freely translated is this: x In Proposition VII, which I have not quoted, Maurolycus uses the usual arithmetical progression device for proving T n = [n(n + l)]/2. He says in effect: r» = l + 2 + 3+"- +n and also T„ = n + (n — 1) + (n — 2) + ■■ • +2 + 1, and therefore by addition 2T n = n(n + 1). * This theorem in the form 1 + 3 + 5 + • • • + (2n — 1) = n 2 is often given in American college algebras as one of the first examples of complete induction to be proved by the student. THE OEIGIN OF MATHEMATICAL INDUCTION. 203 "By a previous proposition 1 the first square number (unity) added to the following odd number (3) makes the following square number (4); and this second square number (4) added to the 3d odd number (5) makes the 3d square number (9); and likewise the 3d square number (9) added to the 4th odd number (7) makes the 4th square number (16); and so successively to infinity the proposition is demonstrated by the repeated application of Proposition XIII." This is a clear case of a complete induction proof. Proposition XIII is used as a lemma. It furnishes the argument from ntoti+ 1. The first few special cases are mentioned in Proposition XV itself. In modern symbols the proof would be this : 1st. The theorem is true when n = 1. 2d. Assume that it is true when n = k, i. «., assume Oi + Ot + • • • + * = Sk', add Ok+i to both sides of this equation and get Oi + O2 + • • • + Ok+i = Sk + Ok+i which equals Sk+i, by Proposition XIII. Pascal's Use op Complete Induction. Pascal repeatedly used the method of complete induction in connection with his arithmetical triangle 2 and its applications. Cantor's argument that Pascal borrowed the method from Maurolycus is valid in spite of the fact that he is in error in saying that Maurolycus proved Proposition XI of his arithmetic by complete induction. For Pascal does refer to Maurolycus for a proof of this proposition which shows that Pascal was familiar with the part of Maurolycus's arithmetic in which Maurolycus does use complete induction. It is in a letter from Pascal (writing under the pseudonym Amos Dettonville) to Carcavi 3 that Pascal refers to Maurolycus for the proof of the theorem that "twice the nth triangular number minus n equals n 2 ." Pascal says " Cela est aise par Maurolic." Pascal makes use of this theorem in connection with his work on centers of gravity. I give the following as two interesting examples of Pascal's use of the method of complete induction. I use modern algebraic notation for the sake of brevity. Without modern notation it would be necessary to explain the construction of Pascal's arithmetical triangle and many of his theorems about it. Theoeem. 4 The number of combinations of n things hat a time is to the number of combinations of n things k + 1 at a time as k + 1 is to n — k. (In symbols, n C k : n Ck+i = k + 1 : (n — k.) Proof. — First part. By inspection the theorem is true when n = 2. For then the only possible values of k and k + 1 are 1 and 2 respectively and j& : »& = 2 : 1. Second part. Assume that the theorem is true when n = q. That is, assume* (A) q Ck : 9 Ck+i = k + l:q-k for all positive integral values of k < q. It is then to be proved that, on this assumption, (B) C+ A- : 5+ A +1 =j + l:q + l-j for all positive integral values of j < q + 1. 1 He refers to Proposition XIII. 2 Oeuvres Completes de Blaise Pascal, Paris, 1889, Vol. Ill, p. 243 ff. 3 L. c, p. 376. 4 This is Pascal's "Consequence XII," 1. e., p. 248. 5 This relation (A) is seen by inspection to be true when k = q, if we define ,C t = when t > s. 204 THE ORIGIN OF MATHEMATICAL INDUCTION. [(B) is obtained from (A) by replacing q in (A) by q + 1 and by using another letter for k to avoid confusion later.] The well-known relation 1 (C) nCb = N-lCs-1 + n-iCb is needed to prove that (2?) follows from (A). By relation (C) the left-hand member of (B) is equal to g^j— l ~r" ii g~'i' g^ j gC j T* fiC j+l - , g C J-t-1 On applying relation (A) to the minor fractions a C,-_i/ fl C,* and a C,>i/ fl C,- this becomes — -i— + i ? - j + 1 ' y + 1 + J + 1 which was to be proved. Another example from Pascal is this problem in the division of stakes in a gambling game. Two players A and B of equal skill, playing for a stake P, wish to leave the game table before finishing their game. Their scores and the number of points which constitute the game being given indirectly as follows: Player A lacks a points of winning and player £ lacks /3 points. If a + {5 be denoted by n, Pascal says that the stakes should be divided between B and A in the ratio (n-lCo + n-lCl + n-lCz + • • • + n-lC a -l) l (n-lC + n-lC a +l + ' ' ' + n-lC„_i). Since 2 n-lCo + n-lCl + n-lCi + • • • + n-lCn-1 = 2 B_1 , this is the same as saying that B's share of the whole stake is P O^ZJ [n-lCo + n-lCl + n-lCa + + n-lCm-l]> and ^4's share is P q^ZJ [n-lC a + n—lCa+1 T ' " ' "I" n— lt/n^-lj- Proof. — Krs< Pari. The .theorem is true in the special case in which n = 2. For in this case the scores of A and B are even and each lacks only one point of winning. They are of equal skill and so one is as likely to win the game as the other and the stake should be divided in the ratio 1 to 1. The theorem states that the stake should be divided in the ratio iCo : id, which is 1 : 1. The theorem is also true in the special case in which n = 3. In this case the score at the end of play must be such that one player lacks one point and the other lacks two points. Suppose that it is A who lacks the one point. Then B lacks two points. If the play were to continue for one more point and if A were to win that point he would win the game and be entitled to the whole stake P. But if he were to lose he would be entitled to P/2 by virtue of the special 1 Fine, H. B., College Algebra, p. 404. This relation is true when B = and when N ^R if we define ,C<> = 1 and ,Ct = when t > s. 2 It is customary to give nC the meaning nC = 1 by definition. The relation b-iCo + n-iCi + h n-iC„_i = 2" _1 is more usually written „_iCi + „_iC 2 + • • • + n-iC„_i = 2 n_1 — 1. See Fine, H. B., College Algebra, p. 402. THE ORIGIN OF MATHEMATICAL INDUCTION. 205 case previously considered. The division of the stake should therefore be such that A will get the P/2 which he is entitled to in case he loses the next point and one half of the other P/2 which he has an even chance of winning. This is the same as saying that A should receive the arithmetic mean between P and P/2. The stake should therefore be divided between B and A in the ratio 1 to 3. The theorem gives the ratio 2 C : (2C1 + 2C2), which is 1 : 3. If A lacked 2 points and B one point the division between B and A would be in the ratio 3:1. The theorem in this case gives (2C0 + 2C1) : 2 CV which is 3 : 1. Second Part of the Proof. Assume the theorem true for n, i. e., assume that when the points lacking for A and B have their sum equal to n the equitable division of the stake is as the theorem indicates. To prove that on this assumption the theorem is true when the sum of the points lacking for A and B is n + 1, suppose that A lacks k points and B lacks I points where k + I = n + 1. If the play were to continue and A were to win the next point, the sum of the points lacking after that would be exactly n points (i. e., A would lack k — 1 points and B would lack / points) and by our assumption the rule given by the theorem may be applied. The result of applying the theorem in this case is p n^i [n-lCo + n-lCi + • • • + n-lCk-l] for B's share of the stake. (This comes from putting k — 1 for a in the statement of the theorem.) But if A were to lose then B would win and A would lack k points and B only I — \ points. The sum of the points lacking would be exactly n and the rule given by the theorem may be applied as before, putting k for a. The result is P n^i U-lCo + n-lCi + • • • + n-lCk-l] for B's share. As in the special case previously considered B's share of the stake should be the arithmetic mean between P , P O^TJ n-lCt + n-lCl + • • • + n-lCh-l] and 2^1 [n-lCj + m-lCl + • • • + n-lCi_l] which equals p r^; [2(n-lCo + n-lCl + • • • + n-lCh-i) + n-lC *_]]. This may be written in the form p o^ [n-lCo + (n-lCe + n-lCl) + (n_lCi -{-n-lCi) + • • • + (»-lCi_j + n-lCjfc_2) + (n-lCjr_2 + n -lC*_i)]. But by virtue of the relation 2/Cr = jv_iCji_i + k-iCb, used in the proof of the preceding theorem of Pascal's, each binomial in this expression may be replaced by a single term so that B's share is p nZ [nC(, + B Ci + «C 2 + • • - + TtCk-1 + nC k-l] which is just what the theorem gives for B's share. This completes the induction argument for this theorem of Pascal's. Other and More Recent Uses op Complete Induction. The following examples will give some idea of the variety of uses which can be made of the method of complete induction. 1. (a) x n — y n is divisible by x — y. (b) x n — y n is divisible by x + y when n is even but not 1 when n is odd. (c) x n + y n is divisible by x + y when n is odd but not 1 when n is even. 1 The reference here (as elsewhere in the paper) is to algebraic divisibility. The statements obviously need not be true for the case of divisibility of the integers represented by the forms. 206 THE ORIGIN OF MATHEMATICAL INDUCTION. Negative divisibility theorems like the second parts of (b) and (c) are just as easily proved by complete induction as positive divisibility theorems such as (a). 2. 1-2 + 2-3 +3-4+ ■ ■ ■ + n(n+ I) = ±n(n+ l)(n + 2). American college algebras contain many such examples in the summation of series. 3. Be Moivre's Theorem, (cos 9 + i sin 0)" = cos nd + i sin nd for positive integral values of n. 4. The binomial theorem for positive integral exponents. 5- If F n (x) = (x + a x ) (x + a 2 ) (x + a 3 ) • • • (x + a n ) = x n + A 1 x»~ 1 + A 2 x»-> + •■■ + A n ^x + A n , then Ax = 2«i, At = 2aia 2 , A 3 = Sa 1 a 2 a 3 , • • •, A n = aia 2 - • -a n . (See H. Weber and J. Wellstein, Encyclopadie der Elementar-Mathematik, volume I, p. 196.) _ 6. Fermat's Theorem. a n - a h divisible by n if a is any integer and n is a prime integer. (See Weber and Wellstein, volume I, p. 197.) 7. The Polynomial Theorem. (x + y + z+ ...)" = 2-TflTi — - xYz*---. alplyl'" " (See Weber and Wellstein, volume I, p. 198.) 8. Any polynomial symmetric in x u x 2 , ••-,£„ is equal to a polynomial in the elementary symmetric functions. (See Weber and Wellstein, volume I, p. 232.) 9. A necessary and sufficient condition that a polynomial in any number of variables vanish identically is that all its coefficients are zero. (For a proof of this theorem for one variable and its extension by complete induction see Maxime Bdcher's Introduction to Higher Algebra, p. 5.) 10. If f t andf 2 are polynomials in any number of variables of degrees mi and m 2 respectively, the product /i/ 2 will be of degree m x m 2 . (See B6cher's Higher Algebra, p. 6.) 11. A necessary and sufficient condition that a polynomial f{xix 2 - ■ -x n ) vanish identically is that it vanish throughout the neighborhood of a point (aia 2 ---a n ). (See Bocher's Higher Algebra, p. 10.) 12. Iff(x) is a polynomial of the nth degree, fix) = a&» + a 1 x n ~ 1 + •■■+ a n - x x + a n (o 4= 0), there exists one and only one set of constants a t a 2 - ■ -a„ such that f(x) = a Q (x - a{)(x - a 2 ) • ■ ■ (x - a n ). To prove this theorem by complete induction one needs the fundamental theorem of algebra that there is at least one value of x for which such a polynomial as f(x) vanishes. (See Bocher's Higher Algebra, p. 17.) THE OEIGIN OF MATHEMATICAL INDUCTION. 13. If all the (r + l)-rowed principal minors of the symmetrical matrix 207 a n «12 • ■ a\ n 021 022 • ain (where a,,- = aji) a»i a n i • ann are zero, and also all the (r + 2)-rowed principal minors, then the rank of the matrix is r or less. (See B6cher's Higher Algebra, p. 57.) 14. The conjugate of the product of any number of matrices is the product of their conjugates taken in reverse order. (See Bocher's Higher Algebra, p. 65.) 15. If y = u\Uf • -u„ and y', u\, u<t ', etc., denote first derivatives with respect to a variable x, then t. = Hi _i_ Vl. 4. _l TO*, y Mi u 2 u„ ' 16. Leibnitz's Theorem. d n (uv) n(n - 1) — = U n V + nU n -iCi -\ ^ Un-iV 2 + dx n 1-2 + nuiV^-i + uv n where u and v are functions of x and the subscripts denote derivatives with respect to x. That is, du d?u «i = dx' «2 = ^i, etc. (For a proof of this theorem and some examples of its use see G. A. Osborne's Differential and Integral Calculus, pages 65-67.) 17. (a) Limit (x\ + xi • • • + x n ) — limit x\ + limit £ 2 + • • • + limit x n . (b) Limit {xix^ • -x n ) — (limit x{) (limit x%) • • • (limit x n ). (See W. F. Osgood's Differential and Integral Calculus, p. 16.) 18. If d n y (- l)"" 1 ^- 1)! y=logx, ^= . Numerous examples like this are to be found in G. A. Osborne's Differential Calculus, pages 62-65.