คณิตศาสตร์พื้นฐาน1

200 Chapter 7 Number of cases and sequence of numbers 1 3 Combination When choosing r out of n different choices and putting them in a group, it is called combination of r from n choices and denoted as nCr. For example, when choosing three letters out of five letters a, b, c, d, and e, the total number of possible combinations is denoted as 5C3. Let’s find the value of possible combinations 5C3. When choosing three letters out of five letters, the total number of permutations is 5P3. The permutations of letter a, b, and c, for example, abc acb bac bca cab cba These are all the same from the combination point of view. For each of the combinations, there are P3 3 = 3! permutations. Thus, C5 3 × 3! = P5 3 Therefore, C5 3 = P5 3 = 5·4·3 = 10 3! 3·2·1 abc abd abe acd ace ade bcd bce bde cde acb adb aeb adc aec aed bdc bec bed ced bac bad bae cad cae dae cbd cbe dbe dce bca bda bea cda cea dea cdb ceb deb dec cab dab eab dac eac ead dbc ebc ebd ecd cba dba eba dca eca eda dcb ecb edb edc In general, the following formula is established.  Formula of combination  Cn r = Pn r = n(n − 1) (n − r + 1) = n! r! r! (n − r)! r!   Define as Cn 0 = 1, so that the formula above is established, when r = 0. Ex.4 C8 3 = 8! = 8·7·6 = 56 C8 5 = 8! = 56 5! 3! 3·2·1 3! 5!

§ 1 Number of cases 201 Q. Find the following values. (1) C6 3 (2) C10 2 (3) C7 5 (4) Cn 1 (5) Cn n Q. Prove the equality Cn r = C .n n−r Exercise When choosing three numbers from the natural numbers 1 to 10, answer the following questions. (1) Find the total number of possible combinations. (2) How many cases are there in which the products of three numbers are divisible by 3 ? Solution (1) Find the total number of possible combinations, when choosing 3 out of 10 numbers. C10 3 = 10! = 10 · 9 · 8 = 120 7! 3! 3·2·1 (2) When none of the three numbers are divisible by 3, the product can’t be divisible by 3. Since there are 7 numbers that are not divisible by 3. C7 3 = 7! = 7·6·5 = 35 4! 3! 3·2·1 Therefore, the number of cases that we are looking for is 120 − 35 = 85 (cases) // Q. There are twelve boys and eight girls. How many different teams can be formed with three boys and two girls in a team? Q. There are six points on the circumference C B of a circle. A How many segments can be drawn connecting F these points ? D How many triangles, which have those points as their vertexes, can be made ? E

202 Chapter 7 Number of cases and sequence of numbers Exercise Prove the following equality C = C + Cn r n−1 r n−1 r−1 Proof Let a specific one out of n choices be a. When selecting r out of n choices, you can think about two possible ways. ( i ) When selecting, excluding a. Which means selecting r from (n − 1), excluding a. Cn−1 r (possible selections) (ii) When selecting, including a. Which means it is same as selecting (r−1) from (n − 1), excluding a. Cn−1 r−1 (possible selections) Therefore, the total number of possible ways to select r out of n choices is, from the sum rule, C + Cn−1 r n−1 r−1 ∴ C = C + Cn r // n−1 r n−1 r−1 Q. Prove the following equalities. (1) C10 4 = C8 2 + 28C3 + C8 4 (2) C10 4 = C7 1 + 37C2 + 37C3 + C7 4 1 4 Various permutations Let’s look into a permutation with identical items. Let’s find how many different ways there are to arrange seven letters a, a, b, b, b, c, c, in a line. When choosing the positions for letter a out of seven possible positions, there are C7 2 possible positions. aa For each of them, there are five remaining positions for letter b, so that there are C5 3 possible positions. ba bab

