Prove statements for every integer using a base case and an inductive step.
AA HL
Paper 1
No GDC
12–15 min
You will not need a calculator for this topic.
How could you prove a claim is true for every positive integer without checking every integer? Reveal idea
Check the first permitted integer. Then show that a true statement at $k$ makes the statement at $k+1$ true. This covers every permitted integer in sequence.
Understand induction
How induction works
Suppose you want to prove that a statement $P(n)$ is true for every integer starting at $n_0$.
Induction does this in two parts: first, prove the statement at $n_0$. Then prove that whenever it is true for one permitted integer $k$, it must also be true for $k+1$.
The induction chainOnce the first case is true, the inductive step carries the result from one integer to the next.
The four steps
A well-written induction proof should make each of these four steps explicit.
1
Base caseVerify $P(n_0)$.
2
Inductive hypothesisAssume $P(k)$ is true for an arbitrary permitted integer $k$.
3
Inductive stepStarting from $P(k)$, prove $P(k+1)$.
4
ConclusionTherefore $P(n)$ is true for every integer $n\ge n_0$.
Checkpoint
Correct. The hypothesis is $P(k)$. The statement $P(k+1)$ is what you still need to prove.
Not quite. The inductive hypothesis must assume $P(k)$. Assuming $P(k+1)$ would assume the result we need to prove.
Show explanation
No. Assume $P(k)$ for an arbitrary permitted $k$, then use that assumption to establish $P(k+1)$.
Example 1
Guided example
Prove by induction that
$$1+2+\cdots+n=\frac{n(n+1)}{2},\qquad n\ge1.$$
Step 1
Base case
Show hint
Start with the smallest integer covered by the statement.
Yes. The permitted range starts at $1$.
$$1=\frac{1(1+1)}{2}=1.$$
Try again. The base case is the first value in the stated domain $n\ge1$.
Reveal the base case
$$1=\frac{1(1+1)}{2}=1.$$
Step 2
Inductive hypothesis
Show hint
Assume one arbitrary case, not every case and not the next case.
Correct. Assume
$$1+2+\cdots+k=\frac{k(k+1)}{2}$$
for an arbitrary integer $k\ge1$.
Not yet. Assume $P(k)$ for one arbitrary permitted $k$; $P(k+1)$ remains to be proved.
Reveal the hypothesis
$$1+2+\cdots+k=\frac{k(k+1)}{2}.$$
Step 3
Inductive step
Show hint
The final term in $P(k)$ is $k$. The next consecutive integer is the new term.
Correct. Now the hypothesis can replace the first $k$ terms.
$$\underbrace{1+2+\cdots+k}_{P(k)}+(k+1).$$
Try again. Move from the sum ending at $k$ to the sum ending at $k+1$.
Reveal the algebra
Start with $P(k+1)$
$$1+2+\cdots+k+(k+1)$$
Apply the hypothesis
$$=\frac{k(k+1)}{2}+(k+1)$$
Factor $k+1$
$$=(k+1)\left(\frac{k}{2}+1\right)$$
Match $P(k+1)$
$$=\frac{(k+1)(k+2)}{2}.$$
This is the original formula with $n$ replaced by $k+1$. Therefore the result holds for every integer $n\ge1$ by mathematical induction.
Check the logic
Which line uses the inductive hypothesis?
Line 2. Here, $1+2+\cdots+k$ is replaced by $\dfrac{k(k+1)}{2}$, which is exactly the inductive hypothesis.
Look for a replacement. Which line exchanges $1+2+\cdots+k$ for the expression supplied by $P(k)$?
Show the key line
Line 2 uses $P(k)$ by substituting $\dfrac{k(k+1)}{2}$ for $1+2+\cdots+k$.
Apply induction
Example 2
Divisibility
Prove that $8^n-1$ is divisible by $7$ for every integer $n\ge1$.
Base case. At $n=1$, $8^1-1=7$, which is divisible by $7$.
Hypothesis. Assume $8^k-1$ is divisible by $7$ for an arbitrary $k\ge1$.
For divisibility proofs, it helps to turn “is divisible by $7$” into an algebraic statement.
$$8^k-1=7m,\qquad m\in\mathbb Z.$$
Try the inductive step first
Rewrite $8^{k+1}-1$ so that the expression $8^k-1$ appears.
Reveal the next algebraic step
Start with $P(k+1)$
$$8^{k+1}-1=8(8^k-1)+7$$
Apply the hypothesis
$$=8(7m)+7$$
Factor $7$
$$=\underbrace{7(8m+1)}_{\text{multiple of }7}.$$
Correct. Because $m$ is an integer, multiplying it by $8$ and then adding $1$ still gives an integer. Therefore $7(8m+1)$ is a multiple of $7$.
Not quite. Use the fact that $m$ was defined to be an integer.
Show reasoning
An integer multiplied by $8$, then increased by $1$, remains an integer.
Conclusion. Therefore $8^n-1$ is divisible by $7$ for every integer $n\ge1$ by mathematical induction.
Example 3
Inequalities
Prove that
$$2^n\ge n+1,\qquad n\ge0.$$
Base case. At $n=0$, $2^0=1$ and $0+1=1$.
Hypothesis. Assume $2^k\ge k+1$ for an arbitrary integer $k\ge0$.
Start with $P(k+1)$
$$2^{k+1}=2\cdot2^k$$
Apply the hypothesis
$$2^{k+1}\ge2(k+1)$$
Show hint
For $P(k+1)$, the right-hand side $n+1$ becomes $(k+1)+1$.
Correct. Compare the expressions by subtracting:
$$2k+2-(k+2)=k\ge0.$$
Thus $2^{k+1}\ge2(k+1)\ge k+2$, which is $P(k+1)$.
Try again. The target for the next case is $2^{k+1}\ge(k+1)+1$.
Reveal the comparison
$$2(k+1)-(k+2)=k\ge0.$$
Conclusion. Therefore $2^n\ge n+1$ for every integer $n\ge0$ by mathematical induction.
Build a proof
Put the proof in order
Arrange the four parts of an induction proof in the correct order.
Use the Move up and Move down controls with a mouse, touch, or keyboard.
Inductive hypothesis
Assume $P(k)$ for an arbitrary permitted $k$.
Base case
Verify $P(n_0)$.
Conclusion
State the integer range proved by induction.
Inductive step
Use $P(k)$ to establish $P(k+1)$.
Show the correct order
Base case → Inductive hypothesis → Inductive step → Conclusion.
Spot the mistake
$P(1)$, $P(2)$, $P(3)$ and $P(4)$ are true, so $P(n)$ is true for every positive integer.
Correct. Checking four cases only proves those four cases. Induction needs a general step showing that $P(k)$ implies $P(k+1)$.
Look at the logic. Four successful cases do not rule out a later counterexample.
Show diagnosis
Only finitely many cases were checked. No link from an arbitrary $P(k)$ to $P(k+1)$ was established.
Exam practice
In the exam
Quick check
Five questions to check that you can set up an induction proof on your own.
Your score is not saved.
Review the answers
$n=1$.
Assume $P(k)$ for an arbitrary permitted $k$.
$2^{k+1}\ge k+2$.
The logical link from $P(k)$ to $P(k+1)$.
$5^{k+1}-1=5(5^k-1)+4=4(5m+1)$.
Summary
Verify the first permitted case $P(n_0)$.
Assume $P(k)$ for one arbitrary permitted integer, then use it explicitly.
Transform the next case until it has exactly the form $P(k+1)$.
Finish by naming the method and the complete integer range proved.
Want to leave a comment?
Log in