CHAPTER XIII. MISCELLANEOUS THEOREMS AND EXAMPLES. 145. Mathematical Induction. A method of proof, ordinarily called mathematical induction, is frequently employed in the demonstration of mathematical propositions. The method is best explained through its application to simple examples. Ex. 1. The following equations are evidently true: 1+ 3 = 422, 1+ 3 + 5 = 9 = 32, 1 + 3 + 5 + 7 = 16 = 42, 1 + 3 + 5 + 7 + 9 = 25 = 52; and they at once suggest that perhaps the sum of the first n odd numbers is equal to n2. Let us assume provisionally that it is. This hypothesis algebraically expressed is in which n is an integer and equal to the number of terms in the sum. To both sides of this equation add 2 n + 1. The result of the addition is and shows that if the sum of the first n odd numbers is n2, then the sum of the first n + 1 odd numbers is (n + 1)2. But the formula above written is obviously true when n = 1 and when n = = 2; hence it is true when n = 3. And being true when n = 3, it is true when n = 4, and so on indefinitely. It is therefore true when n is any integer whatever. Thus the proposition that the sum of the first n odd integers is equal to n2 is proved. Ex. 2. Let it be proposed to find the sum of the first ʼn natural numbers. We begin by writing down the following equations, which are evidently true: 1 + 2 + 3 + 4 + 5 = 15 = ≥ · 5 (5 + 1). They at once suggest that perhaps the sum of the first n integers is in (n + 1). We accordingly assume, provisionally, that 1+ 2+ 3+ 4+ • + n = 1 n (n + 1). Adding n + 1 to both sides of this hypothetical equation, we obtain 1+2+3+ + n + n + 1 = } n2 + } n + n + 1 a result which shows that if n (n + 1) is the sum of the first n integers, then (n + 1)(n+2) is the sum of the first n + 1 integers. But the formula is obviously true when n = 1; hence it is true when n = 2. And being true when n = 2, it is true when n=3, and so on indefinitely. It is therefore true, whatever integer n may represent. These examples may suffice to explain a method of proof that will be made use of, as occasion requires, in subsequent pages of this book. If its logical rigor be not at first entirely evident to the student, a careful study of its applications in a few examples that require its use should remove the doubt. Ex. 3. Prove that the sum of the first n even integers is n(n+1). Ex. 4. Prove that the sum of the squares of the first n integers is } n (n + 1) (2 n + 1). Ex. 5. Prove that 1.2+2.3+3.4+ ... + n (n + 1) = }} n (n + 1) (n + 2). 146. The term induction does not correctly describe the above method of proof. In the natural sciences the true method of induction is used for the purpose of inferring the universality of natural laws from particular manifestations of their truth in natural phenomena. It does not seek to attain absolute certainty, but achieves its object as soon as it establishes a high degree of probability. The so-called method of mathematical induction, however, is as logically rigorous as any other process in mathematics. It is more correctly described as reasoning by progressive transformations, in which the uniqueness of an algebraic form persists, monomorphic transformations, or monomorphosis. 147. Theorem. The expression xn xa for all positive integral values of n. It is known that x α, x2 — a2, and æ3 ble by x-a. a" is divisible by a3 are all divisi = x2−1 (x − a) + a (xn−1 — an−1). Now, if x - a divides n-1 - an-1, it will also divide Hence, if x - a divides a―1 — a”-1, it will also divide xn-an. But we know that a a divides a3 - as; it will therefore also divide at at. And, since x a divides a1 — a1, it will also divide a3. And so on indefinitely. x Hence "a" is divisible by x tive integer [Art. 145]. -a, when n is any posi Since "+a" = x” — a” +2a”, it follows that when 2"+a" is divided by x a the remainder is 2a", so that "a" is never divisible by x -a. If we change a into ―a, x-a becomes x-(-a)=x+a; also "a" becomes a"-(-a)"; and x" — (− a)" is x+a" or " a" according as n is odd or even. Hence, when n is odd, We have in the above shown that the four cases are all included in the first: we leave it as an exercise for the student to prove each case separately. The above results may be written so as to show the quotients: thus M the upper or lower signs being taken on each side of the second formula according as n is odd or even. 7. Find the factors of x2 - 2xy - 8 y2 − 2 x + 20 y − 8. 8. Find the factors of a2 - b2 + c2 — ƒ2 −2 ac - 2 bf. 9. Write down the quotient in each of the following divisions: (i.) (x3 — y3) ÷ (x − y), (ii.) (x2 + y2) ÷ (x + y), 10. Show that, if n is any positive integer, 7" — 1 is divisible by 6; show also that 352n+1 + 1 is divisible by 36. 11. Show without actual division that (3 x2 − 2 x + 1)3 − (2 x2 + 3 x − 5)3 is divisible by x2-5x+6. 12. Write down the result of dividing (2a + 3b)3 + (3 a +2b)3 by 5 a + 5b. 13. Write down the result of dividing (2a + 4b - 4 c) 3 + ( a − b + 7 c)3 by a + b + c. 14. Show that (1 − x)2 is a factor of 1 − x x + x6. |