§ 1 Number of cases 203 Furthermore, there are two positions left for letter c, so that there are C2 2 possible positions. bacbabc Therefore, the total number of different ways that we are looking for is C7 2 × C5 3 × C2 2 = 7! × 5! × 2! = 7! = 210 5! 2! 3! 2! 2! 0! 2!3! 2! In general, the following formula is established.  Formula of permutation with identical items  When p items, another q items,another r items, are identical re- spectively out of n items, the total number of different ways to arrange n items in a line is n! (Note : n = p + q + r + ) p! q! r!   Ex.5 The method of dividing six students into three groups (A, B, C) of two is same as the method of placing Group A, A, B and Group B, C, C in a line. 6! = 90 (different ways) 2! 2! 2! Q. How many eight-digit integers can be formed with eight numbers 1, 1, 1, 1, 2, 2, 3, 3 ? Q. When placing three red balls, two white balls and two blue balls in a line. How many different arrangements can be made ? How many arrangements can be made when two white balls are placed next to each other ? Let’s find how many different arrangements can be formed, when five letters a, b, c, d and e are placed on the circumference of a circle. When five letters are placed in a line, the total number of permutations is P5 5 = 5!. However, the permutations of letters, shown below, are the same arrange-

204 Chapter 7 Number of cases and sequence of numbers ments when placed on the circumference of a circle. abcde bcdea cdeab deabc eabcd Thus, they are considered as one. a b c d e eb ac bd ce da dc ed ae ba cb Since there are five permutations of letters that are considered as the same when placed on the circumference of a circle, the number of possible arrange- ments is 5! = 4! = 24. 5 Note This type of permutation is called circular permutation. The total number of circular permutations with n different items can be found by n! = (n − 1)!. n Exercise Two adults and four children hold hands to make a circle. Answer the following questions. (1) How many possible arrangements are there to line them up? (2) How many possible arrangements are there when two adults are next to each other? Solution (1) Since these are circular permutations with six people. (6 − 1)! = 5! = 120 (possible arrangements) (2) Suppose two adults as one, the number of circular permutations with five people is 4!. As for the two adults, there are 2! possible ways to be lined up. 4! × 2! = 48 (possible arrangements) // Q. Four boys sit in a circle. Answer the following questions. (1) How many possible ways are there to line them up? (2) If four girls joined, how many possible ways are there for boys and girls to sit alternately?

§ 1 Number of cases 205 1 5 Binominal theorem When think about the expansion of the right side of following formula, (a + b)4 = (a + b)(a + b)(a + b)(a + b) five terms appear. a4, a3b, a2b2, ab3, b4 Let’s check how many times each term appear. The term a4 and b4 appear only once. The term a3b (as shown below) is obtained by taking b from a bracket and multiplying three a from the other three brackets on the right side of formula. b × a × a × a, a × b × a × a, a × a × b × a, a × a × a × b Thus, it appears C4 1 = 4 times. Likewise, the term a2b2 appears C4 2 = 6 times, the term ab3 appears C4 3 = 4 times. Therefore, (a + b)4 = a4 + 4C1a3b + 4C2a2b2 + 4C3ab3 + b4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 In general, for the expansion of (a + b)n, the coefficient of term a bn−r r is Cn r and the following equality is established. This is called binominal theorem.  Binominal theorem  (a + b)n = n C0 an + n C1 an−1 b + C a bn−2 2 + + C abn n−1n−1 + n Cn bn n2   The coefficient Cn r (r = 0, 1, , n) of the expansion of (a + b)n is called binominal coefficient. When binominal coefficients are lined up as shown in the figure in the next page, you will see the sum of two numbers on the first row becomes the number of second row. This can be observed from the equality of Exercise 5. C = C + Cn r n−1 r n−1 r−1 This relationship is shown in the figure in the next page. This figure is called Pascal s triangle.

