CHAPTER XI. MATHEMATICAL INDUCTION 125. General statement. Many theorems are capable of direct and simple proof in special cases, while for the general case a direct proof is difficult and complicated. 1, it is easy to - If we ask whether "-1 is divisible by x make the actual division for any particular value of n, as n = 2 or n = 3. But if x3 1 is shown divisible by x - 1, we are no wiser than before concerning the divisibility of x 1. Suppose, however, we can prove that the divisibility for n= m + 1 follows from that for n = m, whatever value m may have. we have established the fact by direct division for n be assured of the divisibility for n = 4, then for n = is identically true. If x = х (xm = Then since = 3, we may 5, and so on. -1 for a given value of m, it is a factor of the right-hand member and consequently a factor of the left-hand member (§ 69), which was to be proved. Thus the divisibility of xm 1 by x - 1 is established for any integral value of n greater than the one for which the division has actually been carried out. To complete the proof of a theorem by mathematical induction we must make two distinct steps. First. Establish the theorem for some particular case or cases, preferably for n = 1 and n = 2. Second. Show that the theorem for n = m +1 follows from its assumed validity for n = m. EXAMPLE. Prove that the sum of the cubes of the integers from 1 to n is To prove that 18 + 28 +33 + ··· + n3 = { } [n (n + 1)]}2. First. This theorem is true for n = 1. For 13 = 1 = {} [1 (2)]}2 = 12 = 1. The theorem is also true for n = For 18+28 = = 2. 9= · } } [2 (2 + 1)] }2 = (} · 6)2 = 32 = 9. Second. Assume the theorem for n = 23 m,* 13 + 28 + ... + m3 = { } [ m (m + 1)]}2. Add (m + 1) to both sides of the equation, 13 +23+ + m3 + (m + 1)3 = { } [m (m + 1)]}2 + (m + 1)3 which is the form desired, i.e. m + 1 replaces m in the formula. 8. x2n y2n 9. 1.2+2 . + . 4+4.5+ + n ⋅ (n + 1) = } n (n + 1) (n + 2). 10. 1.1+2 · 32 + 3 · 52 + + n (2 n − 1)2 = } n (n + 1) (6 n2 — 2 n − 1). 11. 1.2.3+2.3.4+3.4.5+ 12. (13+23+ 33 + ... •+n(n+1)(n+2) = ¦ n(n + 1)(n+2)(n+3). + n3) + 3 (15+ 25 + 35 + + n5) = 4 (1 + 2 + 3 + + n)3. * This statement does not imply that we assume the validity of the formula for any values for which it has not yet been established, but only for values of m not greater than 2. 18. A pyramid of shot stands on a triangular base having m shot on a side. How many shot are in the pile? CHAPTER XII BINOMIAL THEOREM 126. Statement of the binomial theorem. When in previous problems any power of a binomial has been required we have obtained the result by direct multiplication. We can, however, deduce a general law known as the binomial theorem, which gives the form of development of (a + b)", where n is any positive integer and a and b are any algebraical or arithmetical expressions. This law is as follows: From this expression we deduce the following RULE FOR THE DEVELOPMENT OF (a + b)". To obtain any term from the preceding term, decrease the exponent of a in the preceding term by 1 and increase the exponent of b by 1 for the new exponents. Multiply the coefficient of the preceding term by the exponent of a, and divide it by the exponent of b increased by 1 for the new coefficient. REMARK. In practice it is usually more convenient first to write down all the terms with their proper exponents, and then form the successive coefficients. EXERCISES Verify by multiplication the rule given for the following: 127. Proof of the binomial theorem. We have already stated and have seen that it is justified for every particular case that we have tested. By complete induction we now prove this theorem when n is a positive integer. First. Let n = 2. That is, (a + b)2 = a2 + 2 ab + b2. This expression evidently obeys the law as stated in (1). This expression is identical with (2) except that (m +1) replaces m. Hence the theorem is established so far as the first three terms are concerned. 128. General term. Though we have stated the binomial theorem for a general value of n, we have only established the exact form of the first three terms. Let (a + b)" = a" + c1a”−1b + c2an− 272 + 1 .... We note that the sum of the exponents of a and b is n in any term of the development of (a + b)". Also the exponent of b in the (1)st term is 7. |