Your weak spots

Insights load after your first practice round.

Module 5 · L10 of 20 ~40 min ⚡ +95 XP available

Induction for Divisibility II

The substitution trick from Lesson 9 gets you far, but some divisibility statements — like $7^n - 3^n$ always being divisible by 4 — need a cleverer move. This lesson introduces the add/subtract trick: inserting a cancelling pair of terms to force the inductive hypothesis into view. You will also see why $n^3 - n$ is always divisible by 6, using a beautiful fact about consecutive integers.

Today's hook — Compute $7^n - 3^n$ for $n = 1, 2, 3$. Is the result always a multiple of 4? If so, what do you think is happening algebraically? Jot your calculations now — you'll see the elegant proof after card 05.

0/5QUESTS

Recall — your gut answer first

+5 XP warm-up

Compute $7^n - 3^n$ for $n = 1, 2, 3$. Without algebra — observe whether each result is divisible by 4. Can you see a pattern? What might make $7^n - 3^n$ always produce a multiple of 4?

auto-saved

The add/subtract trick

+5 XP to read

When the inductive hypothesis involves $a^k - b^k$, neither the group-and-extract nor the simple substitution technique from Lesson 9 works cleanly. The solution is to insert a strategically chosen zero — add and subtract the same term — so that the hypothesis appears naturally.

The key identity for $a^{k+1} - b^{k+1}$ is:

$a^{k+1} - b^{k+1}$
$= a \cdot a^k - a \cdot b^k + a \cdot b^k - b \cdot b^k$
$= a(a^k - b^k) + b^k(a - b)$

Here, $a^k - b^k$ is the inductive hypothesis (divisible by $d$), and $a - b$ must also be divisible by $d$ for the second term to cooperate. Both conditions together guarantee $f(k+1)$ is divisible by $d$.

$a^{k+1} - b^{k+1} = a(a^k - b^k) + b^k(a-b)$

Check $a - b$ first

Before using the add/subtract trick, confirm that $a - b$ is divisible by $d$. For $7^n - 3^n$ and $d = 4$: $7 - 3 = 4$ ✓. This is what makes the second term divisible.

$k(k+1)$ is always even

The product of any two consecutive integers is always even. This is because one of the two must be even. Use this fact when proving divisibility by 6 from a factor of $3k(k+1)$.

Divisibility by 6

An integer is divisible by 6 iff it is divisible by both 2 and 3. So showing $2 \mid n$ and $3 \mid n$ is equivalent to showing $6 \mid n$. This can be an alternative proof strategy.

What you'll master

Know

Key facts

The add/subtract identity: $a^{k+1} - b^{k+1} = a(a^k - b^k) + b^k(a-b)$
The product of two consecutive integers $k(k+1)$ is always even
An integer is divisible by 6 iff it is divisible by both 2 and 3

Understand

Concepts

Why "inserting a zero" ($+ab^k - ab^k$) creates the hypothesis term $a(a^k - b^k)$
Why both $a^k - b^k$ being divisible by $d$ AND $a - b$ being divisible by $d$ are required
How to identify when the add/subtract trick is needed versus the techniques from Lesson 9

Can do

Skills

Prove $a^n - b^n$ divisibility statements using the add/subtract technique (e.g., $7^n - 3^n$ divisible by 4)
Use the consecutive integer fact to prove divisibility by 6 (e.g., $n^3 - n$)
Construct and justify a complete, examinable divisibility induction proof

Key terms

Add/subtract trickA technique for handling $a^{k+1} - b^{k+1}$ in the inductive step: insert $+a \cdot b^k - a \cdot b^k = 0$ to create two useful groups.

$a^{k+1} - b^{k+1}$ identity$a^{k+1} - b^{k+1} = a(a^k - b^k) + b^k(a - b)$. The first group contains the hypothesis; the second involves $a - b$.

Consecutive integersTwo integers $k$ and $k+1$ (or $k-1$ and $k$). Their product $k(k+1)$ is always even because one of the pair must be even.

Divisibility by 6$6 \mid n$ iff both $2 \mid n$ and $3 \mid n$. Equivalently, if you can write $n = 6P$ for some integer $P$. Often arises when $3k(k+1)$ appears, since $k(k+1)$ is even.

Even integerAn integer $n$ such that $n = 2N$ for some integer $N$. Always introduce a new integer name (like $N$) when asserting an integer is even mid-proof.

Concluding statementThe final sentence: "By the principle of mathematical induction, the result holds for all $n \geq 1$." Required in every induction proof.

Technique 3: the add/subtract trick for $a^n - b^n$

core concept

When proving that $a^n - b^n$ is divisible by $d$, the simple substitution from Lesson 9 is difficult because the expression involves two exponential terms. Instead, insert $+a \cdot b^k - a \cdot b^k$ (a zero!) to factorise usefully:

$$a^{k+1} - b^{k+1} = a(a^k - b^k) + b^k(a-b)$$

Full worked proof: $7^n - 3^n$ divisible by 4

Prove by induction that $4 \mid (7^n - 3^n)$ for all $n \geq 1$.

Base case ($n=1$): $7^1 - 3^1 = 4 = 4 \times 1$. ✓

Inductive hypothesis: Assume $7^k - 3^k = 4M$ for some integer $M$.

Inductive step: Consider $f(k+1) = 7^{k+1} - 3^{k+1}$.

$= 7 \cdot 7^k - 7 \cdot 3^k + 7 \cdot 3^k - 3 \cdot 3^k$

$= 7(7^k - 3^k) + 3^k(7 - 3)$

$= 7(4M) + 3^k(4) = 4(7M + 3^k)$

Since $7M + 3^k$ is an integer, $f(k+1)$ is divisible by 4. By induction, true for all $n \geq 1$. $\blacksquare$

Why does this work? Note that $7 - 3 = 4$, so the second group $3^k(7-3) = 3^k \cdot 4$ is automatically divisible by 4. The first group uses the hypothesis. Both groups contribute a factor of 4.

When proving that $a^n - b^n$ is divisible by $d$, the simple substitution from Lesson 9 is difficult because the expression involves two exponential terms. Instead, insert $+a \cdot b^k - a \cdot b^k$ (a zero!) to factorise usefully:

Pause — copy the add/subtract trick: $a^{k+1}-b^{k+1}=a(a^k-b^k)+b^k(a-b)$, identifying which hypothesis and residual each term uses into your book.

Quick check: When applying the add/subtract trick to $7^{k+1} - 3^{k+1}$, what term do you add and subtract?

The consecutive integer fact — key to divisibility by 6

core concept

We just saw that to prove $a^n-b^n$ divisible by $(a-b)$, you write $a^{k+1}-b^{k+1}=a(a^k-b^k)+b^k(a-b)$ and apply the hypothesis to the first bracket. That raises a question: for divisibility-by-6, what algebraic fact about consecutive integers removes the need for case analysis? This card answers it → the product of any two consecutive integers $n(n+1)$ is always divisible by 2.

A powerful tool for divisibility-by-6 proofs is the fact that the product of any two consecutive integers is always even.

$$k(k+1) = 2N \text{ for some integer } N$$

This means whenever $3k(k+1)$ appears in a proof, it equals $3 \cdot 2N = 6N$, which is divisible by 6.

Full worked proof: $n^3 - n$ divisible by 6

Prove by induction that $6 \mid (n^3 - n)$ for all $n \geq 1$.

Base case ($n=1$): $1 - 1 = 0 = 6 \times 0$. ✓ (Note: 0 is divisible by every integer.)

Inductive hypothesis: 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 + 3k^2 + 2k$

$= (k^3 - k) + 3k^2 + 3k = 6M + 3k(k+1)$

Since $k(k+1)$ is the product of consecutive integers, it is even: $k(k+1) = 2N$ for some integer $N$.