206 Chapter 7 Number of cases and sequence of numbers n=0 1 n=1 1 1 n−1Cr−1 n−1Cr n=2 121 n Cr n=3 1331 n=4 14641 n=5 1 5 10 10 5 1 ... ... Ex.6 (a − 2)4 = a4 + 4C1a3(−2) + 4C2a2(−2)2 + 4C3a(−2)3 + (−2)4 = a4 − 8a3 + 24a2 − 32a + 16 Q. Expand the following equations. (1) (a + 1)7 (2) (a + 2b)4 (3) (x − 1)6 Exercise Solve the following. (1) Find the coefficient of x4y3 in the expansion of (2x + y)7. (2) ( 1 )9 Find the coefficient of x in the expansion of x + . x Solution (1) From the binominal theorem, the terms of the expansion are 7−r r 7 Cr (2x)7−r y r = 2 C x y7−r 7r When r = 3, it is x y7−r r = x4y3 Thus, the coefficient of x4y3 is 247C3 = 560 (2) The terms of the expansion are ( )r 1 C x9−r x = C x9−2r 9r 9r When 9 − 2r = 1, where r = 4, it is x9−2r = x Thus, the coefficient of x is C9 4 = 126 // Q. Find the coefficients of x5y3 in the expansion of (x )8 − 6y . 2

§ 1 Number of cases 207 Chapter 7 Column Probabilities and Combinations The earliest records on combinations date back to B.C. era. In the study of probability theory that began in the 17th century, combinations have received great attention as a powerful tool of counting all possible cases of an event. Through many studies by mathematicians, combinations developed into an independent branch of mathematics (combination theory) in the 20th century. As we learned in junior high school, when performing experiments or making observations, if there are n equally likely possible ways, of which m ways can happen, then the probability of occurrence of the event is represented by, P = m = the number of cases that can happen n the total number of all possible cases The formula may sounds easy at first glance. However counting the number of cases often takes a lot of work. In such a case, permutations and combi- nations formulas can play important roles and these enable us to calculate probabilities. Let’s take an example. If three students are to be chosen by drawing lots out of forty students in a class, what is the probability of student A being chosen? First, the all possible cases have C40 3 = 9880 ways. In this case, when A is chosen, the remaining two students are to be chosen out of thirty-nine students excluding A, that means, C39 2 = 741 ways. Therefore, the probability of student A being chosen is, P = C39 2 = 741 = 3 C40 3 9880 40 Then, what if there are twenty-four male students and sixteen female stu- dents in the class, of which three students are to be chosen. what is the probability of two male students and one female student to be chosen for those three? The probability is given as follows. P = C · C24 2 16 1 = 4416 = 552 C40 3 9880 1235

208 Chapter 7 Number of cases and sequence of numbers Exercises 1–A 1. There are five routes between point A and point B and there are four routes between point B and point C. How many possible ways are there to travel from A to C and come back to A without passing through the same route? 2. When two dice are thrown (big and small), how many possible arrangements are there in which the sums of the dice are multiples of 5. 3. Form four-digit integers using eight integers 0, 1, 2, 3, 4, 5, 6 and 7. Answer the following questions. (1) How many different arrangements can be formed using four different inte- gers? (2) How many different arrangements can be formed when the integers can be used more than once? 4. Simplify the following formulas. (1) n! (2) (n + 1)! (3) (n − r + 1)! (n + 1)! (n − 1)! (n − r − 1)! 5. There are eight different color balls and three different size boxes. How many possible arrangements are there for the balls to be stored in the boxes ? (Note: a box may have no balls in) 6. The figure on the right shows a set of seven parallel lines intersecting with an- other set of six parallel lines. How many parallelograms are there in the figure ? 7. When number 1, 2 and 3 are arranged with repetition to form six-digit inte- gers, how many integers containing three of the digit 1? 8. Form six-digit number using all six numbers 3, 3, 3, 4, 4 and 5. Answer the following questions. (1) How many can be formed ? (2) How many even integers can be formed? 9. ( 1 )6 Find the coefficients of the following terms in the expansion of 2x − . x (1) x4 (2) 1 (3) constant term x2

