Skip to main content

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.