FM - Core Pure 1 - 8) Proof by induction

Question 1

General steps of proof by induction

Answer 1

• Basis → prove the statement is true for n = 1
• Assumption → assume the statement is true for n = k
• Inductive → prove the statement is true for n = k + 1
• Conclusion → state the statement is true for all n ∈ ℤ⁺

Question 2

Method for proof by induction of summations of series

Answer 2

1. Let n = 1
2. Substitute 1 into both sides
3. LHS = RHS ∴ true for n = 1
4. Let n = k
5. Substitute k into both sides
6. Let n = k + 1
7. Substitute k + 1 into RHS (what you need to find)
8. Summation of k + 1 = summation of k + [k + 1]^th term
9. k^th term (from assumption) + (substitution of k + 1 into LHS)
10. Simplify until it matches proof ∴ true for n = k + 1
11. “Statement is true for n = 1 and if true for n = k, then true for n = k + 1 ∴ true for all n ∈ ℤ⁺”

Question 3

Method for proof by induction of divisivility statements

Answer 3

1. Let n = 1
2. Substitute 1 into statement
3. Divisible by r ∴ true for n = 1
4. Let n = k
5. Substitute k into statement, is divisible by r
6. Let n = k + 1
7. Substitute k + 1 into statement
8. Rewrite and simplify terms (e.g. 3^{k + 1} = 3^k × 3⁽¹⁾)
9. Do f(k + 1) - af(k) and simplify until divisible by r
10. Divisible by r ∴ true for n = k + 1
11. “Statement is true for n = 1 and if true for n = k, then true for n = k + 1 ∴ true for all n ∈ ℤ⁺”

Question 4

Method for proof by induction of matrices

Answer 4

1. Let n = 1
2. Substitute 1 into both sides
3. LHS = RHS ∴ true for n = 1
4. Let n = k
5. Substitute k into both sides
6. Let n = k + 1
7. Substitute k + 1 into RHS (what you need to find)
8. matrix of k + 1 = matrix of k + matrix of 1
9. k^th term (from assumption) × matrix of 1
10. Simplify until it matches proof ∴ true for n = k + 1
11. “Statement is true for n = 1 and if true for n = k, then true for n = k + 1 ∴ true for all n ∈ ℤ⁺”