# Full text of "On 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 AMEEICM MATHEMATICAL MONTHLY. Entered at the Post-office at Springfield; Missouri, as second-class matter. VOL. XV. AUGUST-SEPTEMBER, 1908. NOS. 8-9. ON MATHEMATICAL INDUCTION. By DR. J. W. A. YOUNG, The University of Chicago. I. Its Function and Place. In the secondary school, the pupil in mathematics is becoming famil- iar with this fundamental type of thought by working in it and applying it. He thinks mathematics, but not about mathematics. In college, when the student begins to philosophize, he may, in addition to working in and with mathematics, also begin to think about it, to analyze and classify its proces- ses of thought, to seek its essential characteristics and the lines of demar- cation between it and other subjects. He will learn that many mathematicians see the distinctive marks of their science, not in its subject matter, not in numbers, points, lines and symbols, but in the mode of thinking which is used.* He will find the definition, "Mathematics is the science which draws necessary conclusions, "t a good expression of this conception of the subject. It identifies mathemat- ics with deductive reasoning, and accounts for the peculiar certainty and accuracy which, in his experience, has been its distinctive characteristic. But when he thinks of the way in which he works out mathematics, solves problems, does "original" work of any description, he sees that in- duction plays an important part in this aspect of mathematics. Further, as his acquaintance with the subject matter of mathematics widens, he will find numerous instances in which concepts are extended and theorems generalized. He will frequently find that the course of develop- ment is from the particular to the general, and in such cases he will often find employed a method of reasoning called mathematical induction,% which shares with non-mathematical induction the peculiarity of generalizing from particular instances, but which nevertheless, like other mathematics, pro- duces that unhesitating confidence in the absolute accuracy of the result "For an instructive discussion of various definitions of mathematics, see Bocher, Bulletin of American Math- ematical Society, 1904, p. 115. tPeirce, American Journal of Mathematics, Vol. IV. t'Also, Complete Induction, and, in German, der Kaestnerische Schluss, although published by Pascal in 1662 (Cantor, Gesch. d. Math., II. p. 684) long before the time of Kaestner (1719-1800). 146 which is not felt as to the results of non-mathematical reasoning. This two-fold property leads one of the most acute thinkers of the day* to see in mathematical induction the sole instrument whereby the mathematician en- larges the sum-total of mathematical knowledge (at least in pure mathe- matics or arithmetic, as distinguished from geometry and infinitesimal anal- ysis). Whether or not we concurt without reserve in Poincarl's thesis that "we can advance only by means of mathematical induction, which alone can teach us anything new," all will agree that explicitly it produces a large body of the mathematician's most valued results, and that implicitly it lurks unsuspected at the bottom of the reasoning by which a far greater body of mathematical truth is established. The process of mathematical induction is exceptionally well fitted to introduce the beginner to the philosophic study of mathematical thinking, since it deals neither with the delicate and abstract questions relative to the foundations of mathematics, whose successful treatment requires extensive experience in mathematical reasoning, nor with such concepts from the bor- derland of mathematics and philosophy as have in the past proved themselves vague and elusive (for example, "continuity" or "infinity"). While a care- ful discussion of the logical nature and function of mathematical induction should perhaps be deferred to a period later than the early collegiate years, practical acquaintance with the process itself and a certain amount of readi- ness in its use may well be acquired at that time. To this end, a consider- able body of material is requisite, both to illustrate the range and fertility of the method and also to supply a fund of exercises sufficiently ample to meet the student's need of considerable practice, and to permit variety in the same class and in successive classes. II. Its Character. I give some of the exercises which I have collected for such use from many sources, preceded by a discussion of the method itself based on a par- ticular example. By trial: 1=1, 1+2=3, 1+2+3=6, 1+2+3+4=10, 1+2+3+4+5=15. Letting S n denote the sum of the first n positive integers, the equa- tions can be written: c _ L2J c _jy* o -M c _4J> <? _5.6 *Poineare, Bur la nature du raisonnetnent matkematuiue. Revue de metaphysique et morale, 1894, p. 371. tl have discussed elsewhere ( The Teaching of Mathematics, p. 25, note) the manner in which deductive rea- soning enlarges the sum-total of mathematical knowledge. 1 1.2 means 1X2. 147 Examining these equations, we see that they are all of the type: o _ n(n+l) On — o • By taking a few additional ones, we find that the formula continues to hold. Thus: S e =l+2+3+4+5+6=21=^. Trial of additional instances increases the "moral" certainty that the formula is true for every positive integer n, but no matter how many instances we may have the patience to try, mathematical certainty is not achieved thereby. This is attained by means of the mind's power of oper- ating with mathematical certainty upon unspecified numbers. The invariable method of mathematical induction is to prove that whenever the formula in question holds in any particular instance, it also holds in the next following instance.* Recurring to our example, we must show that if the formula S n — — p — holds for any particular value of n, say n—k, it also holds for the next value of n or k+1. k(k+l) (A) That is, we must show that, whenever S*=-^-s — - holds, then, S k+1 = « +1 f +2) holds also. Proof. By definition, Sk+i—St+k+1. Substituting the. assumed value of St, „ _ k(k+l) . , , 1 _(k+l) (k+2) The proof required above is thus made, but the result is purely hypo- thetical. We pass to actually valid results as follows. (B) Trial has already shown that the formula is true for S t to S e . Since the formula is true for S e , we know, without trial but solely by the proof at (.A), that the formula holds for S 7 . since it is true for S 7 , we know similarly without trial, that it is true for S 8 . Similarly we know that the formula is true for S 9 , for Si , and so on to any S n whatever. The success of the proof hinges upon three things: 1. The ability to express any instance in terms of the next preceding, even when the latter is not specified. •The application of the method presupposes that the cases to be considered have in some way been arranged in a definite order and numbered consecutively, and that after each case follows another. 148 2. The ability to make the proof (A) without specifying the particular instance that is being considered. 3. The power of the mind to see with certainty that repetition of the steps at (B) would lead to any given n, without actually going through all these steps. These three things are but various phases of the mind's power of op- erating with certainty upon unspecified numbers. In any proof by mathematical induction, the following two parts must unfailingly be present: 1). The proof that if the statement holds in any particular instance, it also holds in the next, and 2) . The proof that the statement actually holds in the first instance (that is, in some particular case). These two proofs are quite independent and may therefore be made in either order, but the relation to true induction is most apparent when the formula to be proved is actually discovered by true induction (as in the ex- ample above), thus amply making the second proof at the outset. Beginners are prone to regard one or the other of these proofs as suf- ficient in itself. The need of both may be made clear by non-mathematical illustrations and by mathematical examples. As a non-mathematical illustration we may consider a row of bricks so arranged that whenever any brick is knocked over, it will in its fall knock over its neighbor on the right. But this is only potential. In order actually to knock over the whole row, it is necessary and sufficient actually to knock over the first brick. If this cannot be done the whole row cannot be knocked over. A second illustration is that of a ladder.* "We must have a ladder by which to climb from any round (the kth) to the next round (the fc+lst) ; but the ladder must rest on a solid basis so that we can get on to the ladder (the k=l or k =2 rounds)." Mathematical examples can also be given in which one of the parts can be proved but not the other, and hence the statement in question is no* proved. 1. Consider the series, 1.1!, 2.2!, 3.3!, .... It is readily proved that if the sum of the first k terms is (A;+l) !, then the sum of the first A;+l terms is (k+1+1) ! Or, denoting the sum of the first n terms of any series by S n , if, for this series, the formula S n =(n+1)\ holds for any particular value of n, it also holds for the next following value of n. But there is no value of n for which it can be proved to hold, and therefore the formula is not proved. (If it could be proved for any partic- *Dickson, College Algebra, p. 100. 149 ular value of n after the first, the formula would of course be proved from that value of n on.) 2. Considering the series, 18 5 7 9 -M ¥> A, S, TIT* •••• it can be proved that if the formula 2w+3 S»=l- 2»-i holds for any particular value of k, it also holds for &+1. But no value k can be found for which the formula holds and hence it is not proved. On the other hand it may be possible to verify a certain statement in many consecutive instances, without leading to the conclusion that it is true in every instance. 1. The expression, l—2» +a +2.3» +1 -4 n+1 +5" is zero for n=0, 1, 2, 3, but not zero for n=L 2. (4»-6.8»+H.2"-14)[l- (-1)"] is zero for n=0, 1, ..., 6, but not zero for n—7. 3. n*+n+ll is prime for n~ 0, 1, 2, ..., 16, but not for n— 17. 4. 2n 9 +29 is prime for n=0, 1, 2, ..., 28, but not for n=29. 5. n* — n+41 is prime for n~ 0, 1, 2, ..., 40, but not for n=41. 6. The theorem that if an odd prime be increased by 3, the result is the product of an odd prime and a power of two, holds for the odd primes to 43, but does not hold for 47. III. Exercises. In the exercises that follow, a formula for S n is to be proved, unless otherwise specified. The finding of the formula by true induction is one of the most fascinating activities, and offers, in proportion to the difficulty of the task, more or less opportunity for the application of mathematical abil- ity and the enjoyment of mathematical inspiration. Not to rob the reader of the possibility of the pleasures, the answers are not as a rule given with the exercises, but are collected at the end. The exercises are not arranged in order of difficulty. This will natur- ally vary with different minds. Of those whose answers are reserved, the following are among the easiest, arranged somewhat in order of supposed difficulty: 21, 10, 13, 1, 32, 23, 12, 11, 4, 9. The degree of difficulty of the exercises may be diminished by giving a part of the result. Thus, No. 3 becomes very easy if it is given that 4w 8 +6n— 1 is a factor of the result, and No. 7 becomes moderately easy if it is given that 2n+l is a factor of the result. 150 In each of the following the sum of the series is to be found by math- ematical induction. (1) 1.2, 2.3, 3.4, ... (5) l 8 , 2 8 , 3 2 , ... (2) 1.2, 3.4, 5.6, ... (6) l 2 , 3 8 , 5 s , ... (3) 1.3, 3.5, 5.7, ... (7) 2 8 , 4 s , 6 8 , ... (4) 2.3, 4.6, 6.8, ... (8) 4% V, 10 8 , 13 8 , ... (9) 0, 2.3, 3.8, 4.15 k{k*-\), ... (10) I 3 , 2 3 , 3 3 , ... (11) I 8 , 3 3 , 5 s , ... (12) 2 8 , 4 s , 6 3 , ... (13) 2.3.4, 3.4.5, 4.5.6, ... (14) 1.3.5, 3.5.7, 5.7.9, ... (15) 1.1 s , 2.3 2 , 3.5 s , 4.7 8 , ... (16) 1.2 s , 2.3 2 , 3.4 8 , 4.5 2 , ... (17) 1 4 10 20 *(*+«(*+» (18) I 4 , 2*, 3*, 4 4 , 5 4 , ... (19) 1.2.3.4, 2.3.4.5, 3.4.5.6, ... (20) 1 , ^ oq k(k+l)(k+2)(k+3) A, O, LO, OO, ..., .j , ... (21) Ill 1.2' 2.3' 3.4' - (22) 111 1.3' 2.4' 3.5' "• (23) 111 3.5' 5.7' 7.9' ■•• (24) 111 1.2.3' 2.3.4' 3.4.5' *" (25) 13 5 1.2.3' 2.3.4' 3.4.5' "* (26) 12 3 2.3.4' 3.4.5' 4.5.6' *" (27) 111 1.3.5' 3.5.7' 5.7.9' "* (28) 12 3 2.5.8' 5.8.11' 8.11.14' "' (29) 111 1.2.3.4' 2.3.4.5' 3.4.5.6' "' (30) l 5 , 2 6 , 3 5 , 4 5 , ... (31) I 6 , 2 8 , 3 6 , 4 6 ,...* (32) 1, 2.2, 3.2*, 42 3 , ... (33) 1, 2.3, 3.3 3 , 4.3 3 , ... •On the series 1», 2", 8", ... see Chrystal's Alpha. Vol. I. p. 486. 151 (34) 1, 2.5, 3.5 2 , 4.5 3 , ... (35) 1, 3.2, 5.2% 7.2 8 , ... (36) 1, 4.3, 7.3 s , 10.3 8 , ... (37) 1, 5.4, 9.4 s , 13.4 s , ... (38) 1, 4.2, 9.2 2 , 16.2 8 , ... (39) 1, 4.3, 9.3 2 , 16.3 s , ... (40) 1, 8.2, 27.2 2 , 64.2 8 , ... (41) 1, 3.2, 6.2 s , 10.2 8 , ..., M^+l) 2 fc -S ... (AO\ i 1 i J (43) a, 2(a+l), 3(a+2), 4(a+3), ... Show that: (44) 2.6.10.14,..., (4w-6)(4n-2)=(%+l)(%-2) (2n-l)2n. (45) n(n+l)(n+2), ..., (2n- 2) =1.3.5.7, ..., (2«-3).2«- 1 . (46) (1+*) (1+a; 2 ) (1+x*) (l+a 8 )... (l+x 2 ")=l+a;+a; !! +...+a; 8B+1 - 1 (47) Show that x tn — y 2n is divisible by x+y. (48) Show that n y 3 - n is divisible by 13, for every positive integer n. (49) If p is a prime number, show that n p ~n is divisible by p for every positive integer n. (50) Show that 2.7"+3.5"-5 is divisible by 24 for every positive in- teger n. Suggestion: Assume, 1) 2.7*+3.5*— 5=multiple of 24. To show, 2.7* +1 +3.5 fc+1 =-multiple of 24. Multiply 1) by 7, 2.7* +1 +3.5*.7-5.7=multiple of 24. Hence, 2.7 fc+1 +3.5 fc+1 -5-30+3.5.2*=multiple of 24. To prove the last assertion, we must show that 6.5*— 30— multiple of 24, which is easily done. (51) Show that 3.5 2m+1 +2 3 ' l + 1 is divisible by 17 for every positive in- teger n. (52) If % is a positive integer, show that (a+b) n =a n +na n ~ 1 b+ y B M i . + ,,, + n(n-l)M...M+l) tfHlftt+||| (53) If all the positive integers of n and fewer digits be written, show that the number of times any digit (other than zero) occurs is n.10" -1 . (54) If the positive integers are grouped as follows: [(1, 2), (3)]; [(4, 5, 6), (7, 8)]; [(9, 10, 11, 12), (13, 14, 15)]; ... and these groups taken in pairs as indicated, prove that the sum of the numbers in the two groups of any pair is the same. (55) 2 (a+kby=n[a 2 +ab(n+l)+^-(2n 2 +Sn+l)]. fc— i b (56) ^^=1.3.5... (2n-l). 152 (57) Letting t* denote the Mi term of a series, show that, if fc-fc(*+l)...(fc+ff-2), &= »i g+l)--(»+g-l) . (58) If «*= A .( A . +1 ) ### ( A . +P ). &=y [yi - (»+i)...(»+p) J • (59) Assuming that the formulas, sm(x±y)— sine cosy ± cosa: siny, cos(*±j/)==coso3 cosy± since siny, have been proved for all acute angles x, y, prove that they hold for all posi- angles x, y. (In this proof, the quadrants are to be regarded as numbered consecutively, 5, 6, 7, 8, etc., as the angle increases beyond 360°, and the formulas of the type sin(90+a;)=cosa;, are to be accepted as proved for every angle*.) (60) (cosa+isina)"=cosna+'tsinna. DeMoivre's formula. Sum the following: (61) sina, sin2a, sin3a, ... (62) sina, sin3a, sin5a, ... (63) cosa, cos2a, cos3a, ... (64) cosa, cos3a, cos5a, ... IV. Answers. m n(n+l) (n+2) / 9 s n(n+l)(4n+l) (I) - 3 . W 3 , v n(4n a +6n-l) M v 4n(n+ l) (n+2) W 3 " 3 /K v n(n+l)(2n+l ) , ft v n(2n-l) (2n+l) (5) g . (6) g . ,~ 2n (n+l) ( 2n+l) , fi v n(6n 2 +15n+U) (7) 3 . (8) g • (9) (n-l)n(n+l)(n+2) j (1Q) [" n(n+l) 1» (II) n 8 (2n 2 -l). (12) 2n 2 (n+l) s . (13) (»+D(»+2)(»+8) . (14) % (2n3+8n'+7n-2). MK v tt (n+l) ( 6n a -2n -l) /1fi v nfn+1) (n+2) (3n+5) (lb) g . lib; ^ . , 17 * (n+3) ! , 1a * n(n+l)(6n 3 +9n 2 +n-l) (17) 4!(n-l)r (18) 30 ' (19) n(n+l)(n+2)(n+3)(n+4) > (2Q) (n+4)! 5!(n-l)!" (21) -5-,. (22) _»G»+B)_ n+1* v ' 4(n+l)(n-t-2)* <»> 3W3)' < 24 > *[* (n+1) (n+2). 153 (25) (27) (29) (31) (32) (34) (36) (38) (40) (42) (61) (63) n(3n+l) 4(n+l) (n+2) ' n(n+2) 3(2n+l) (2n+3)" 3L3! (n+1) (n+2) (n+3) n(n+l) (2»+l) (3n*+6n 3 - (26) (28) ]. (30) -3n+l) n(n+l) 6.7 (n-l)2»+l. (4n-l)5"+l 16 (6n-7)3"+7 4 (n 2 -2n+3)2*-3. [(n-l) 8 -6(n-2)]2»+13. 3 re+1 -(n 8 +3n+3) 2.3"- 1 . »a . (n+l)a sin-g- sin- — nf— sin sin-g- cos a 2 (n+1) a 2 (33) (35) (37) (39) (41) (43) (62) (64) 4(n+2) (n+3) ' w(n+l) 4(3n+2) (3n+5)' n 2 (n+l)*(2n*+2n-l) 3.4 (2n-l)3"+l 4 (2n-3)2"+3. (12n-13)4"+13 9 (n a -n+l)3 re -l 2 2»- 1 (n 4 -n+2)-l. n(n+l) (3a+2n-2) sin ; «ffi sina sm- sin2na 2sina ' ON THE GENERAL TANGENT TO PLANE CURVES.* By PROF. R. D. CARMICHAEL, Anniston, Alabama. The object of this note is to work out without the Calculus a certain well known formula for a tangent to a plane algebraic curve at an ordinary (not a singular) point, and especially to show how this result is easily ex- tended to the loci of transcendental equations. The formula found is read- ily developed by aid of the Differential Calculus, but is here found by other means. It might therefore be used in a course which does not presuppose the Calculus. Let us take, in rectangular Cartesian coordinates, the general equa- tion of a proper nth degree locus in the form *Read before the Chicago Section of the American Mathematical Society, April 18, 1908,