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)

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

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.