Summary Mathematical Induction, Advanced Programme Mathematics - Grade 12 (IEB)

Mathematical Induction
= helps to prove statements

Steps:
1. Let S(n) be a statement involving the natural number, n
2. Prove that statement is true for n = 1
3. Assume the statement is true for n = k where k € N
4. Prove true for n = k + 1
5. By the principle of MI, the statement is true A n € N

Two types:
- Divisibility
- Summing

Example of divisibility:

Prove 5n - 1 is divisible by 4 for n ∈ N

Step 1: Prove that statement is true for n = 1
51 - 1 = 4
4
. =1
4
∴ The statement is true for n = 1

Step 2: Assume the statement is true for n = k where k ∈ N
5k - 1 is divisible by 4
5𝑘−1
. 4
= p where p ∈ N
5k - 1 = 4p
. 5k = 4p + 1

Step 3: Prove true for n = k + 1
5k + 1 – 1
= 5k.51 – 1
= (4p + 1).5 – 1
= 20p + 5 – 1
= 20p + 4
= 4 (5p + 1) which is divisible by 4.

Step 4: By the principle of MI, the statement is true A n ∈ N

Example of a summing:

Prove that 2 + 4 + 6 + ... + 2n = n (n + 1) for n ∈N

LHS:
T1 = 2
T2 = 4
T3 = 6
T4 = 2n

RHS:
Sn = n(n + 1)