§ 1 Number of cases 209 Exercises 1–B 1. Five boys and three girls sit around a circular table. Answer the following questions. (1) How many sitting arrangements are there ? (2) How many arrangements are there when three girls sit next to each other ? (3) How many arrangements are there when none of the girls sit next to each other ? A 2. The figure on the right is a map of town that has five roads running north to south and four roads running east to west. C Answer the following questions. B (1) How many possibilities are there to travel from point A to point B using the shortest route ? (2) Among the possible routes above, how many of them don t go through point C ? 3. Choose three vertexes of a regular octagon to form the triangles. Answer the following questions. (1) How many triangles can be formed all together ? (2) How many triangles share two sides with the regular octagon ? (3) How many triangles share one side with the regular octagon ? (4) How many triangles don t share sides with the regular octagon ? 4. Form seven-digit numbers using all seven numbers 0, 1, 1, 1, 2, 2, 3. Answer the following questions. (1) How many arrangements can be formed? (2) How many even integers can be formed? 5. Prove the following equality by applying binominal theorem to (1 + x)n. Cn 0 + Cn 1 + Cn 2 + + Cn n = 2n 6. Find the coefficients of the following terms in the expansion of (x2+x+1)5. (1) x9 (2) x7 (3) x5

210 Chapter 7 Number of cases and sequence of numbers § 2 Sequence of numbers 2 1 Sequence of numbers Line up the positive even numbers from 2 to 100 in order. 2, 4, 6, 8, 10, , 100 (1) Line up the positive even numbers from 2 to 100 in order. 1, 4, 9, 16, 25, (2) In such a way, the line of numbers in accordance with a certain rule is called sequence of numbers. Each number is called term, and from the beginning, they are called initial term (first term), second term respectively. In addition, a term n-th from the first term is called n-th term. If it is the last number in the sequence, it is called last term and the total number of terms is called term number. For (1), the last term is 100 and the term number is 50. When representing a general number sequence, the first a1, second a2, third a3, and n-th terms an are written as, a1, a2, a3, , an, The number sequence can also be represented as {an}. The n-th terms of the number sequence (1) and (2) are 2n and n2 respec- tively. In such a way, the n-th term represented by a formula of n, is called a general term of number sequence and represented as {2n} and {n2} for (1) and (2). Q. Find the first five terms of number sequences, where the general terms are expressed with the bfnol=low(i−ng21fo)rnmulas. (3) cn = 1 (1) an = 3n − 1 (2) n(n + 1) Q. When the general term is an = (−1)n−1, solve the following. (1) Find the first six terms of the sequence {an}. (2) Find the first six terms of the sequence {bn}, when bn = an + 1 . 2

§ 2 Sequence of numbers 211 2 2 Arithmetical progression The number sequence, shown below, is obtained by adding a fixed value 4 successively to the first term 3. 3, 7, 11, 15, 19, (1) In such a way, a sequence begins with a certain number a and progresses by adding a fixed value d successively is called arithmetical progression and the fixed value d is called common difference. a, a + d, a + 2d, a + 3d, a + 4d, The n-th term of arithmetical progression is obtained by adding common difference d to the first term a for (n 1) times. Therefore, the following formula is established.  General term of arithmetical progression  The general term of arithmetical progression with first term a and com- mon difference d is an = a + (n − 1)d   Ex.1 Since a = 3 and d = 4 in the sequence (1), the general term is an = 3 + (n − 1)4 = 4n − 1 Q. Fill in the below with appropriate numbers to form the arith- metical progressions. (1) 2, , 10, , (2) , 5, , , 4 Q. There is an arithmetical progression with first term 32 and common difference −3. Answer the following. (1) Find the general term. (2) Find the 10-th term. (3) Find the term number for −22. (4) In which term does the value be negative for the first time ? Let’s find the sum from the first to n-th term of arithmetical progression {an}, where the first term a and common difference d. Sn = a1 + a2 + a3 + + an−1 + an By putting the sums of the right side in reverse order, Sn = an + an−1 + + a3 + a2 + a1 By combining the two formulas above and putting two terms in each bracket, 2Sn = (a1 + an) + (a2 + an−1) + + (an + a1)

212 Chapter 7 Number of cases and sequence of numbers Here a1 + an = a + {a + (n − 1)d} = 2a + (n − 1)d a2 + an−1 = (a + d) + {a + (n − 2)d} = 2a + (n − 1)d = a1 + an a3 + an−2 = (a + 2d) + {a + (n − 2)d} = 2a + (n − 1)d = a1 + an Thus, an + a1 = a1 + an a a + (n − 1)d 2Sn = n(a1 + an) a+d a + (n − 2)d a + 2d a + (n − 3)d n ... From this, a + (n − 3)d a + 2d a + (n − 2)d a+d Sn = n(a1 + an) a + (n − 1)d a 2 And, a1 + an = 2a + (n − 1)d 2a + (n − 1)d Therefore, the following formula is obtained.  Sum of arithmetical progression  Sum Sn from the first to n-th term of arithmetical progression, where the first term a and common difference d. Sn = n(a1 + an) = n{2a + (n − 1)d} 2 2   Exercise Find the sum of all the multiples of 3 between the integers 100 to 200. Solution Since the integers form an arithmetical progression with first term 102, common difference 3, and the last term 198, the term number n will be, 102 3(n − 1) = 198 ∴ n = 33 Thus, the sum that we are looking for is 33(102 + 198) = 4950 // 2 Q. Find the sums of the following arithmetical progressions. (1) −2 + 1 + 4 + + 34 (2) 1 + 3 + 5 + + (2n − 1) (Refer to the figure on the right) Q. Find the value of n, when the sum from the first to the n-th term of arithmetical progression, where the first term 5 and common difference 3, is 55.

§ 2 Sequence of numbers 213 2 3 Geometrical progression The number sequence, shown below, is obtained by multiplying a fixed value 3 sequentially to the first term 2. 2, 6, 18, 54, 162, (1) In such a way, a sequence begins with a certain number a and progresses by multiplying a fixed value r sequentially is called geometrical progression and the fixed value r is called common ratio. a, ar, ar2, ar3, ar4, The n-th term of geometrical progression is obtained by multiplying com- mon ratio r to the first term a for (n 1) times. Therefore, the following formula is established.  General term of geometrical progression  The general term of geometrical progression with first term a  and common ratio r is an = arn−1.  Ex.2 Since a = 2 and r = 3 in the sequence (1), then, an = 2 · 3n−1. Exercise Find the first term and common ratio of geometrical pro- gression, where the second term is 6 and the fourth term is 54. Solution By letting the first term be a and the common ratio be r, ar = 6 ar3 = 54. Thus, r2 = 9 ∴ r = ±3, a = ±2 (double-sign in same order) // Q. Fill in the below with appropriate numbers to form the geo- metrical progressions. (1) 5, , , −40, (2) , 162, , 18, Q. Find the 10th term of geometrical progression, where the first term is −8 and the fourth term is −1.

214 Chapter 7 Number of cases and sequence of numbers Let’s find the sum Sn from the first to n-th term of geometrical progression, where the first term a and common ratio r. When writing Sn and rSn next to each other. Sn= a + ar + ar2 + ar3 + + arn−2 + arn−1 rSn= → ar + ar2 + ar3 + + arn−2 + arn−1 + arn By subtracting both sides, (1 − r)Sn = a − arn Therefore, a(1 − rn) + a = na When r =\\ 1, Sn = 1 − r Sn = a + a + a + Whenr = 1, n Thus, the following formula is obtained.  Sum of geometrical progression   Sn = a(1 − rn) a(rn − 1) (When r =\\ 1) 1−r = r−1 (When r = 1) na  Exercise Find the value of n, when the sum from the first to n-th term of geometrical progression, where the first term 5 and common difference 3, is 1093. Solution By letting the term number we are looking for be n, // 1 × (3n − 1) 3 − 1 = 1093 Thus, 3n = 2187 = 37 ∴ n = 7 Q. Find the sums of the following geometrical progressions. (1) 1 + 2 + 22 + 23 + 24 + + 27 (2) 1− 1 + 1 − 1 + − 1 2 22 23 29 √ (3) 3−1+ √1 − 1 + √1 − (Up to 10-th term) 3 3 33 (4) 2 + 6 + 18 + + 486 Q. Find the values of first term and common ratio of geometrical pro- gression, where the sum of first 3 terms is 6, and first 6 terms is −42.

