Proof by Induction Topic Review summary

Key learning points

• Structure: basis → assume true for $k$ → prove for $k+1$ → conclude for all $n\\ge n_0$.
• Write the induction hypothesis explicitly.
• Divisibility: show $f(k+1)-f(k)$ (or similar) is divisible by the target factor.
• Inequalities: keep direction careful when multiplying/adding.
• Strong induction when the step needs more than one previous case.

Worked example 1 — Sum

Induct on $\\sum_{r=1}^n r=\\frac{n(n+1)}{2}$.

Working

Algebra to match formula at $k+1$.

Worked example 2 — Divisibility

Show $3^{2n}-1$ divisible by 8.

Working

Classic induction style.

Worked example 3 — Practice point 1

Structure: basis → assume true for $k$ → prove for $k+1$ → conclude for all $n\\\\ge n_0$.

Working

Attempt without notes, then check the answers PDF.

Worked example 4 — Practice point 2

Apply this idea from the Topic Review: Write the induction hypothesis explicitly.

Working

Attempt without notes, then check the answers PDF.

Scaffolded Learning Sheet and answers (PDFs)

This page is a short, searchable overview for revision and search engines. Use the Scaffolded Learning Sheet first, then the Answers PDF for a full written solution. The printable PDFs remain the main classroom resource.