Resources For Teachers For Tutors For Students & Parents Pricing
Create Free Account
Algebra 2 Proof by induction

Mathematical induction

20 practice questions 0 video lessons Theory + worked examples
Practice 20 questions
Practice questions

Every question with a fully worked solution.

Start practising
Create a free accountTrack your progress and save your work as you go.
Create free account

Theory

Mathematical induction proves a statement \(P(n)\) for all natural numbers in two parts:
  1. Base case: show \(P(1)\) is true.
  2. Inductive step: assume \(P(k)\), then prove \(P(k+1)\).
Like falling dominoes: the base case tips the first, and each step topples the next.
Induction as dominoes Induction proves a statement for all n: the base case starts the chain and each step topples the next. base case each pushes the next induction is like falling dominoes
The base case starts the chain; each step topples the next.
Proof by induction Proof by induction Proof by induction 1. base case: show true for n = 1 2. assume true for n = k 3. prove it for n = k + 1 then true for all n
The structure of an induction proof.

The two parts:

\[P(1)\ \text{true},\qquad P(k)\Rightarrow P(k+1)\]
show P of 1, then show P of k implies P of k plus 1
Both parts are required — one alone doesn't prove the statement.

How to prove by induction

  1. Verify the base case \(P(1)\).
  2. Assume \(P(k)\) is true (the inductive hypothesis).
  3. Use it to prove \(P(k+1)\).
  4. Conclude \(P(n)\) holds for all \(n\).
Example 1 — Base case
To prove \(1+2+\dots+n=\dfrac{n(n+1)}{2}\), check the base case \(n=1\).
Solution

Both sides must match at \(n=1\).

\(\text{left}\)\(=\)\(1\)
\(\text{right}\)\(=\)\(\dfrac{1(2)}{2}=1\ \checkmark\)
the base case holds at n equals 1
Example 2 — Inductive hypothesis
State the inductive hypothesis for that sum.
Solution

Assume the statement holds at \(n=k\).

\(1+2+\dots+k\)\(=\)\(\dfrac{k(k+1)}{2}\)
assume the formula holds for n equals k
Example 3 — Inductive step
Show it then holds for \(k+1\).
Solution

Add \((k+1)\) to both sides.

\(\dfrac{k(k+1)}{2}+(k+1)\)\(=\)\(\dfrac{k(k+1)+2(k+1)}{2}\)
\(=\)\(\dfrac{(k+1)(k+2)}{2}\)

This is the formula at \(k+1\), completing the proof.

the step gives the formula at k plus 1
Example 4 — The two parts
What two parts does every induction proof need?
Solution

A base case and an inductive step (assume \(k\), prove \(k+1\)).

a base case and an inductive step

Common pitfalls

You need both parts — base case and inductive step.
Use the hypothesis \(P(k)\) in the step.
Prove \(P(k+1)\) exactly, not just plausibly.

Frequently asked questions

What is mathematical induction?

A method to prove a statement for all natural numbers.

What is the base case?

Showing the statement is true for the first value, usually \(n=1\).

What is the inductive step?

Assuming the statement for \(k\) and proving it for \(k+1\).

Why does induction work?

Like dominoes: the base case starts the chain and each step continues it.

More in Proof by induction