§ 2 Sequence of numbers 215 2 4 Sum of various sequences of numbers ∑n Sum of sequence a1 + a2 + a3 + + an can also be expressed as ak ∑ k=1 using a symbol (sigma). The symbol represents the sum of all the terms ak, of which are obtained by changing value of k from 1 to n one by one. ∑n ak = a1 + a2 + a3 + + an k=1 ∑7 ∑10 3k−1 = 1 + 3 + 32 + + 39 Ex.3 k = 1 + 2 + 3 + + 7, Q. k=1 k=1 ∑ Express the sums of following sequences without using , and find the sums. (1) Ssumk = 15k2 ∑10 ∑n (2) (2l − 1) (3) 3 · 2m−1 l=1 m=1 Exercise ∑ Express the sums of following sequences using . (1) 2 + 5 + 8 + + 203 (2) 3 + 3 + 3 + 3 + 3 + 3 + 3 Solution (1) Since it is an arithmetical progression with first term 2 and common difference 3, the k-th term is, 2 + 3(k − 1) = 3k − 1 (k = 1, 2, 3, ) By letting the term number be n, 3n − 1 = 203. ∴ n = 68. ∑68 Thus, 2 + 5 + 8 + + 203 = (3k − 1) k=1 (2) For all k, the k-th term is 3 (a constant number) and the term number is 7. ∑7 // Q. 3+3+3+3+3+3+3= 3 k=1 ∑ Express the sums of following sequences using . (1) 101 + 102 + 103 + 104 + 105 + + 200 (2) 1− 1 + 1 − 1 + 1 − 1 + − 1 3 9 27 81 243 2187

216 Chapter 7 Number of cases and sequence of numbers ∑ For the calculation of notation, the following formulas are established. ∑  Properties of symbol  (I) ∑n ∑n ∑n double-sign in same order (ak ± bk) = ak ± bk c is a constant number (II) c is a constant number k=1 k=1 k=1 (III)  ∑n ∑n cak = c ak k=1 k=1 ∑n c = nc k=1  Proof ∑n (ak ± bk) = (a1 ± b1) + (a2 ± b2) + + (an ± bn) k=1 = (a1 + a2 + + an) ± (b1 + b2 + + bn) ∑n ∑n = ak ± bk (double-sign in same order) k=1 k=1 ∑n + can = c(a1 + a2 + ∑n cak = ca1 + ca2 + + an) = c ak k=1 k=1 ∑n // c = c + c + c + + c = nc k=1 n Let’s find the sum of powers of natural numbers. First, the sum of natural numbers from 1 to n is, from the formula of the sum of arithmetical progres- sion, ∑n 1 k = 1+2+3+ 2 +n= n(n + 1) k=1 By applying an identical formula (k + 1)3 − (k − 1)3 = 6k2 + 2. ∑n ∑n {(k + 1)3 − (k − 1)3} = (6k2 + 2) k=1 k=1 By calculating the left side and right side of this formula respectively, ∑n ∑n Left side = (k + 1)3 − (k − 1)3 k=1 k=1 = {23 + 33 + 43 + + (n + 1)3} − {03 + 13 + 23 + + (n − 1)3} = n3 + (n + 1)3 − 1 = 2n3 + 3n2 + 3n

