4 Ijesha Close, Ilupeju, Lagos
+2347 086 296 002

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
  1. Prove that un = 7n + 4n + 1 is a multiple of 6
    • Step 1:
      • Let n = 1
      • ∴ un = 7 + 4 + 1 = 12 = 6 × 2
      • Therefore, the formula is true for n = 1
    • Step 2:
      • Assuming the formula is true for n = k
      • uk = 7k + 4k + 1 = 6p
      • where p is just a dummy value
      • when n = k + 1
        • uk+1 = 7k+1 + 4k+1 + 1
        • uk+1 = 7(7k) + 4(4k) + 1
        • uk+1 = 4(7k + 4k + 1) + 3(7k – 3)
        • (7k – 1) is even so can be written as 2q where q is another dummy value
        • ∴ uk+1 = 4(6p) + 3(2q)
        • uk+1 = 6(4p + q)
      • If uk is a multiple of 6, then so is uk+1
    • Conclusion: By the principle of mathematical induction,
      un = 7n + 4n + 1 is a multiple of 6 for n ≥ 1
  2. It is given that for n = 0, 1, 2, 3, …, an = 172n + 3(9n) + 20. Simplify an+1 – an, 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:
      • an = 172n + 3(9n) + 20
      • an+1 = 172n+2 + 3(9n+1) + 20
      • an+1 = 17²(172n) + 3(9)(9n) + 20
      • Calculating an+1 – an:
        • 17²(172n) + 3(9)(9n) + 20 – 172n – 3(9n) – 20
        • 288(172n) + 24(9n)
        • 24(12)(172n) + 24(9n)
        • 24(12(172n) + 9n)
    • Conclusion: By the principle of mathematical induction
      an = 172n + 3(9n) + 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)21 = 3/4
      • Using the formula given:
        • 1 – 1/(1 + 1)21 = 1 – 1/4 = 3/4
      • Therefore, the formula is true for N = 1
    • Step 2:
      • Assume the formula is true for N = k
      • When N = k
        • 1 – 1/(k + 1)2k
      • When N = k+1
        • 1 – 1/(k + 1 + 1)2k+1
        • = 1 – 1/(k + 2)2k+1
      • If the formula is true then:
        • k+1n=1 (n + 2/n(n + 1)2n) = kn=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
Minimum 4 characters