$= 6M + 3(2N) = 6M + 6N = 6(M + N)$

Since $M + N$ is an integer, $f(k+1)$ is divisible by 6. By induction, true for all $n \geq 1$. $\blacksquare$

Generalisation. The product of any $r$ consecutive integers is divisible by $r!$. In particular: $k(k+1)(k+2)$ is divisible by 6 for all $k$. This is related to the fact that $\binom{k+2}{3}$ is always an integer.

A powerful tool for divisibility-by-6 proofs is the fact that the product of any two consecutive integers is always even .

Pause — copy the consecutive-integer divisibility fact ($n(n+1)$ always even) and show how it closes a divisibility-by-6 inductive step into your book.

Did you get this? True or false: in the induction proof that $n^3 - n$ is divisible by 6, the term $3k(k+1)$ is shown to be divisible by 6 because one of $k$ or $k+1$ is always even.

Worked examples · 3 in a row, reveal as you go

PROBLEM 1 · ADD/SUBTRACT TRICK

Prove by induction that $5^n - 2^n$ is divisible by 3 for all $n \geq 1$.

Base case ($n=1$): $5^1 - 2^1 = 3 = 3 \times 1$. ✓ Note: $5 - 2 = 3$, divisible by 3 — good sign.

Always check that $a - b$ is divisible by $d$ first. Here $5 - 2 = 3$ confirms the trick will work.

PROBLEM 2 · CONSECUTIVE INTEGER FACT

Prove by induction that $n(n+1)(n+2)$ is divisible by 6 for all $n \geq 1$.

Base case ($n=1$): $1 \times 2 \times 3 = 6 = 6 \times 1$. ✓

The product of three consecutive integers starting at 1 is indeed 6.

PROBLEM 3 · EXAM STYLE

Prove by induction that $4^n - 1$ is divisible by 3 for all $n \geq 1$. (HSC-style: write all steps explicitly.)

Step 1 — Base case: When $n = 1$, $4^1 - 1 = 3$. Since $3 = 3 \times 1$, the result is true for $n = 1$.

Write "the result is true for $n = 1$" — not just the arithmetic. Examiners want the explicit statement.

Fill the gap: In the proof that $7^n - 3^n$ is divisible by 4, after applying the add/subtract trick, the inductive step simplifies to $4(7M +$ $)$.

Misconceptions to fix · the 3 traps that cost marks

Trap 01

Assuming $k(k+1)$ is even without justification

When you use the fact that $k(k+1)$ is even, you must state why: "One of $k$ or $k+1$ is even, so $k(k+1)$ is even. Write $k(k+1) = 2N$ for some integer $N$." Simply asserting it is even without explanation will lose a mark in HSC-style marking.

Trap 02

Incorrectly inserting the zero term

The inserted term must match the leading coefficient. For $7^{k+1} - 3^{k+1}$, insert $\pm 7 \cdot 3^k$ (matching the coefficient 7 on the first term). A common error is inserting $\pm 3 \cdot 7^k$ instead, which does not create the hypothesis $7(7^k - 3^k)$.

Trap 03

Skipping the conclusion sentence

Both Lesson 9 and Lesson 10 proofs require the full conclusion: "By the principle of mathematical induction, the statement is true for all integers $n \geq 1$." In HSC marking schemes, this typically carries its own mark. Do not omit it even if you feel the result is obvious from the algebra.

Did you get this? True or false: when applying the add/subtract trick to $7^{k+1} - 3^{k+1}$, the correct term to insert is $+7 \cdot 3^k - 7 \cdot 3^k$.

Work mode · how are you completing this lesson?

Activities · practice with the ideas

Prove by induction that $7^n - 3^n$ is divisible by 4 for all $n \geq 1$. Write all four steps explicitly.

In the add/subtract trick for $5^{k+1} - 2^{k+1}$: what zero do you insert? Write out the two resulting groups.

Prove by induction that $n^3 - n$ is divisible by 6 for all $n \geq 1$. Include the full justification that $k(k+1)$ is even.

