Proof by mathematical induction - TCE Mathematics Specialised (Tasmania)

Syllabus dot point

“Prove statements for all positive integers using the principle of mathematical induction.”

TCESpecialist MathematicsUnit 39 min readUpdated 2 Jun 2026

Quick answer

Mathematical induction proves a statement $P(n)$ for all integers $n \ge n_0$ in two steps: show the base case $P(n_0)$ is true, then assume $P(k)$ is true and use that assumption to prove $P(k+1)$ . Together these knock down every case like a line of dominoes.

What this dot point is asking

This dot point introduces the first formal proof technique of the course. Induction is the standard way to prove a statement that should hold for every positive integer, such as a formula for a sum, a divisibility fact, or an inequality. The logic is rigorous and the layout is expected to be precise, so examiners reward a clear, conventional structure.

The principle

Principle of mathematical induction

To prove a statement $P(n)$ holds for all integers $n \ge n_0$ :

Base case: prove that $P(n_0)$ is true.
Inductive step: assume $P(k)$ is true for some integer $k \ge n_0$ (the inductive hypothesis), and use this to prove $P(k+1)$ is true.
If both steps hold, then $P(n)$ is true for all $n \ge n_0$ .

The image is a line of dominoes: the base case tips the first one, and the inductive step guarantees that each falling domino tips the next, so they all fall.

Required layout

A complete induction proof should clearly state the proposition $P(n)$ , prove the base case, write down the inductive hypothesis explicitly, perform the inductive step ending at the $P(k+1)$ statement, and finish with a concluding sentence invoking the principle of induction. Missing any of these costs marks even when the algebra is correct.

Proving a summation formula

Prove that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for all integers $n \ge 1$ .

Step 1: State the proposition

Before any calculation, name exactly what $P(n)$ means. A clear statement of the proposition is required by examiners and ensures that you know what you are trying to prove at each stage.

Let $P(n)$ be the statement that the sum of the first $n$ positive integers equals $\tfrac{n(n+1)}{2}$ .

Step 2: Prove the base case

The base case anchors the induction. Without it, the chain of implications has nothing to start from. Check that the formula holds for the smallest value $n = 1$ .

The left side is $1$ and the right side is $\tfrac{1 \cdot 2}{2} = 1$ . Since both sides agree, $P(1)$ is true.

Step 3: State the inductive hypothesis

The inductive hypothesis is the engine of the proof. We explicitly assume $P(k)$ holds for some arbitrary integer $k \ge 1$ ; every step that follows must genuinely use this assumption.

Assume $P(k)$ is true for some $k \ge 1$ , that is:

1 + 2 + \dots + k = \frac{k(k+1)}{2}.

Step 4: Prove the inductive step

We need to show that assuming $P(k)$ forces $P(k+1)$ to be true. The strategy is to write the $(k+1)$ -sum as the $k$ -sum plus one extra term, then apply the inductive hypothesis to replace the $k$ -sum.

Adding $(k+1)$ to both sides of the assumed equation:

1 + 2 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}.

This is exactly the formula with $n = k + 1$ , so $P(k+1)$ is true.

Step 5: State the conclusion

The two steps together complete the induction, and the concluding sentence is a required part of a full proof. Without it, the logical argument is incomplete.

By the principle of mathematical induction, $P(n)$ holds for all integers $n \ge 1$ .

Divisibility proofs

For divisibility, the trick in the inductive step is to write the $k+1$ expression in terms of the $k$ expression, so the inductive hypothesis can be substituted.

Proving a divisibility result

Prove that $3^{2n} - 1$ is divisible by $8$ for all integers $n \ge 1$ .

Step 1: State the proposition

Naming the proposition precisely sets up a clear target for the base case and inductive step. We write divisibility using the notation $8 \mid (\cdot)$ to mean "8 divides".

Let $P(n)$ be the statement that $8 \mid (3^{2n} - 1)$ .

Step 2: Prove the base case

