| n(r)＝(n −1)(r) + (n −1)(r−1) | (4), |
and therefore
(nr)＝n(r).
Hence the formula (2) is also true for the nth power of A+a. But it is true for the 1st and the 2nd powers; therefore it is true for the 3rd; therefore for the 4th; and so on. Hence it is true for all positive integral powers of n.
(iii.) The product 1. 2. 3 . . . r is denoted by |r or r !, and is called factorial r. The form r ! is better for printing, but the form |r is more convenient for ordinary use. If we denote n(n−1) . . . (n−r+ 1) (r factors) by n(r), then n(r) ≡ n(r)/r !.
(iv.) We can write n(r) in the more symmetrical form
| n(r) ＝ n!(n−r)! r | (5), |
which shows that
| n(r) ＝ n(n−r) | (6). |
We should have arrived at this form in (i.) by considering the selection of terms in which there are to be two large and three small letters, the large letters being written down first. The terms can be built up in 5! ways; but each will appear 2! 3! times.
(v.) Since n(r) is an integer, n(r) is divisible by r !; i.e. the product of any r consecutive integers is divisible by r ! (see § 42 (ii.)).
(vi.) The product r ! arose in (i.) by the successive multiplication of r, r − 1, r − 2, . . . 1. In practice the successive factorials 1!, 2!, 3! . . . are supposed to be obtained successively by introduction of new factors, so that
| r ! ＝ r . (r −1)! | (7). |
Thus in defining r ! as 1. 2. 3 . . . r we regard the multiplications as taking place from left to right; and similarly in n(r). A product in which multiplications are taken in this order is called a continued product.
(vii.) In order to make the formula (5) hold for the extreme values n(0) and n(n) we must adopt the convention that
| 0! ＝ 1 | (8). |
This is consistent with (7), which gives 1! ＝ 1.0!. It should be observed that, for r ＝ 0, (4) is replaced by
| n(0) ＝ (n − 1)(0) | (9), |
and similarly, for the final terms, we should note that
| p(q) ＝ 0 if q > p | (10). |
(viii.) If ur denotes the term involving ar in the expansion of (A+a)n, then ur/ur −1 ＝ {(n−r+1)/r}.a/A. This decreases as r increases; its value ranging from na/A to a/(nA). If na<A, the terms will decrease from the beginning; if n A<a, the terms will increase up to the end; if na > A and nA > a, the terms will first increase up to a greatest term (or two consecutive equal greatest terms) and then decrease.
(ix) The position of the greatest term will depend on the relative values of A and a; if a/A is small, it will be near the beginning. Advantage can be taken of this, when n is large, to make approximate calculations, by omitting terms that are negligible.
(a) Let Sr denote the sum u0+u1+ . . . ur, this sum being taken so as to include the greatest term (or terms); and let ur+1/ur ＝ θ, so that θ<1. Then the sum of the remaining terms ur+1+ur+2+ . . . +un is less than(1+θ+θ2+ . . . +θn−r −1)ur+1, which is less than ur+1/(1−θ); and therefore (A+a)n lies between Sr, and Sr + ur+1/(1−θ). We can therefore stop as soon as ur+1/(1−θ) becomes negligible.
(b) In the same way, for the expansion of (A − a)n, let σr denote u0−u1+ . . . ± ur. Then, provided σr includes the greatest term, it will be found that (A − a)n lies between σr and σr+1.
For actual calculation it is most convenient to write the theorem in the form
(A±a)n ＝ An(1±x)n ＝ An±n1x.An+n−12x.n1x.An±...
where x ≡ a/A; thus the successive terms are obtained by successive multiplication. To apply the method to the calculation of Nn, it is necessary that we should be able to express N in the form A+a or A−a, where a is small in comparison with A, An is easy to calculate and a/A is convenient as a. multiplier.
42. The reasoning adopted in § 41 (ii.) illustrates two general methods of procedure. We know that (A+a)n is equal to a multinomial of n+1 terms with unknown coefficients, and we require to find these coefficients. We therefore represent them by separate symbols, in the same way that we represent the unknown quantity in an equation by a symbol. This is the method of undetermined coefficients. We then obtain a set of equations, and by means of these equations we establish the required result by a process known as mathematical induction. This process consists in proving that a property involving p is true when p is any positive integer by proving (1) that it is true when p ＝ 1, and (2) that if it is true when p ＝ n, where n is any positive integer, then it is true when p ＝ n+1. The following are some further examples of mathematical induction.
(i.) By adding successively 1, 3, 5 . . . we obtain 1, 4, 9, . . . This suggests that, if un is the sum of the first n odd numbers, then un ＝ n2. Assume this true for u1, u2, . . ., un. Then un+1 ＝ un+(2n+1) ＝ n2+(2n+1) ＝ (n+1)2, so that it is true for un+1. But it is true for u1. Therefore it is true generally.
(ii.) We can prove the theorem of § 41 (v.) by a double application of the method.
(a) It is clear that every integer is divisible by 1!.
(b) Let us assume that the product of every set of p consecutive integers is divisible by p!, and let us try to prove that the product of every set of p+1 consecutive integers is divisible by (p+1)!. Denote the product n(n+1) . . . (n+r −1) by n[r]. Then the assumption is that, whatever positive integral value n may have, n[p] is divisible by p!.
(1) n[p+1]−(n−1)[p+1] ＝ n(n+1). . . (n+p−1) ＝ (p+1) . n[p]. But, by hypothesis, n[p+1]−(n−1)[p+1] is divisible by p!. Therefore if (n−1)[p+1] is divisible by (p+1)!, n[p+1] is divisible by (p+1)!.
(2) But 1[p+1] ＝ (p+1)!, which is divisible by (p+1)!.
(3) Therefore n[p+1] is divisible by (p+1)!, whatever positive integral value n may have.
(c) Thus, if the theorem of § 41 (v.) is true for r ＝ p, it is true for r ＝ p+1. But it is true for r ＝ 1. Therefore it is true generally.
(iii.) Another application of the method is to proving the law of formation of consecutive convergent to a continued fraction (see Continued Fractions).
43. Binomial Coefficients.—The numbers denoted by n(r) in § 41 are the binomial coefficients shown in the table in § 40; n(r) being the (r+1)th number in the (n+1)th row. They have arisen as the coefficients in the expansion of (A+a)n; but they may be considered independently as a system of numbers defined by (1) of § 41. The individual numbers are connected by various relations, some of which are considered in this section.
(i.) From (4) of § 41 we have
| n(r)−(n−1)(r) ＝ (n−1)(r −1) | (11). |
Changing n into n−1, n−2, . . ., and adding the results,
| n(r)−(n−s)(r) ＝ (n−1)(r −1)+(n−2)(r −1)+ ... +(n−s)(r −1) | (12). |
In particular,
| n(r) ＝ (n−1)(r −1)+(n−2)(r −1)+...+(r −1)(r −1) | (13). |
Similarly, by writing (4) in the form
| n(r)−(n−1)(r −1) ＝ (n−1)(r) | (14), |
changing n and r into n−1 and r −1, repeating the process, and adding, we find, taking account of (9),
| n(r) ＝ (n−1)(r)+(n−2)(r −1)+...+(n−r −1)0 | (15). |
(ii.) It is therefore more convenient to rearrange the table of § 40 as shown below, on the left; the table on the right giving the key to the arrangement.
| 1 | 0(0) | |||||||||||||||||
| 1 | 1(1) | |||||||||||||||||
| 1 | 1 | 1(0) | 2(2) | |||||||||||||||
| 2 | 1 | 2(1) | 3(3) | |||||||||||||||
| 1 | 3 | 1 | 2(0) | 3(2) | 4(4) | |||||||||||||
| 3 | 4 | 1 | 3(1) | 4(3) | 5(5) | |||||||||||||
| 1 | 6 | 5 | 1 | 3(0) | 4(2) | 5(4) | 6(6) | |||||||||||
| 4 | 10 | 6 | 1 | 4(1) | 5(3) | 6(5) | 7(7) | |||||||||||
| 1 | 10 | 15 | 7 | 1 | 4(0) | 5(2) | 6(4) | 7(6) | 8(8) | |||||||||
| &c., | &c., | |||||||||||||||||