§ 2 Sequence of numbers 217 ∑n ∑n ∑n Right side = 6k2 + 2 = 6 k2 + 2n k=1 k=1 k=1 Therefore, ∑n 2n3 + 3n2 + 3n = 6 k2 + 2n k=1 From this, ∑n 1 (2n3 + 3n2 + n) = 1 n(n + 1)(2n + 1) k2 = 66 k=1 Thus, the following formulas are obtained.  Sum of powers of natural numbers   ∑n 1 n(n + 1), ∑n 1 n(n + 1)(2n + 1) k= 2 k2 = 6  k=1 k=1 Exercise Find the sum Sn from the first to n-th term of the following sequence. 1 · 3, 3 · 5, 5 · 7, Solution The k-th term of this sequence is (2k − 1)(2k + 1) = 4k2 − 1 Thus, ∑n ∑n ∑n Sn = (4k2 − 1) = 4 k2 − 1 k=1 k=1 k=1 = 2 n(n + 1)(2n + 1) − n 3 = 1 n(4n2 + 6n − 1) // 3 Q. Find the sums. + n(n + 2) ∑n (1) k(k + 1) k=1 (2) 1 · 3 + 2 · 4 + 3 · 5 + (3) 12 + 32 + 52 + + (2n − 1)2

218 Chapter 7 Number of cases and sequence of numbers 2 5 Recurrence formula and mathematical induction The rule to define a number sequence can be given by a relational expres- sion between several terms. For example, an arithmetical progression with first term a and common difference d is obtained by adding d to immediately preceding terms except for the first term. Therefore, it can be expressed as, a1 = a, ak+1 = ak + d (k = 1, 2, 3, ) In such a way, a method to define a number sequence from a relational expres- sion between several terms is called recursive definition of number sequence. The relational expression between terms is called recurrence formula of number sequence. Ex.4 The geometrical progression with first term a and common ratio r can be expressed by the following recurrence formula. a1 = a, ak+1 = rak (k = 1, 2, 3, ) Q. Write the recurrence formulas expressing the following number se- quences. (1) A sequence, where the first term is 1 and the terms are found by mul- tiplying the previous terms by 2, then adding 3. (2) A sequence, where the first term is 0 and the terms are found by adding 1 to the previous terms and raising to the second power. Q. Find the first 4 terms of the following number sequence expressed with recurrence formulas. (1) a1 = 1, ak+1 = a2 + 2 (k = 1, 2, 3, ) k (2) b1 = 3, bk+1 = bk + 3k (k = 1, 2, 3, ) Exercise Find the general term of the following number sequence ex- pressed with recurrence formula. a1 = 1, ak+1 = 2ak + 1 (k = 1, 2, 3, ) Solution Find each of the terms using the recurrence formula. a2 = 2a1 + 1 = 2 + 1 a3 = 2a2 + 1 = 2(2 + 1) + 1 = 22 + 2 + 1 a4 = 2a3 + 1 = 2(22 + 2 + 1) + 1 = 23 + 22 + 2 + 1 .................................... From this, an = 1 + 2 + 22 + + 2n−1 = 1 · (2n − 1) = 2n − 1 // 2−1

