#### Mathematical Induction

- Step 1: Prove assertion is true for some initial value of the variable
- Step 2: The inductive step
- Conclusion: The final statement of what you have proved

**Examples of Divisibility**

- Prove that u
_{n}= 7^{n}+ 4^{n}+ 1 is a multiple of 6- Step 1:
- Let n = 1
- ∴ u
_{n}= 7 + 4 + 1 = 12 = 6 × 2 - Therefore, the formula is true for n = 1

- Step 2:
- Assuming the formula is true for n = k
- u
_{k}= 7^{k}+ 4^{k}+ 1 = 6p - where p is just a dummy value
- when n = k + 1
- u
_{k+1}= 7^{k+1}+ 4^{k+1}+ 1 - u
_{k+1}= 7(7^{k}) + 4(4^{k}) + 1 - u
_{k+1}= 4(7^{k}+ 4^{k}+ 1) + 3(7^{k}– 3) - (7
^{k}– 1) is even so can be written as 2q where q is another dummy value - ∴ u
_{k+1}= 4(6p) + 3(2q) - u
_{k+1}= 6(4p + q)

- u
- If u
_{k}is a multiple of 6, then so is u_{k+1}

- Conclusion: By the principle of mathematical induction,

u_{n}= 7^{n}+ 4^{n}+ 1 is a multiple of 6 for n ≥ 1

- Step 1:
- It is given that for n = 0, 1, 2, 3, …, a
_{n}= 17^{2n}+ 3(9^{n}) + 20. Simplify a_{n+1}– a_{n}, and hence prove by induction that an is divisible by 24 for all n ≥ 0.- Skip step 1 as it is already given
- Step 2:
- a
_{n}= 17^{2n}+ 3(9^{n}) + 20 - a
_{n+1}= 17^{2n+2}+ 3(9^{n+1}) + 20 - a
_{n+1}= 17²(17^{2n}) + 3(9)(9^{n}) + 20 - Calculating a
_{n+1}– a_{n}:- 17²(17
^{2n}) + 3(9)(9^{n}) + 20 – 17^{2n}– 3(9^{n}) – 20 - 288(17
^{2n}) + 24(9^{n}) - 24(12)(17
^{2n}) + 24(9^{n}) - 24(12(17
^{2n}) + 9^{n})

- 17²(17

- a
- Conclusion: By the principle of mathematical induction

a_{n}= 17^{2n}+ 3(9^{n}) + 20 is a multiple of 24, for n ≥ 0

**Example of Summation**

- Prove by induction that, for all N ≥ 1,

- Step 1:
- Let N = 1:
^{1 + 2}/_{1(1 + 1)21}=^{3}/_{4}

- Using the formula given:
- 1 –
^{1}/_{(1 + 1)21}= 1 –^{1}/_{4}=^{3}/_{4}

- 1 –
- Therefore, the formula is true for N = 1

- Let N = 1:
- Step 2:
- Assume the formula is true for N = k
- When N = k
- 1 –
^{1}/_{(k + 1)2k}

- 1 –
- When N = k+1
- 1 –
^{1}/_{(k + 1 + 1)2k+1} - = 1 –
^{1}/_{(k + 2)2k+1}

- 1 –
- If the formula is true then:
^{k+1}∑_{n=1}(^{n + 2}/_{n(n + 1)2n}) =^{k}∑_{n=1}(^{n + 2}/_{n(n + 1)2n}+ (k + 1)^{th}term)- = 1 –
^{1}/_{(k + 1)2k}+^{k + 3}/_{(k + 1)(k + 2)2k+1} - = 1 –
^{2(k + 2) – k – 3}/_{(k + 1)(k + 2)2k+1} - = 1 –
^{2k + 4 – k – 3}/_{(k + 1)(k + 2)2k+1} - = 1 –
^{k + 1}/_{(k + 1)(k + 2)2k+1} - = 1 –
^{1}/_{(k + 2)2k+1}

- Conclusion: By the principle of mathematical induction, the formula is true for all N ≥ 1

- Step 1: