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₁ + a_n) = (1 + n) =

Notation:

If P_n is a statement,
Then P₁ is this statement where n = 1
P₂ is this statement where n = 2, etc.

    Ex. Let P_n be: n² + n is positive.
        Then P₁ says, "1² + 1 is positive",
        P₄ says, "4² + 4 is positive", etc.

AXIOM OF MATHEMATICAL INDUCTION

Let P_n be a statement (i.e.P₁, P₂, P₃, ... etc. are defined).

Furthermore, let the following 2 conditions exist:

1) P₁ 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, ...

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 = , i.e., 1 = 1 SO P₁ 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ⁿ - 1 is divisible by 4.

P₁: = = = 1 Therefore: P₁ is true.

ASSUME P_k : 5^k - 1 divisible by 4.

or = q, an integer

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

PROVE P_k+1: 5^k+1 - 1 divisible by 4.

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