608. The method of mathematical induction may be divided into three parts: First, it is ascertained by observation or trial that the theorem under consideration is true in some particular cases; in the second step, it is proved that if the theorem is true in any case it is true in the next case; in the third step, the conclusion is deduced that the proposition holds in any case by combining the results of the first and second steps, i. e., if the proposition is true in any arbitrary case it is true in the next case (second step) but the proposition is known to be true in some cases, therefore it is true in the next case, and so on for any case.

609. There is, in general, a marked distinction between the method of mathematical induction and the inductive method of reasoning used in the natural sciences, for example, in Chemistry and Physics. In these sciences a law or theorem is formulated which is observed to be true in a number of particular cases, verified by experiment or investigation. The investigator however guards his conclusions by verifying as many test cases as possible. Such a law thus established is accepted as true until the discovery of a fact (hitherto not taken into account) compels a modification. The second step in mathematical induction is entirely omitted in the inductive method of reasoning as used in the natural sciences. The method of mathematical induction is just as rigorous as any of the direct methods of mathematical demonstration.

6. Prove the general formula in 268 for expanding

(a + a + a + . . . . + a„)2.

CHAPTER II

ARRANGEMENTS AND COMBINATIONS

610. One supposes that there are n distinct objects at hand. The arrangements of these n objects taken at a time are the different dispositions which can be made with these n objects, by taking them r at a time in all possible ways, and placing them side by side in a straight line. Two arrangements differ either by the nature of the objects which compose them, or only by the order in which they are placed.

For example, in the case of three letters, a, b, c, taken two at a time in all possible ways, we can form the six following arrangements:

ab, ac, ba, bc, ca, cb.

The first and the third, the second and the fifth, the fourth and the sixth, differ respectively only in the order in which the letters are placed.

In general, let the n different objects be represented by the following symbols,

and let 4* designate the number of arrangements which can be formed with these n objects taken at a time and in all possible ways.

611. The number of arrangements of n objects taken one at a time is found evidently by taking each of them separately; which gives n arrangements,

The arrangements of n objects taken two at a time are found by placing after the first symbol, a1, each of the other symbols suc

*n is not a factor but a part of the symbol.

cessively; after the second symbol, a,, each of the others successively, and so on; which gives us the following table of arrangements:

The first horizontal line contains all the arrangements which begin with the symbol a,, the second all of those which begin with the symbol a,, etc.; thus are formed all the arrangements of n symbols taken two at a time. Since each horizontal row contains n - . 1 arrangements, and there are n rows, the table contains n(n - 1) arrangements; therefore,

Similarly, if after each of the arrangements taken two at a time, each of the other n 2 symbols is placed successively, the following table of arrangements taken three at a time is formed:

-

p

the first arrangements of two symbols, a, a,; similarly, after the second, a, a each of the other symbols, an, etc., has been placed. Therefore, all the arrangements of a things taken three at a time have been tabulated; because an arrangement of three letters is successively composed of an arrangement of two letters followed by another letter. The same arrangement is not repeated, because the arrangements of the same horizontal row differ by the third symbol, and two arrangements of two rows differ by the arrangement of the first two letters. Each horizontal row contains n 2 arrangements; and there are n (n − 1) horizontal rows, just as many as there are arrangements of n things taken two at a time; therefore, the number of arrangements of n symbols three at a time is

By continuing the same reasoning the general formula is obtained,

(i) An (n-1) (n − 2) . . . . ( n − r + 1).

n

The number of arrangements of n objects taken r at a time is equal to the product of r consecutive decreasing integral numbers beginning with n.

612. It remains to prove that the formula for „4, is general. Suppose that the arrangements of n symbols taken r 1 at a time, have been formed and that it is desired to form the arrangements of n symbols taken r at a time. One places after each of the arrangements taken r- -1 at a time, each of the remaining n—(r−1)—n—r+1 symbols successively. Thus are formed all the arrangements taken r at a time; for an arrangement of r symbols is composed of r — 1 symbols followed by another symbol. The same arrangements will not be repeated, because any two arrangements thus formed differ either by the last symbol, or by the arrangement of the first r — 1 symbols. Each of the preceding arrangements will furnish n-r+1 new arrangements. Hence, it will follow in general that

If the values 2, 3, 4, . . . . n are given successively to r, the result will be

1

1

nA2 = „4, ( n − 2 + 1 ) = „4, ( n − 1 ) = n ( n − 1 ),
ng=,4,(n−3+1)= 1,(n−2),
n(n

n4 ̧ = „Å ̧ ( n − 4 + 1 ) = „4, ( n − 3),

3

From multiplying these equations together member by member the following result is obtained:

...An(-1) (n-2) (n-3)... (n-r+1); (n—1) (n−2)

or, after dividing out the equal factors,

=

4, n (n-1) (n-2)... ( n − r + 1).

Applications.-1. What is the number of the arrangements of nine symbols taken three at a time? It is the product of three consecutive decreasing integers beginning with 9,

94,9·8·7504.

2. How many different words of five letters can be formed from nine letters? The number of words will be the same as the number of arrangements of nine symbols taken five at a time,

3. How many numbers of four digits each can be formed from the first eight digits? There will be as many as there are arrangements of eight symbols taken 4 at a time,

4,8·7·6.5= 1680.

PERMUTATIONS

613. By the number of permutations of n objects is meant the number of different dispositions which may be made of n objects by placing them side by side in a straight line. Each permutation contains all the objects, and two permutations differ only in the order of the objects.

For example, two permutations can be formed from two objects, a, b,

ab, ba.

The permutation of n objects is, in general, represented by P It follows from the definition that the permutation of n objects is simply the arrangement of n objects taken at a time.

The number of permutations of n symbols is equal to the product of the first n positive integers.

614. Applications.-1. How many different words of four letters each can be formed from four given letters?

there are permutations of four letters:

There are as many as

2. In how many ways can a troop of eleven soldiers be disposed In as many ways as there are permutations of eleven

of in a line?

objects:

P1 = 1.2.3. . . . . 11 = 39,916,800.