Proof by mathematical induction

Learning objectives

Set out an induction proof with a verified base case, a clearly stated inductive hypothesis assumed true for n = k, a proof of the statement for n = k + 1 that uses the hypothesis, and a closing statement of the conclusion

Prove a closed formula for the sum of a series, or for the nth term of a sequence defined by a recurrence relation, by induction

Prove a divisibility result by induction, for example that 3^(2n) − 1 is a multiple of 8, by writing the expression for n = k + 1 in terms of the expression for n = k plus a multiple of the divisor

Prove a result for the nth power of a 2×2 matrix by induction, substituting the inductive hypothesis into the product Aᵏ⁺¹ = AᵏA and simplifying entry by entry

Prove a formula for an nth derivative, or an inequality that holds for all integers n greater than some starting value, by induction, being careful to start the base case at the correct value of n