Skip to main content

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,