The base case confirms that the divisibility claim is true for the starting value $n = 1$ , giving the induction somewhere to begin.

When $n = 1$ : $3^2 - 1 = 8$ , which is divisible by $8$ . So $P(1)$ is true.

Step 3: State the inductive hypothesis

For a divisibility proof, the inductive hypothesis is most useful when stated by introducing an integer $m$ to represent the quotient. This makes the algebraic manipulation in the next step concrete.

Assume $3^{2k} - 1 = 8m$ for some integer $m$ .

Step 4: Prove the inductive step

We must show $P(k+1)$ , that is $8 \mid (3^{2(k+1)} - 1)$ . The key technique for divisibility is to rewrite the $k+1$ expression so that the $k$ expression (and hence $8m$ ) appears as a factor, allowing the inductive hypothesis to be substituted.

First expand $3^{2(k+1)}$ :

3^{2(k+1)} - 1 = 3^{2k}\cdot 9 - 1 = 9\cdot 3^{2k} - 1.

Now add and subtract $9$ to reveal $3^{2k} - 1$ inside:

3^{2(k+1)} - 1 = 9(3^{2k} - 1) + 9 - 1 = 9(8m) + 8 = 8(9m + 1).

Since $9m + 1$ is an integer, $3^{2(k+1)} - 1$ is divisible by $8$ , so $P(k+1)$ is true.

Step 5: State the conclusion

Both the base case and the inductive step have been established, completing the two requirements of the principle.

By the principle of mathematical induction, $8 \mid (3^{2n} - 1)$ for all integers $n \ge 1$ .

Inequality proofs

Inequalities use the same structure, but the inductive step adds or multiplies by a quantity rather than rearranging to an exact formula. State clearly each direction of inequality used.

The inductive hypothesis must actually be used

A proof is only valid if the inductive step genuinely relies on assuming $P(k)$ . If you can prove $P(k+1)$ from scratch without the hypothesis, you have not done induction, and examiners may not award the structural marks. The hallmark of a correct step is a line where you substitute the assumed $P(k)$ result.

Assuming what you are trying to prove

A frequent error is to assume $P(k+1)$ is true and then verify it, which is circular reasoning. You may only assume $P(k)$ as the hypothesis; $P(k+1)$ is the target you must derive. Keep the roles distinct: $k$ is the assumed case, $k+1$ is the one you build and prove. Always finish with the standard concluding statement citing the principle of induction.

Why this matters

Induction is the rigorous backbone for any result indexed by the positive integers, and the disciplined layout it demands carries over to all proof writing. Mastering the three proof types here, sums, divisibility and inequalities, covers the great majority of induction questions you will meet.

Exam-style questions

Questions in the style of TASC exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

Practice6 marks

Use mathematical induction to prove that

1 \times 3 + 2 \times 3^2 + 3 \times 3^3 + \cdots + n \times 3^n = \dfrac{3}{4}\left[(2n - 1)3^n + 1\right]

for

n \ge 1

Show worked answer →

Let $P(n)$ be the statement that the sum equals $\dfrac{3}{4}\left[(2n - 1)3^n + 1\right]$ .

Base case ( $n = 1$ ): the left side is $1 \times 3 = 3$ and the right side is $\dfrac{3}{4}\left[(2(1) - 1)3^1 + 1\right] = \dfrac{3}{4}[3 + 1] = 3$ . So $P(1)$ is true.

Inductive step: assume $P(k)$ is true, so the sum to $k$ terms equals $\dfrac{3}{4}\left[(2k - 1)3^k + 1\right]$ . Add the $(k+1)$ th term, $(k + 1)3^{k+1}$ , to both sides. The new sum is $\dfrac{3}{4}\left[(2k - 1)3^k + 1\right] + (k + 1)3^{k+1}$ .

