Mathematical Induction

Key idea

Prove statements for all n by base case and inductive step.

In depth

To prove a statement for all n ≥ 1: show the base case, then show that if it is true for k, it is true for k + 1. Like dominoes, the first falls and each knocks over the next.

Worked example

Prove 1 + 2 + ... + n = n(n+1)/2: n = 1 works. Assume for k, then add (k + 1) to get (k+1)(k+2)/2.

Real-world uses

• Proving that code loops or algorithms work for all input sizes in computer science

Common mistake

Assuming what you are trying to prove in the step instead of the inductive hypothesis.

How to learn this

1. Read the key idea and say it in your own words.
2. Work through the worked example, then try a similar problem.
3. Use the interactive lesson’s visual and mini-quiz to check the pattern.

Frequently asked questions

Expand all Collapse all

Related expert topics in Algebra

• Linear Programming – Optimise a linear objective over a feasible polygon; maxima occur at vertices.
• Rational Root Theorem – Possible rational roots are ± factors of constant over factors of leading coefficient.
• Fundamental Theorem of Algebra – Every degree-n polynomial has exactly n complex roots counted with multiplicity.
• Binomial Theorem – Expand (a+b)ⁿ with binomial coefficients.
• Partial Fractions – Decompose a rational function into simpler fractions.
• Cramer’s Rule – Solve linear systems using determinants.