Identify the error: "In the proof that $5^n - 2^n$ is divisible by 3, I insert $+2 \cdot 5^k - 2 \cdot 5^k$, giving $2(5^k - 2^k) + 5^k(2-5) = 2(3M) - 3 \cdot 5^k = 3(2M - 5^k)$." Is this approach valid?

Which of the following can be proved using the add/subtract trick? (a) $2^n + 1$ divisible by 3; (b) $6^n - 4^n$ divisible by 2; (c) $n^2 + n$ divisible by 2. For each, state your technique and why.

Odd one out: Three of these steps are from a correct divisibility induction proof. Which one is NOT a valid proof step?

Revisit your thinking

Earlier you computed $7^n - 3^n$ for $n = 1, 2, 3$: you should have found 4, 40, and 316 — all multiples of 4.

The reason is that $7 - 3 = 4$, and this difference cascades through every power. The add/subtract trick makes this precise: $7^{k+1} - 3^{k+1} = 7(7^k - 3^k) + 3^k \cdot 4$. The first group is divisible by 4 (hypothesis); the second group contributes an explicit factor of 4 from $7 - 3$. Did the "inserting a zero" idea make sense? What was most surprising?

auto-saved

Multiple choice

+5 XP per correct · +25 XP all-correct

Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.

Short answer

ApplyBand 31 mark

Q1. State the identity used in the add/subtract trick for $a^{k+1} - b^{k+1}$. (1 mark)

auto-saved

ApplyBand 43 marks

Q2. Prove by induction that $7^n - 3^n$ is divisible by 4 for all $n \geq 1$. (3 marks)

auto-saved

AnalyseBand 53 marks

Q3. Prove by induction that $n^3 - n$ is divisible by 6 for all $n \geq 1$. (3 marks)

auto-saved

Comprehensive answers (click to reveal)

Activity answers:

1. Base: $7-3=4$ ✓. Hypothesis: $7^k-3^k=4M$. Step: $7(4M)+4\cdot 3^k=4(7M+3^k)$. ✓

2. Insert $\pm 5 \cdot 2^k$; Group 1: $5(5^k-2^k)=5(3M)$; Group 2: $2^k(5-2)=3\cdot 2^k$; total $3(5M+2^k)$.

3. $(k+1)^3-(k+1) = (k^3-k)+3k(k+1) = 6M+3(2N) = 6(M+N)$. Key: state $k(k+1)=2N$. ✓

4. The insertion $\pm 2 \cdot 5^k$ is valid — it gives $2(5^k-2^k)+5^k(2-5) = 2(3M)-3\cdot 5^k = 3(2M-5^k)$. Both insertions work here. ✓

5. (a) $2^n+1$ — not $a^n-b^n$ form; use substitution. (b) $6^n-4^n$ — add/subtract; $6-4=2$ ✓. (c) $n^2+n$ — group-and-extract (polynomial).

Q1 (1 mark): $a^{k+1} - b^{k+1} = a(a^k - b^k) + b^k(a-b)$ [1].

Q2 (3 marks): Base: $7-3=4$ ✓ [1]. Hypothesis: $7^k-3^k=4M$ [1]. Step: $7(4M)+3^k \cdot 4 = 4(7M+3^k)$; conclude [1].

Q3 (3 marks): Base: $1-1=0$ ✓ [1]. Hypothesis: $k^3-k=6M$; step: expand and group, show $3k(k+1)=6N$ using consecutive integer fact [1]; $6(M+N)$; conclude [1].

Boss battle · The Add/Subtract Master

earn bronze · silver · gold

Five timed questions. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.

⚔ Enter the arena

Science Jump · platform challenge

Climb platforms by answering divisibility induction questions. Lighter alternative to the boss.

Mark lesson as complete

Tick when you've finished the practice and review.

← Lesson 9 · Induction for Divisibility I Lesson 11 · Induction for Inequalities I →

Module overview · Extension 1 · Checkpoint 2