Proving Divisibility Results
One algebraic manoeuvre — rewriting the assumption as an equation and substituting — unlocks an entire family of exponential and polynomial divisibility proofs.
The divisibility induction technique
To prove $f(n)$ is divisible by a fixed integer $k$ for all $n\geq n_0$: verify the basis case directly; assume $f(k)=k\cdot m$ for some integer $m$ (rewriting the assumption as an equation, not just a statement); then express $f(k+1)$ using this equation, and show the result is $k$ times an integer.
The central manoeuvre in every divisibility induction proof is rewriting $f(k+1)-f(k)$ (or a related combination) so that the assumed divisible quantity $f(k)$ appears explicitly, and can be substituted using the inductive assumption. Practice recognising this pattern — it is the single skill that unlocks this entire question type.
Basis ($n=1$): $8^1-3^1=5=5(1)$, divisible by $5$.
Assumption: assume $8^k-3^k=5m$ for some integer $m$, i.e. $8^k=3^k+5m$.
Inductive step:
Since $3^k+8m$ is an integer, $8^{k+1}-3^{k+1}$ is divisible by $5$.
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so $8^n-3^n$ is divisible by $5$ for all positive integers $n$ by induction.
Basis ($n=1$): $1-1=0$, divisible by $6$ (zero is divisible by every integer).
Assumption: assume $k^3-k=6m$ for some integer $m$.
Inductive step: $(k+1)^3-(k+1)=k^3+3k^2+3k+1-k-1=(k^3-k)+3k^2+3k=6m+3k(k+1)$.
Since $k$ and $k+1$ are consecutive integers, one of them is even, so $k(k+1)$ is always even — write $k(k+1)=2p$ for some integer $p$. Then $3k(k+1)=6p$, giving $6m+6p=6(m+p)$, which is divisible by $6$.
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so $n^3-n$ is divisible by $6$ for all positive integers $n$ by induction.
Divisibility proofs with a coefficient adjustment
Basis ($n=1$): $7+4-2=9=3(3)$, divisible by $3$.
Assumption: assume $7^k+4^k-2=3m$ for some integer $m$, i.e. $7^k=3m-4^k+2$.
Inductive step: $7^{k+1}+4^{k+1}-2=7\cdot7^k+4\cdot4^k-2=7(3m-4^k+2)+4\cdot4^k-2$
$=21m-7\cdot4^k+14+4\cdot4^k-2=21m-3\cdot4^k+12=3(7m-4^k+4)$.
Since $7m-4^k+4$ is an integer, this is divisible by $3$.
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$ by induction.
Basis ($n=1$): $5^2-1=24$, divisible by $24$.
Assumption: assume $5^{2k}-1=24m$ for some integer $m$, i.e. $5^{2k}=24m+1$.
Inductive step: $5^{2(k+1)}-1=25\cdot5^{2k}-1=25(24m+1)-1=600m+25-1=600m+24=24(25m+1)$.
Since $25m+1$ is an integer, this is divisible by $24$.
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$ by induction.
Forgetting to rewrite the inductive assumption as an equation (e.g. $8^k=3^k+5m$, not just "$8^k-3^k$ is divisible by 5") makes it impossible to substitute cleanly into the $(k+1)$ expression — always isolate one term this way before starting the inductive step.
A harder case: two exponential terms with different bases
When $f(n)$ combines two exponential terms with different bases (e.g. $a^n$ and $b^n$), isolating a single power and substituting can leave a messy expression. It is often cleaner to write $f(k+1)$ as a constant multiple of $f(k)$ plus a leftover term, i.e. $f(k+1)=c\cdot f(k)+(\text{a multiple of the divisor})$, then argue that both parts of this sum are divisible by the required integer.
Basis ($n=1$): $4^3+3^3=64+27=91=13(7)$, divisible by $13$.
Assumption: assume $f(k)=4^{2k+1}+3^{k+2}=13m$ for some integer $m$.
Inductive step: write $f(k+1)=4^{2k+3}+3^{k+3}$, and express each term as a multiple of the corresponding term in $f(k)$:
Both $16f(k)=16(13m)$ and $13(3^{k+2})$ are divisible by $13$, so their difference $f(k+1)=16(13m)-13(3^{k+2})=13\big(16m-3^{k+2}\big)$ is divisible by $13$, since $16m-3^{k+2}$ is an integer.
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so $4^{2n+1}+3^{n+2}$ is divisible by $13$ for all positive integers $n$ by induction.
Exam-style questions
Question 1 6 marks
Prove by induction that $3^{2n}-1$ is divisible by $8$ for all positive integers $n$.
Basis ($n=1$): $3^2-1=8$, divisible by $8$. (B1)
Assumption: assume $3^{2k}-1=8m$, i.e. $3^{2k}=8m+1$. (M1)
Inductive step: $3^{2(k+1)}-1=9\cdot3^{2k}-1=9(8m+1)-1=72m+8=8(9m+1)$ (M1, A1)
Divisible by $8$ since $9m+1$ is an integer. (A1)
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$. (B1)
Question 2 6 marks
Prove by induction that $2^{3n}-1$ is divisible by $7$ for all positive integers $n$.
Basis ($n=1$): $2^3-1=7$, divisible by $7$. (B1)
Assumption: assume $2^{3k}-1=7m$, i.e. $2^{3k}=7m+1$. (M1)
Inductive step: $2^{3(k+1)}-1=8\cdot2^{3k}-1=8(7m+1)-1=56m+7=7(8m+1)$ (M1, A1)
Divisible by $7$ since $8m+1$ is an integer. (A1)
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$. (B1)
Question 3 7 marks
Prove by induction that $n(n+1)(n+2)$ is divisible by $6$ for all positive integers $n$.
Basis ($n=1$): $1(2)(3)=6$, divisible by $6$. (B1)
Assumption: assume $k(k+1)(k+2)=6m$ for some integer $m$. (M1)
Inductive step: $(k+1)(k+2)(k+3)=k(k+1)(k+2)+3(k+1)(k+2)$ (M1, A1)
$=6m+3(k+1)(k+2)$. Since $(k+1)$ and $(k+2)$ are consecutive integers, their product is even, so $(k+1)(k+2)=2p$ for some integer $p$. (M1)
$=6m+6p=6(m+p)$, divisible by $6$. (A1)
Conclusion: true for $n=1$; true for $n=k+1$ whenever true for $n=k$; so true for all positive integers $n$. (B1)