Write the $3^k$ term as $\dfrac{1}{4}(2k - 1)3^{k+1}$ and combine over $3^{k+1}$ : $3^{k+1}\left[\dfrac{2k - 1}{4} + (k + 1)\right] = 3^{k+1}\cdot\dfrac{6k + 3}{4} = \dfrac{3}{4}(2k + 1)3^{k+1}$ . With the constant $+\dfrac{3}{4}$ this is $\dfrac{3}{4}\left[(2(k+1) - 1)3^{k+1} + 1\right]$ , which is $P(k+1)$ .

Since $P(1)$ holds and $P(k)$ implies $P(k+1)$ , by induction $P(n)$ is true for all $n \ge 1$ . Markers reward a correct base case, an explicit inductive assumption, and clean algebra reaching the target form.

Practice7 marks

Use mathematical induction to prove that

\dfrac{1}{1\cdot 2\cdot 3} + \dfrac{1}{2\cdot 3\cdot 4} + \cdots + \dfrac{1}{n(n+1)(n+2)} = \dfrac{n(n+3)}{4(n+1)(n+2)}

for

n \ge 1

Show worked answer →

Let $P(n)$ be the given statement.

Base case ( $n = 1$ ): the left side is $\dfrac{1}{1\cdot 2\cdot 3} = \dfrac{1}{6}$ and the right side is $\dfrac{1 \times 4}{4 \times 2 \times 3} = \dfrac{4}{24} = \dfrac{1}{6}$ . So $P(1)$ is true.

Inductive step: assume $P(k)$ , so the sum to $k$ terms is $\dfrac{k(k + 3)}{4(k + 1)(k + 2)}$ . Add the next term $\dfrac{1}{(k + 1)(k + 2)(k + 3)}$ . Over the common denominator $4(k + 1)(k + 2)(k + 3)$ the numerator is $k(k + 3)^2 + 4 = k^3 + 6k^2 + 9k + 4 = (k + 1)^2(k + 4)$ .

So the new sum is $\dfrac{(k + 1)(k + 4)}{4(k + 2)(k + 3)} = \dfrac{(k + 1)\big((k + 1) + 3\big)}{4\big((k + 1) + 1\big)\big((k + 1) + 2\big)}$ , which is $P(k+1)$ .

By the principle of induction $P(n)$ holds for all $n \ge 1$ . The key step markers look for is factorising the cubic numerator to expose the $(k + 1)$ factor.

Practice6 marks

Use mathematical induction to prove that

1^2\cdot 2^1 + 2^2\cdot 2^2 + 3^2\cdot 2^3 + \cdots + n^2\cdot 2^n = 2^{n+1}(n^2 - 2n + 3) - 6

for

n \ge 1

Show worked answer →

Let $P(n)$ be the statement above.

Base case ( $n = 1$ ): the left side is $1^2\cdot 2^1 = 2$ and the right side is $2^2(1 - 2 + 3) - 6 = 4 \times 2 - 6 = 2$ . So $P(1)$ is true.

Inductive step: assume $P(k)$ , so the sum is $2^{k+1}(k^2 - 2k + 3) - 6$ . Add the $(k+1)$ th term $(k + 1)^2\cdot 2^{k+1}$ , giving a new sum $2^{k+1}(k^2 - 2k + 3) - 6 + (k + 1)^2 2^{k+1}$ .

Factor out $2^{k+1}$ : $2^{k+1}\left[k^2 - 2k + 3 + (k + 1)^2\right] - 6 = 2^{k+1}\left[2k^2 + 4\right] - 6 = 2^{k+2}(k^2 + 2) - 6$ .

The target is $2^{k+2}\big((k+1)^2 - 2(k+1) + 3\big) - 6$ , and $(k+1)^2 - 2(k+1) + 3 = k^2 + 2$ , matching exactly. So $P(k+1)$ holds. By induction $P(n)$ is true for all $n \ge 1$ . Markers reward the base case, a stated assumption, and the algebra that collapses $k^2 - 2k + 3 + (k+1)^2$ to $2(k^2 + 2)$ .

Practise this

Sources & how we know this

Mathematics Specialised Level 4 (MTS415118) course document (2018 onwards) — TASC