Induction for Divisibility I
Can you prove that $n^3 + 2n$ is always divisible by 3, no matter which positive integer $n$ you pick? This lesson introduces the key technique for divisibility induction proofs: rewriting $f(k+1)$ so that the inductive hypothesis $f(k)$ appears explicitly, leaving a remainder that is clearly a multiple of the divisor.
Compute $n^3 + 2n$ for $n = 1, 2, 3, 4$. Without using a formal proof — do you always get a multiple of 3? What pattern do you notice? Record your calculations below.
To prove that $f(n)$ is divisible by $d$ for all positive integers $n$, induction follows three essential steps. The hardest — and most important — is the inductive step, where you must force the hypothesis to appear inside $f(k+1)$.
Step 1 — Base Case: Show $f(1)$ is divisible by $d$. Usually a single arithmetic calculation.
Step 2 — Inductive Hypothesis: Assume $f(k) = Md$ for some integer $M$. Always introduce the integer $M$ explicitly — this is what you will substitute later.
Step 3 — Inductive Step: Show $f(k+1)$ is divisible by $d$, using the hypothesis. The goal is to rewrite $f(k+1)$ in the form $d \times (\text{integer})$.
Key facts
- Divisibility definition: $a$ is divisible by $d$ iff $a = Md$ for some integer $M$
- The three-step induction structure for divisibility proofs
- Two standard techniques: group-and-extract, and substitution for exponentials
Concepts
- Why introducing $M$ (not just saying "divisible") enables the algebraic manipulation
- How grouping $f(k+1)$ around $f(k)$ exposes the inductive hypothesis
- Why the final factor must be demonstrated to be an integer
Skills
- Prove polynomial divisibility (e.g., $n^3 + 2n$ divisible by 3)
- Prove exponential divisibility using the substitution method (e.g., $4^n + 14$ divisible by 6)
- Write a complete, examinable divisibility induction proof
For polynomial expressions, expand $f(k+1)$ and group terms so that $f(k)$ appears inside the expression. The remaining terms must then factor out the divisor $d$.
Full worked proof: $n^3 + 2n$ divisible by 3
Prove by induction that $3 \mid (n^3 + 2n)$ for all $n \geq 1$.
Base case ($n=1$): $f(1) = 1 + 2 = 3 = 3 \times 1$. Divisible by 3. ✓
Inductive hypothesis: Assume $f(k) = k^3 + 2k = 3M$ for some integer $M$.
Inductive step: Consider $f(k+1) = (k+1)^3 + 2(k+1)$.
$= k^3 + 3k^2 + 3k + 1 + 2k + 2$
$= \underbrace{(k^3 + 2k)}_{=3M} + 3k^2 + 3k + 3$
$= 3M + 3(k^2 + k + 1) = 3\bigl[M + k^2 + k + 1\bigr]$
Since $M + k^2 + k + 1$ is an integer, $f(k+1)$ is divisible by 3. By induction, true for all $n \geq 1$. $\blacksquare$
For polynomial expressions, expand $f(k+1)$ and group terms so that $f(k)$ appears inside the expression. The remaining terms must then factor out the divisor $d$.
Pause — copy the group-and-extract method: expand $f(k+1)$, reveal $f(k)$ inside, apply hypothesis, handle residual into your book.
Quick check: In the induction proof that $n^3 + 2n$ is divisible by 3, which expression correctly represents the regrouped inductive step?
We just saw that the group-and-extract technique rewrites $f(k+1)$ to expose $f(k)$ inside it, then applies the divisibility hypothesis to that piece and handles the residual separately. That raises a question: when $f(n)$ involves $a^n$, is there a cleaner alternative? This card answers it → yes: solve the hypothesis for $a^k$ and substitute directly into $a^{k+1}=a\cdot a^k$.
When $f(n)$ involves $a^n$, it is often better to solve the hypothesis for $a^k$ and substitute that expression directly into $f(k+1)$. This eliminates $a^k$ from the inductive step and leaves an expression in $M$ alone.
Full worked proof: $4^n + 14$ divisible by 6
Prove by induction that $6 \mid (4^n + 14)$ for all $n \geq 1$.
Base case ($n=1$): $4^1 + 14 = 18 = 3 \times 6$. Divisible by 6. ✓
Inductive hypothesis: Assume $4^k + 14 = 6M$ for some integer $M$, so $4^k = 6M - 14$.
Inductive step: Consider $f(k+1) = 4^{k+1} + 14 = 4 \cdot 4^k + 14$.
Substitute $4^k = 6M - 14$:
$= 4(6M - 14) + 14 = 24M - 56 + 14 = 24M - 42 = 6(4M - 7)$
Since $4M - 7$ is an integer, $f(k+1)$ is divisible by 6. By induction, true for all $n \geq 1$. $\blacksquare$
When $f(n)$ involves $a^n$, it is often better to solve the hypothesis for $a^k$ and substitute that expression directly into $f(k+1)$. This eliminates $a^k$ from the inductive step and leaves an expression in $M$ alone.
Pause — copy the substitution technique for exponential expressions: from the hypothesis express $a^k$ in terms of $d$, substitute into $a^{k+1}=a\cdot a^k$ and simplify into your book.
Did you get this? True or false: when proving $4^n + 14$ is divisible by 6 by induction, you can substitute $4^k = 6M - 14$ into $4^{k+1} + 14$ to obtain $6(4M - 7)$.
Worked examples · 3 in a row, reveal as you go
Prove by induction that $5^n - 1$ is divisible by 4 for all $n \geq 1$.
Prove by induction that $3^{2n} - 1$ is divisible by 8 for all $n \geq 1$.
Prove by induction that $6 \mid (n^3 + 5n)$ for all $n \geq 1$.
Fill the gap: When proving $5^n - 1$ divisible by 4, the inductive hypothesis gives $5^k = 4M +$ , which is then substituted into $5^{k+1} - 1$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: writing "assume $f(k)$ is divisible by $d$" (without introducing an integer $M$) is sufficient for the inductive hypothesis in a divisibility proof.
Activities · practice with the ideas
Prove by induction that $n^3 + 2n$ is divisible by 3 for all $n \geq 1$. Write all four steps.
In the proof that $4^n + 14$ is divisible by 6: what value do you get when you substitute $4^k = 6M - 14$ into $4^{k+1} + 14$? Show the algebra.
Prove that $7^n - 1$ is divisible by 6 for all $n \geq 1$. Use the substitution technique.
Identify and fix the error in this proof step: "Since $f(k)$ is divisible by 5, $f(k+1) = f(k) + 5k = \text{divisible by 5} + 5k$, so $f(k+1)$ is divisible by 5."
Without computing, state which technique (group-and-extract or substitution) you would use for each: (a) $n^2 + n$ divisible by 2; (b) $3^n + 5$ divisible by 2; (c) $n^3 - n$ divisible by 6. Justify your choices.
Odd one out: Three of these statements are correct steps in a divisibility induction proof. Which one is NOT correct?
Earlier you tested $n^3 + 2n$ for $n = 1, 2, 3, 4$. You should have found 3, 12, 33, 72 — all multiples of 3.
The induction proof makes this certain for every positive integer, not just those four values. The key was grouping $(k^3 + 2k)$ inside $f(k+1)$ so that the hypothesis could be applied, leaving $3(k^2 + k + 1)$ as an obviously divisible remainder. Did the algebra click? Where did you find it hardest to follow?
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. State the inductive hypothesis for a proof that $n^3 + 2n$ is divisible by 3. (1 mark)
Q2. Prove by induction that $n^3 + 2n$ is divisible by 3 for all $n \geq 1$. (3 marks)
Q3. Prove by induction that $5^n - 1$ is divisible by 4 for all $n \geq 1$. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Step 1: $n=1$: $1+2=3$ ✓. Step 2: $k^3+2k=3M$. Step 3: $(k+1)^3+2(k+1) = (k^3+2k)+3k^2+3k+3 = 3M+3(k^2+k+1) = 3[M+k^2+k+1]$. ✓
2. $4(6M-14)+14 = 24M-56+14 = 24M-42 = 6(4M-7)$ ✓
3. $7^k=6M+1$. $7^{k+1}-1 = 7(6M+1)-1 = 42M+7-1 = 42M+6 = 6(7M+1)$ ✓
4. Error: "divisible by 5 + 5k" is not valid algebra. Correction: write $f(k)=5M$; then $f(k+1) = 5M + 5k = 5(M+k)$. ✓
5. (a) group-and-extract; (b) substitution; (c) group-and-extract (with consecutive integer trick).
Q1 (1 mark): "Assume that $k^3 + 2k = 3M$ for some integer $M$." [1]
Q2 (3 marks): Base: $f(1)=3$ ✓ [1]. Hypothesis: $k^3+2k=3M$ [1]. Step: $(k^3+2k)+3(k^2+k+1) = 3[M+k^2+k+1]$; conclude [1].
Q3 (3 marks): Base: $5-1=4$ ✓ [1]. Hypothesis: $5^k=4M+1$ [1]. Step: $5(4M+1)-1=20M+4=4(5M+1)$; conclude [1].
Five timed questions. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering divisibility induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.