MATH 122
MATHEMATICAL INDUCTION

Let Pn 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 Sn = (a1 + an) = (1 + n) =

Notation:

If Pn is a statement,
Then P1 is this statement where n = 1
P2 is this statement where n = 2, etc.

    Ex. Let Pn be: n + n is positive.
        Then P1 says, "1 + 1 is positive",
        P4 says, "4 + 4 is positive", etc.

AXIOM OF MATHEMATICAL INDUCTION

Let Pn be a statement (i.e.P1, P2, P3, ... etc. are defined).

Furthermore, let the following 2 conditions exist:

1) P1 is true
2) Pk+1 is true whenever Pk is true (k is any positive integer)

Conclusion: Pn is true for n = 1, 2, 3, ...

    i.e.P1, P2, P3, P4,... are all true.

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

EXAMPLE 1. PROVE 1 + 2 + 3 + ... + n = by mathematical induction.
        (i.e. Prove that Pn is true for n = 1, 2, 3, ...)

Pn: 1 + 2 + 3 + ... + n =

P1: 1 = , i.e., 1 = 1 SO P1 is true
    ASSUME Pk true: i.e., 1 + 2 + 3 + ... + k =
    PROVE Pk+1 true: i.e., Prove 1 + 2 + 3 + ... + (k + 1) =

USUALLY YOU START ALL WITH THE LEFT SIDE OF Pk+1:

   
Therefore, Pn true for n = 1, 2, 3,...

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

EXAMPLE 2. SHOW THAT: Pn: 5n - 1 is divisible by 4.

P1: = = = 1 Therefore: P1 is true.

ASSUME Pk : 5k - 1 divisible by 4.

or = q, an integer

Then 5k - 1 = 4q and 5k = 4q + 1

PROVE Pk+1: 5k+1 - 1 divisible by 4.

   
    Therefore Pn TRUE for n = 1, 2, 3,...