Checking a formula for a few values of n never proves it for every n. This course introduces mathematical induction, the method that does. It starts with the principle itself, explained through a row of falling dominoes, and a fixed four-part layout for every proof. Students then prove the classic formulas for sums of squares and cubes, divisibility results such as 7ⁿ − 1 being a multiple of 6, and inequalities, including those that only hold from some starting number. The last lesson applies induction to sequences defined step by step, to products and to counting, and explains the common mistakes that break a proof.
Middle Years
Mathematical Induction
The principle of mathematical induction and how to set out a proof, with induction proofs of sum formulas, divisibility results, inequalities, recursive sequences, products and counting results.
- 5 lessons
Overview
Lessons
-
The principle of mathematical induction
Why checking cases proves nothing, statements P(n), the domino picture, the base step and inductive step, and a four-part layout for every induction proof.
-
Proving formulas for sums
Induction proofs of the sums of squares and cubes, series of products and fractions, and a geometric series, using the sum of k terms plus one more term.
-
Proving divisibility
Writing divisibility as an equation, then making the k expression appear inside the k + 1 expression by substituting or by adding and subtracting a term.
-
Proving inequalities
Induction for inequalities such as 2ⁿ > n and Bernoulli's inequality, starting the induction at a number other than 1, and factorials.
-
More uses of induction and common mistakes
Induction for recursive sequences, long products and counting diagonals, and the mistakes that break a proof, including the famous same-height fallacy.