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