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 proofdo 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 confidencethat 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.