§ 2 Sequence of numbers 219 Q. Find the general terms of the following sequences expressed with recurrence formulas. (1) a1 = 2, ak+1 = 3ak + 2 (k = 1, 2, 3, ) ) (2) b1 = 4, bk+1 = bk + (2k − 1) (k = 1 2, 3, When a proposition P(n) is given regarding a natural number n, the fol- lowing should be proved in order to verify that the proposition P(n) holds for all natural numbers n. ( i ) P(1) is established. ( ii ) For any natural number k, ” If P(k) is established, P(k + 1) is also established.” Which means, for ( ii ) If P(1) is established, P(2) is also established. If P(2) is established, P(3) is also established. ... Therefore, if ( i ) and ( ii ) are proved, P(1) is established from from ( i ). Then, P(2) is established from P(1) and ( ii ). Then, P(3) is established from P(2) and ( ii ). ... Thus, the proposition P(n) holds for all natural numbers n. Such method of proving is called mathematical induction and is frequently used to prove the equalities and inequalities regarding the natural numbers n. Exercise When n is a natural number, prove that n3 + 2n is divisible by 3. Proof Proof by mathematical induction. ( i ) When n = 1, n3 + 2n = 13 + 2 · 1 = 3 Thus, it is divisible by 3.

220 Chapter 7 Number of cases and sequence of numbers ( ii ) Suppose that n3 + 2n = k3 + 2k is divisible by 3, when n = k. At the time, it can be expressed as k3+2k = 3m. (Note : m is an integer) Then, think about n3 + 2n, when n = k + 1, n3 + 2n = (k + 1)3 + 2(k + 1) = k3 + 2k + 3(k2 + k + 1) = 3(m + k2 + k + 1) Therefore, (k + 1)3 + 2(k + 1) is divisible by 3, when n = k + 1. From ( i ) and ( ii )), n3 + 2n is divisible by 3 for all natural numbers n. // Exercise Prove that the n-th term of number sequence expressed by the recurrence formula, a1 = 3, ak+1 = 3ak + 3k+1 (k = 1, 2, 3, ) is given by the following formula. (1) an = n · 3n Proof Proof by mathematical induction. // ( i ) When n = 1, Left side of (1) = a1 = 3, Right side of (1) = a1 = 3 Thus, (1) is established. ( ii ) Suppose that (1) is established, when n = k. ak = k · 3k When n = k + 1, by using recurrence formula and the supposition above, ak+1 = 3ak + 3k+1 = 3(k · 3k) + 3k+1 = (k + 1) · 3k+1 Thus, (1) is established, when n = k + 1. From ( i ) and ( ii ), (1) is established for all natural numbers n. Q. For a number sequence expressed by the following recurrence formula, a1 = 2, ak+1 = 2 − 1 (k = 1, 2, 3, ) ak prove that an = n+1 using mathematical induction. n

§ 2 Sequence of numbers 221 Exercises 2–A 1. For the arithmetical progression with first term 35 and common difference −2, answer the following. (1) In which term does the value be negative for the first time ? (2) Find the sum of the first 10 terms. (3) Find the value of n, when the sum of first n terms is negative for the first time. 2. For the geometrical progression with first term 2 and common ratio 3, answer the following. (1) In which term does the value be over 1000 for the first time ? (2) Find the sum of first 5 terms. (3) Find the value of n, when the sum of the first n terms is over 10000 for the first time. 3. By using two different methods (1) and (2), prove that the following equality is established, when n is a natural number. 1 n2(n + 1)2 = { n(n + 1) }2 ∑n 42 k3 = k=1 (1) By using the identical equation (k + 1)4 − (k − 1)4 = 8k3 + 8k. (2) By using mathematical induction. 4. Find the sums. n∑−1 ∑n (2) k(k + 1) (1) k2(k + 1) k=1 k=1 5. Prove that the n-th term of number sequence expressed by the recurrence formula, ) a1 = 1, ak+1 = 2ak + (k + 1)2k (k = 1, 2, 3, is given by the following formula. an = n(n + 1)2n−2

222 Chapter 7 Number of cases and sequence of numbers Exercises 2–B 1. For the number sequence an, the difference, where bn = an+1 − an, between (n + 1)-th term and n-th term is called difference. A number sequence bn determined by the difference is called progression of difference of an. Answer the following. n∑−1 (1) Prove that an = a1 + bk. k=1 (2) Find the progression of difference bn of the following sequence an and ex- press aa with a formula of n. 1, 2, 4, 7, 11, 2. When the sum Sn of the first n terms of number sequence an is expressed as Sn = n2 + 2n (n ≧ 1). Find the sequence an. 3. There are n straight lines on a plane surface. None of two lines are parallel and none of three lines pass through the same points. Let the num- ber of intersection points be an, then solve the following. (1) Find the values of a2, a3 and a4. (2) Express ak+1 with ak and k. (3) Express an with a formula of n. (n ≧ 2) 3. For any natural number n, prove that 8n − 1 is divisible by 7. 5. Suppose that p, q, r are different prime numbers and l, m, n are natural numbers. Prove that the sum of all divisors of integer plqmrn are given below. pl+1 − 1 · qm+1 − 1 · rn+1 − 1 p−1 q−1 r−1