MATHEMATICAL INDUCTION

449. Induction is generally understood as the process of inferring a general principle from particular instances. But mathematical induction differs in some respects from ordinary induction. Mathematical Induction is the process of proving a general principle by means of a known fact together with a conditional principle. The known fact is that the principle under consideration is true for as many of the first consecutive cases as we examine, and the conditional principle is that if it is true for the nth case it holds true for the (n + 1)th case.

This method of proof is illustrated by the following examples:

=

1. In the series of odd numbers 1, 3, 5, 7, ..., the first odd number = 2(1) 1; the second odd number 2(2) -1; the third odd number = 2(3) 1. From these particular instances it may be inferred that the nth odd number 2n 1, and it is now stated as a principle to be investigated that in the series 1, 3, 5, 7, ..., any odd number is 1 less than twice the number of the term.

Supposing that the nth odd number is 2n1, by the law of the given series the (n + 1)th odd number is (2n − 1) + 2.

(2n+2)

But, $$ 56, 85, (2n-1) + 2 = (2n + 2) — 1 = 2(n + 1) −1; that is, the principle holds for the (n + 1)th odd number on condition that it holds for the nth odd number.

Therefore, since the principle is true for the third odd number it holds for the fourth; since it is true for the fourth it holds for the fifth; and so on. Hence, the principle is true generally.

2. By trial - y, x3 — y2, x3 — y3, xy, and -y are each found to be divisible by x y. From these special cases it may be inferred, and stated as a principle to be proved or disproved,

that the difference of any like powers of two numbers is divisible by the difference of the numbers. But the proved fact that x − y, x2 — y2, ..., xô -y are each divisible by x y is no warrant for accepting without further inquiry the statement that a y, for example, is divisible by x-y. It is first necessary to know whether x - y can be expressed in terms of these numbers known to be exactly divisible by xy. Since y6 x6 – x3y +x3y y=x3 (x − y) + y (xy), each term of which has been proved to be divisible by a y, 26 — y is divisible by x - y; and this illustrates the general proof.

-

it follows that "+1 y,

y" is divisible by x

=

"

is divisible by x

These two things then are proved:

First, the difference of the same powers of any two numbers, up to and including the fifth powers, is divisible by the difference of the numbers.

Second, if the difference of the nth powers of any two numbers is divisible by the difference of the numbers, the difference of the next higher powers is divisible by the difference of the numbers.

Therefore, since by actual division ay has been proved to be divisible by x y, 26 y is divisible by a y; since, as just

y, xy' is divisible by a since, as just proved, y is divisible by ay, ay is divisible by x

Hence, for all positive integral values of n, however great, x" — y" is divisible by x

3. Let it be required to derive a formula for squaring any polynomial.

By actual multiplication, rearranging terms,

(a + b)2 = a2 + b2 + 2 ab;

(a+b+c)2 = a2 + b2 + c2 + 2 ab + 2 ac + 2 bc;

+2ab+2 ac + 2 ad + 2 bc + 2 bd + 2 cd.

(3)

It is proved, then, that the square of a polynomial of n terms, provided that n is not greater than 4, is equal to the sum of the squares of the terms, plus twice the product of each term by each term that follows it. It may be inferred that this principle is of general application, but without further proof it does not follow that it holds for polynomials of more than four terms.

Suppose, however, that the principle is true for a polynomial of n terms, n being any positive integer. If this is so, then,

is the formula for the square of a polynomial of n terms.

But (5) expresses the same law for forming the square of a polynomial of n+1 terms that (4) expresses for forming the square of a polynomial of n terms. Hence, if the principle is true for polynomials of n terms, it is true for polynomials of n + 1 terms.

By actual multiplication the principle has been proved true for polynomials of two, three, and four terms, respectively. Therefore, being true for polynomials of four terms, the principle holds. true for polynomials of five terms; being true for polynomials of

five terms, it holds true for polynomials of six terms; and so on indefinitely.

Hence, the principle is universally true.

4. Let it be required to prove by mathematical induction that

12+22+32 + ... +n2 = {n(n + 1) (2 n + 1).

Supposing that (1) is true, then, Ax. 2,

+n2+(n+1)2 = { n(n + 1) (2 n + 1) + (n + 1)2

= }(n + 1)[n(2 n + 1) + 6(n + 1)]

=

(1)

(2)

By comparing (2) with (1) it is seen that the sum of the squares of the first (n + 1) integers has the same form with respect to (n + 1) that the sum of the squares of the first n integers has with respect to n; that is, it has been proved that if the formula is true for n terms, it is true for n + 1 terms.

...

It can be verified by actual trial that the formula is true for 1, 2, 3, 4, terms, as far as we please. Supposing that the verification stops with n = = 5. By the above proof, since the formula is true for five terms it holds true for six terms; being true for six terms it holds true for seven terms; and so on indefinitely. Hence, the principle expressed by (1) is true for all integral values of n.

5. x2- y2n is divisible by x+y, n being a positive integer.

THE BINOMIAL THEOREM

450. The Binomial Theorem derives a formula by means of which any power of a binomial may be expanded into a series, whether the index of the power is positive or negative, integral or fractional.

POSITIVE INTEGRAL EXPONENTS

451. The powers of (a + x), expanded in § 221, may be written :

If the law of development revealed in the above is assumed to ▾ apply to the expansion of any power of any binomial, as the nth power of (a + x), the result is

(a+x)"=a"+na”-1x+

n(n−1) an−2x2 +

n(n-1)(n-2) an-31⁄23 +... (1)

1.2

1.2.3

From formula (1) it is evident that in any term,

1. The exponent of x is 1 less than the number of the term. Hence, the exponent of x in the (r+1)th term is r.

2. The exponent of a is a minus the exponent of x. Hence, the exponent of a in the (r+1)th term is n — r.