What does the assumption E of k equals dM mean?

It means you assume that at n = k the expression is exactly d times some integer M, which is what 'divisible by d' means. You then use this by substituting it into the n = k + 1 expression.

How do you prove a result for all odd n by induction?

When a claim holds only for odd n, prove the base case at n = 1 and make the inductive step go from n = k to n = k + 2, so you stay within the odd numbers. The same idea, stepping by two, works for 'all even n'.

How do you rewrite a to the power k plus 1 in an induction proof?

Write a to the k plus 1 as a times a to the k, then replace a to the k using the assumption so the inductive hypothesis appears. This is the key algebraic move for divisibility proofs involving powers.

What is the trick for a to the n minus b to the n divisibility?

Split a to the k plus 1 minus b to the k plus 1 as a times the bracket a to the k minus b to the k, plus a minus b times b to the k. The first part carries the assumption and the second is a multiple of a minus b.

What does the assumption E of k equals dM mean?

It means you assume that at n = k the expression is exactly d times some integer M, which is what 'divisible by d' means. You then use this by substituting it into the n = k + 1 expression.

How do you prove a result for all odd n by induction?

When a claim holds only for odd n, prove the base case at n = 1 and make the inductive step go from n = k to n = k + 2, so you stay within the odd numbers. The same idea, stepping by two, works for 'all even n'.

How do you rewrite a to the power k plus 1 in an induction proof?

Write a to the k plus 1 as a times a to the k, then replace a to the k using the assumption so the inductive hypothesis appears. This is the key algebraic move for divisibility proofs involving powers.

What is the trick for a to the n minus b to the n divisibility?

Split a to the k plus 1 minus b to the k plus 1 as a times the bracket a to the k minus b to the k, plus a minus b times b to the k. The first part carries the assumption and the second is a multiple of a minus b.

Year 12 Maths Extension 1 (2027) Proof

Proof of divisibility by induction

Q: How do you prove divisibility by induction?

Show the base case is divisible by d. Assume the expression at n = k equals d times an integer M. Then rewrite the n = k + 1 expression as a multiple of the n = k expression plus a multiple of d, and factor d out. Finish with a concluding sentence.

Q: Is divisibility by induction in the NSW Extension 1 course?

Yes. NESA outcome ME1-12-01 states that a student uses mathematical induction to prove results involving sums and divisibility. A syllabus example is proving 3 to the n plus 7 to the n is divisible by 10 for all odd n.

20 practice questions 2 video lessons Theory + worked examples

Learn proof of divisibility by mathematical induction for NSW Year 12 Mathematics Extension 1. This method proves that an expression is always divisible by a given number for every positive integer, by checking a base case and then carrying the result to the next case.

You will learn to verify the base case, assume the inductive hypothesis and rearrange the next-case expression to reveal the required factor, then state the conclusion clearly — a core divisibility proof regularly tested in the HSC Extension 1 exam.

Practice 20 questions

Practice questions

Every question with a fully worked solution.

Start practising

Watch 2 video(s)

Proof by Induction Divisibility proofs Watch
Induction Divisibility Watch

Theory

Divisibility proofs by induction show that an expression is always a multiple of some number $d$ . This NSW Year 12 Mathematics Extension 1 topic (NESA outcome ME1-12-01) uses the same base case and inductive step, with one key move: rewrite the $n = k + 1$ expression so the $n = k$ assumption appears, then factor out $d$ .

A divisibility proof by induction shows that an expression $E (n)$ is divisible by a fixed integer $d$ for every $n$ from a starting value onwards. "Divisible by $d$ " means $E (n) = d \times (an integer)$ .

The structure is the same as any induction proof: a base case, an inductive hypothesis (assume $E (k) = d M$ for some integer $M$ ), and an inductive step. What is special is the step: you rewrite $E (k + 1)$ as a multiple of $E (k)$ plus a multiple of $d$ , then factor $d$ out of the whole thing.

If a claim is only true for odd $n$ (or only even $n$ ), the step advances by two — from $n = k$ to $n = k + 2$ — so it stays within the odd (or even) numbers.

NESA link. Part of the Year 12 Proof by mathematical induction focus area. Outcome ME1-12-01 — "uses mathematical induction to prove results involving sums and divisibility" — with MAO-WM-01. The syllabus lists the example: prove $3^{n} + 7^{n}$ is divisible by $10$ for all odd $n$ (worked in Example 3).

The base case and step, phrased for divisibility by

d

Rewrite

E (k + 1)

so both pieces carry a factor of

d

, then take

d

out.

To prove $E (n)$ is divisible by $d$ for all $n \geq n_{0}$ :

Base: E (n_{0}) = d \times (integer) .

Assume: E (k) = d M (M \in Z) .

Step: E (k + 1) = \underset{= a d M}{\underset{⏟}{a E (k)}} + \underset{}{\underset{⏟}{(multiple of d)}} = d \times (integer) .

E (k + 1) = a E (k) + d r = d (a M + r)

Useful algebraic moves

Situation	Rewrite for the step
A power $a^{k + 1}$	$a \cdot a^{k}$ , then substitute $a^{k}$ from $E (k) = d M$
A difference $a^{n} - b^{n}$	$a^{k + 1} - b^{k + 1} = a (a^{k} - b^{k}) + (a - b) b^{k}$
Only for odd (or even) $n$	step $k \to k + 2$ , and prove the correct base case

