• 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

1. Prove that u_n = 7ⁿ + 4ⁿ + 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ⁿ + 4ⁿ + 1 is a multiple of 6 for n ≥ 1
2. It is given that for n = 0, 1, 2, 3, …, a_n = 17²ⁿ + 3(9ⁿ) + 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²ⁿ + 3(9ⁿ) + 20
     • a_n+1 = 17²ⁿ⁺² + 3(9ⁿ⁺¹) + 20
     • a_n+1 = 17²(17²ⁿ) + 3(9)(9ⁿ) + 20
     • Calculating a_n+1 – a_n:
       • 17²(17²ⁿ) + 3(9)(9ⁿ) + 20 – 17²ⁿ – 3(9ⁿ) – 20
       • 288(17²ⁿ) + 24(9ⁿ)
       • 24(12)(17²ⁿ) + 24(9ⁿ)
       • 24(12(17²ⁿ) + 9ⁿ)
   • Conclusion: By the principle of mathematical induction
     a_n = 17²ⁿ + 3(9ⁿ) + 20 is a multiple of 24, for n ≥ 0

Example of Summation

1. Prove by induction that, for all N ≥ 1,
   
   • Step 1:
     • Let N = 1:
       • ^{1 + 2}/_{1(1 + 1)2¹} = ³/₄
     • Using the formula given:
       • 1 – ¹/_{(1 + 1)2¹} = 1 – ¹/₄ = ³/₄
     • Therefore, the formula is true for N = 1
   • Step 2:
     • Assume the formula is true for N = k
     • When N = k
       • 1 – ¹/_{(k + 1)2^k}
     • When N = k+1
       • 1 – ¹/_{(k + 1 + 1)2^k+1}
       • = 1 – ¹/_{(k + 2)2^k+1}
     • If the formula is true then:
       • ^k+1∑_n=1 (^{n + 2}/_{n(n + 1)2ⁿ}) = ^k∑_n=1 (^{n + 2}/_{n(n + 1)2ⁿ} + (k + 1)^th term)
       • = 1 – ¹/_{(k + 1)2^k} + ^{k + 3}/_{(k + 1)(k + 2)2^k+1}
       • = 1 – ^{2(k + 2) – k – 3}/_{(k + 1)(k + 2)2^k+1}
       • = 1 – ^{2k + 4 – k – 3}/_{(k + 1)(k + 2)2^k+1}
       • = 1 – ^{k + 1}/_{(k + 1)(k + 2)2^k+1}
       • = 1 – ¹/_{(k + 2)2^k+1}
   • Conclusion: By the principle of mathematical induction, the formula is true for all N ≥ 1