MATH 122

MATHEMATICAL INDUCTION

Let P_{n} be a statement involving the positive integer n. Some
examples are:

a) n² = n x n

b) 2n is an even number

c) 2n + 1 is an odd number

d) = 1

e) n is divisible by 3

f) 1 + 2 + 3 + ... + n =

Which of the above statements are true for ALL positive integral values of n?

Answer: a, b, c and f (f is not obviously true)

Note that d is not true for any value of n, while c is only true for

n = 3, 6, 9, ...

f is true for the following reason:

1 + 2 + 3 + ... + n = sum of the first n terms of an A.P.

Thus S_{n} = (a_{1}
+ a_{n}) = (1 + n) =

Notation:

If P

_{n}is a statement,

Then P_{1}is this statement where n = 1

P_{2}is this statement where n = 2, etc.

Ex. Let P_{n} be: n² + n is positive.

Then P_{1} says, "1² + 1 is
positive",

P_{4} says, "4² + 4 is
positive", etc.

__AXIOM OF MATHEMATICAL INDUCTION__

Let P_{n} be a statement (i.e.P_{1}, P_{2}, P_{3},
... etc. are defined).

Furthermore, let the following 2 conditions exist:

1) P

_{1}is true

2) P_{k+1}is true whenever P_{k}is true (k is any positive integer)

Conclusion: P_{n} is true for n = 1, 2, 3, ...

i.e.P_{1}, P_{2}, P_{3}, P_{4},...
are __all__ true.

---------------------------------------------------------------------------

__EXAMPLE 1__. PROVE 1 + 2 + 3 + ... + n = by mathematical induction.

(i.e. Prove that P_{n} is true for n =
1, 2, 3, ...)

P_{n}: 1 + 2 + 3 + ... + n =

P_{1}: 1
= , i.e., 1 = 1 SO P_{1} __is__ true

ASSUME P_{k} true: i.e., 1 + 2 + 3 + ... + k =

PROVE P_{k+1} true: i.e., Prove 1 + 2 + 3 + ... + (k + 1) =

USUALLY YOU START ALL WITH THE LEFT SIDE OF P_{k+1}:

Therefore, P_{n} true for n = 1, 2, 3,...

---------------------------------------------------------------------------

__EXAMPLE 2__. SHOW THAT: P_{n}: 5^{n} - 1 is divisible
by 4.

P_{1}: = = = 1 Therefore: P_{1} is true.

ASSUME P

_{k}: 5^{k}- 1 divisible by 4.or = q, an integer

Then 5

^{k}- 1 = 4q and 5^{k}= 4q + 1PROVE P

_{k+1}: 5^{k+1}- 1 divisible by 4.

Therefore P_{n} TRUE for n = 1, 2, 3,...