Key idea. The step only succeeds if the leftover bracket after taking out $d$ is an integer. You must actually use $E (k) = d M$ ; restating the claim proves nothing.

How to prove a divisibility result by induction

Test the base case. Substitute the smallest $n$ and check the value is a multiple of $d$ .
Assume the hypothesis. Write $E (k) = d M$ for some integer $M$ — and rearrange it (e.g. $a^{k} = d M + \dots$ ) ready to substitute.
Rewrite the step. Express $E (k + 1)$ as a multiple of $E (k)$ plus a multiple of $d$ . Substitute $E (k) = d M$ , then factor $d$ out; check the bracket is an integer.
Conclude. State that, by the principle of induction, $E (n)$ is divisible by $d$ for all $n \geq n_{0}$ . (For an odd-only claim, note the step went $k \to k + 2$ .)

Example 1 — A power minus one

Prove

4^{n} - 1

is divisible by

3

for all

n \geq 1

Solution

Base case $(n = 1)$ : $4 - 1 = 3$ , divisible by $3$ .

Assume $4^{k} - 1 = 3 M$ , so $4^{k} = 3 M + 1$ .

Inductive step:

$4^{k + 1} - 1$	$=$	$4 \cdot 4^{k} - 1$
	$=$	$4 (3 M + 1) - 1$
	$=$	$12 M + 3 = 3 (4 M + 1)$

4^{k + 1} - 1 = 3 (4 M + 1)

Divisible by $3$ , so by induction it holds for all $n \geq 1$ .

Example 2 — A difference of powers

Prove

8^{n} - 3^{n}

is divisible by

5

for all

n \geq 1

Solution

Base case $(n = 1)$ : $8 - 3 = 5$ , divisible by $5$ .

Assume $8^{k} - 3^{k} = 5 M$ .

Inductive step: split $8 \cdot 8^{k} - 3 \cdot 3^{k}$ as $8 (8^{k} - 3^{k}) + 5 \cdot 3^{k}$ :

$8^{k + 1} - 3^{k + 1}$	$=$	$8 (8^{k} - 3^{k}) + 5 \cdot 3^{k}$
	$=$	$8 \cdot 5 M + 5 \cdot 3^{k}$
	$=$	$5 (8 M + 3^{k})$

8^{k + 1} - 3^{k + 1} = 5 (8 M + 3^{k})

Divisible by $5$ , so by induction it holds for all $n \geq 1$ .

Example 3 — NESA example (odd n)

Prove

3^{n} + 7^{n}

is divisible by

10

for all odd

n

. (A NESA syllabus example for ME1-12-01.)

Solution

Base case $(n = 1)$ : $3 + 7 = 10$ , divisible by $10$ .

Assume for odd $n = k$ : $3^{k} + 7^{k} = 10 M$ .

Inductive step to the next odd value $n = k + 2$ :

$3^{k + 2} + 7^{k + 2}$	$=$	$9 \cdot 3^{k} + 49 \cdot 7^{k}$
	$=$	$9 (3^{k} + 7^{k}) + 40 \cdot 7^{k}$
	$=$	$9 (10 M) + 40 \cdot 7^{k}$
	$=$	$10 (9 M + 4 \cdot 7^{k})$

3^{k + 2} + 7^{k + 2} = 10 (9 M + 4 \cdot 7^{k})

Divisible by $10$ . Since the base case (odd $n = 1$ ) holds and the step goes odd $\to$ odd, by induction it holds for all odd $n$ .

Example 4 — A polynomial expression

Prove

n^{3} + 2 n

is divisible by

3

for all

n \geq 1

Solution

Base case $(n = 1)$ : $1 + 2 = 3$ , divisible by $3$ .

Assume $k^{3} + 2 k = 3 M$ .

Inductive step: expand $(k + 1)^{3} + 2 (k + 1)$ and group the assumption:

$(k + 1)^{3} + 2 (k + 1)$	$=$	$k^{3} + 3 k^{2} + 3 k + 1 + 2 k + 2$
	$=$	$(k^{3} + 2 k) + 3 (k^{2} + k + 1)$
	$=$	$3 M + 3 (k^{2} + k + 1)$
	$=$	$3 (M + k^{2} + k + 1)$

{(k + 1)}^{3} + 2 (k + 1) = 3 (M + k^{2} + k + 1)

Divisible by $3$ , so by induction it holds for all $n \geq 1$ .

Common pitfalls

Restating instead of using. Write the assumption as

E (k) = d M

and actually substitute it. Simply repeating the claim for

k + 1

is not a proof.

The leftover must be an integer. After taking

d

out of

E (k + 1)

, the remaining bracket has to be a whole number — otherwise you have not shown divisibility.

Odd or even claims. If the statement is only for odd (or even)

n

, step from

k

k + 2

, and make sure your base case is odd (or even).

No concluding sentence. Tie the base case and step together and cite the principle of induction.

Frequently asked questions

How do you prove divisibility by induction?

Check the base case is a multiple of $d$ , assume $E (k) = d M$ , then rewrite $E (k + 1)$ as a multiple of $E (k)$ plus a multiple of $d$ and factor $d$ out.

What does the assumption E(k) = dM mean?

It says that at $n = k$ the expression is exactly $d$ times some integer $M$ — the definition of "divisible by $d$ ". You then substitute it in the step.

How do you do induction for all odd n?

Prove the base case at $n = 1$ and make the inductive step go $k \to k + 2$ , so you move from one odd number to the next. The same trick (step by two) works for all even $n$ .