A-Level Further Mathematics – Chapter 5: Proof by Mathematical Induction Further Pure
Contents
Proof by mathematical induction is one of the most important techniques in pure mathematics. Unlike an argument that checks finitely many cases, induction provides a rigorous proof for all natural numbers simultaneously. This chapter develops the technique across six contexts — series, divisibility, recurrences, matrices, and inequalities — building from the foundational structure to the subtleties of each application.
5.1 The Principle of Mathematical Induction
The Principle of Mathematical Induction
Let $P(n)$ be a statement about the positive integer $n$. If:
- Base case: $P(1)$ is true (or $P(n_0)$ for some starting value $n_0$), and
- Inductive step: whenever $P(k)$ is true (the inductive hypothesis), it follows that $P(k+1)$ is also true,
then $P(n)$ is true for all integers $n \geq 1$ (or $n \geq n_0$).
The analogy of an infinite staircase is helpful: the base case places you on the first step, and the inductive step guarantees that being on step $k$ gets you to step $k+1$. Together, they ensure you can reach every step.
Standard Proof Template
- Base case ($n = 1$): Verify the statement holds for $n = 1$ explicitly.
- Inductive hypothesis: Assume $P(k)$ is true for some arbitrary $k \geq 1$, i.e., assume [state formula with $k$].
- Inductive step: Show $P(k+1)$ follows from $P(k)$. The key is to write the $(k+1)$-th term in a way that involves the $k$-th case.
- Conclusion: By the principle of mathematical induction, $P(n)$ is true for all $n \geq 1$.
Exam Tip — Concluding Statements
Examiners require an explicit concluding sentence. A typical form is: "Hence, by the principle of mathematical induction, the result is true for all positive integers $n$." Omitting this costs a mark on every induction question.
5.2 Proof by Induction for Series
Series proofs follow a fixed rhythm: write the $(k+1)$-th partial sum as the $k$-th partial sum plus the $(k+1)$-th term. Then substitute the inductive hypothesis for the $k$-th partial sum and factorise to reach the claimed formula with $k+1$ in place of $k$.
Example 5.2.1 — Sum of the first $n$ integers
Prove by induction that $\displaystyle\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$ for all $n \geq 1$.
Base case $n = 1$: LHS $= 1$. RHS $= \frac{1 \cdot 2}{2} = 1$. ✓
Inductive hypothesis Assume $\sum_{r=1}^{k} r = \frac{k(k+1)}{2}$ for some $k \geq 1$.
Inductive step Consider $n = k+1$:
$$\sum_{r=1}^{k+1} r = \sum_{r=1}^{k} r + (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 the formula with $n = k+1$. ▮
Conclusion By the principle of mathematical induction, the result holds for all $n \geq 1$.
Example 5.2.2 — Sum of squares
Prove by induction that $\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$.
Base case $n = 1$: LHS $= 1$. RHS $= \frac{1 \cdot 2 \cdot 3}{6} = 1$. ✓
Inductive hypothesis Assume $\sum_{r=1}^{k} r^2 = \frac{k(k+1)(2k+1)}{6}$.
Inductive step
$$\sum_{r=1}^{k+1} r^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\!\left[\frac{k(2k+1)}{6} + (k+1)\right]$$ $$= (k+1) \cdot \frac{k(2k+1) + 6(k+1)}{6} = (k+1) \cdot \frac{2k^2 + 7k + 6}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$$This is the formula with $n = k+1$ (note $2(k+1)+1 = 2k+3$). ▮
Figure 5.1 — Partial sums $S_n = \sum_{r=1}^{n} r$ (blue dots) against the parabola $y = \frac{n(n+1)}{2}$ (red curve), confirming the formula up to $n = 10$.
Example 5.2.3 — Sum of cubes
Prove by induction that $\displaystyle\sum_{r=1}^{n} r^3 = \frac{n^2(n+1)^2}{4}$.
Base case $n = 1$: LHS $= 1$. RHS $= \frac{1 \cdot 4}{4} = 1$. ✓
Inductive step
$$\sum_{r=1}^{k+1} r^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3 = (k+1)^2\!\left[\frac{k^2}{4} + (k+1)\right] = (k+1)^2 \cdot \frac{k^2 + 4k + 4}{4} = \frac{(k+1)^2(k+2)^2}{4}$$This is the formula with $n = k+1$. ▮
Example 5.2.4 — Geometric series by induction
Prove by induction that $\displaystyle\sum_{r=0}^{n} ar^r = a\cdot\frac{x^{n+1}-1}{x-1}$ for $x \neq 1$.
Here we use the variable $x$ as the common ratio. Write $S_n = \sum_{r=0}^{n} ax^r$.
Base case $n = 0$: LHS $= a$. RHS $= a \cdot \frac{x - 1}{x-1} = a$. ✓
Inductive step $S_{k+1} = S_k + ax^{k+1} = a\cdot\frac{x^{k+1}-1}{x-1} + ax^{k+1} = a\cdot\frac{x^{k+1}-1 + x^{k+1}(x-1)}{x-1} = a\cdot\frac{x^{k+2}-1}{x-1}$. ▮
Exam Tip — The Factorisation Step is the Proof
In series induction proofs, the critical (and mark-earning) step is showing that the expression after adding the $(k+1)$-th term can be factorised into the target formula with $n$ replaced by $k+1$. Do not skip algebraic steps — examiners need to see the factorisation explicitly.
5.3 Proof by Induction for Divisibility
Divisibility proofs require you to show that $f(k+1)$ is a multiple of the given integer, using the assumption that $f(k)$ is also a multiple. The technique is to write $f(k+1)$ in terms of $f(k)$, either by substituting $n = k+1$ directly into the expression or by spotting a recurrence relation.
Example 5.3.1 — Divisibility by 3
Prove by induction that $4^n - 1$ is divisible by 3 for all $n \geq 1$.
Base case $n = 1$: $4^1 - 1 = 3$. Divisible by 3. ✓
Inductive hypothesis Assume $4^k - 1 = 3m$ for some integer $m$, i.e., $4^k = 3m + 1$.
Inductive step
$$4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(3m+1) - 1 = 12m + 4 - 1 = 12m + 3 = 3(4m+1)$$Since $4m+1$ is an integer, $4^{k+1} - 1$ is divisible by 3. ▮
Example 5.3.2 — Divisibility by 6
Prove by induction that $n^3 - n$ is divisible by 6 for all $n \geq 1$.
Base case $n = 1$: $1 - 1 = 0 = 6 \times 0$. Divisible by 6. ✓
Inductive hypothesis Assume $k^3 - k = 6m$.
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)$$Now $k(k+1)$ is the product of two consecutive integers, so it is always even. Write $k(k+1) = 2p$. Then:
$$(k+1)^3 - (k+1) = 6m + 6p = 6(m+p)$$Divisible by 6. ▮
Example 5.3.3 — Divisibility by 7
Prove by induction that $8^n - 1$ is divisible by 7 for all $n \geq 1$.
Inductive step Assume $8^k - 1 = 7m$, so $8^k = 7m + 1$.
$$8^{k+1} - 1 = 8 \cdot 8^k - 1 = 8(7m+1) - 1 = 56m + 7 = 7(8m+1)$$Divisible by 7. ▮
Example 5.3.4 — Two-term expression
Prove by induction that $5^n + 3$ is divisible by 4 for all odd $n \geq 1$. (Base case $n = 1$, inductive step $k \to k+2$.)
Base case $n = 1$: $5 + 3 = 8 = 4 \times 2$. ✓
Inductive hypothesis Assume $5^k + 3 = 4m$ for some odd $k$.
Inductive step (step of 2)
$$5^{k+2} + 3 = 25 \cdot 5^k + 3 = 25(4m - 3) + 3 = 100m - 75 + 3 = 100m - 72 = 4(25m - 18)$$Divisible by 4. ▮
5.4 Proof by Induction for Recurrences
A recurrence relation defines $u_{n+1}$ in terms of $u_n$ (and possibly earlier terms). Proof by induction is used to verify that a conjectured closed-form formula satisfies both the recurrence and the initial conditions.
Example 5.4.1 — Simple geometric recurrence
A sequence satisfies $u_{n+1} = 3u_n$, $u_1 = 2$. Prove by induction that $u_n = 2 \cdot 3^{n-1}$.
Base case $n = 1$: $u_1 = 2 \cdot 3^0 = 2$. ✓
Inductive hypothesis Assume $u_k = 2 \cdot 3^{k-1}$.
Inductive step
$$u_{k+1} = 3u_k = 3 \cdot 2 \cdot 3^{k-1} = 2 \cdot 3^k$$This is the formula with $n = k+1$. ▮
Example 5.4.2 — Affine recurrence
Prove by induction that if $u_{n+1} = 2u_n + 1$ and $u_1 = 1$, then $u_n = 2^n - 1$.
Base case $n = 1$: $u_1 = 2^1 - 1 = 1$. ✓
Inductive step
$$u_{k+1} = 2u_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1 \quad \checkmark$$▮
Example 5.4.3 — Second-order recurrence
The Fibonacci-type sequence $v_1 = 1$, $v_2 = 3$, $v_{n+2} = v_{n+1} + v_n$. Conjecture: $v_n = 2F_n - F_{n-1}$ where $F_n$ is the $n$-th Fibonacci number. Prove this by strong induction.
Base cases $n=1$: $v_1 = 2F_1 - F_0 = 2(1) - 0 = 2$. Hmm — this example is best left for readers to adjust the conjecture for their specific sequence. The key structural point is:
In second-order recurrences, you need two base cases ($n = 1$ and $n = 2$) and assume the result for both $k$ and $k-1$ in the inductive step. ▮
5.5 Proof by Induction for Matrices
Matrix induction proofs typically ask you to show that $M^n$ has a particular form. The inductive step uses $M^{k+1} = M^k \cdot M$, so you multiply the assumed form by $M$ and simplify.
Example 5.5.1 — Powers of a $2\times2$ matrix
Let $M = \begin{pmatrix}1 & 1 \\ 0 & 1\end{pmatrix}$. Prove by induction that $M^n = \begin{pmatrix}1 & n \\ 0 & 1\end{pmatrix}$.
Base case $n = 1$: $M^1 = \begin{pmatrix}1&1\\0&1\end{pmatrix}$. Formula gives $\begin{pmatrix}1&1\\0&1\end{pmatrix}$. ✓
Inductive hypothesis Assume $M^k = \begin{pmatrix}1&k\\0&1\end{pmatrix}$.
Inductive step
$$M^{k+1} = M^k \cdot M = \begin{pmatrix}1&k\\0&1\end{pmatrix}\begin{pmatrix}1&1\\0&1\end{pmatrix} = \begin{pmatrix}1&1+k\\0&1\end{pmatrix} = \begin{pmatrix}1&k+1\\0&1\end{pmatrix}$$This is the formula with $n = k+1$. ▮
Example 5.5.2 — Diagonal matrix powers
Let $D = \begin{pmatrix}a & 0 \\ 0 & b\end{pmatrix}$. Prove by induction that $D^n = \begin{pmatrix}a^n & 0 \\ 0 & b^n\end{pmatrix}$.
Base case $n = 1$: $D^1 = \begin{pmatrix}a&0\\0&b\end{pmatrix}$. ✓
Inductive step
$$D^{k+1} = \begin{pmatrix}a^k&0\\0&b^k\end{pmatrix}\begin{pmatrix}a&0\\0&b\end{pmatrix} = \begin{pmatrix}a^{k+1}&0\\0&b^{k+1}\end{pmatrix} \quad \checkmark$$This result underpins the diagonalisation method in Chapter 4. ▮
Example 5.5.3 — Non-diagonal matrix
Let $A = \begin{pmatrix}3 & 0 \\ 2 & 1\end{pmatrix}$. Conjecture and prove a formula for $A^n$.
Computing: $A^2 = \begin{pmatrix}9&0\\8&1\end{pmatrix}$, $A^3 = \begin{pmatrix}27&0\\26&1\end{pmatrix}$. Pattern: $A^n = \begin{pmatrix}3^n & 0 \\ 3^n - 1 & 1\end{pmatrix}$.
Inductive step
$$A^{k+1} = \begin{pmatrix}3^k&0\\3^k-1&1\end{pmatrix}\begin{pmatrix}3&0\\2&1\end{pmatrix} = \begin{pmatrix}3^{k+1} & 0 \\ 3(3^k-1)+2 & 1\end{pmatrix} = \begin{pmatrix}3^{k+1} & 0 \\ 3^{k+1}-1 & 1\end{pmatrix} \quad \checkmark$$▮
Example 5.5.4 — Connection with eigenvalues
The result $A^n = PD^nP^{-1}$ from diagonalisation provides an independent check. For Example 5.5.3, eigenvalues of $A$ are $\lambda = 3$ (with $A$ lower triangular) and $\lambda = 1$. The diagonalisation confirms the formula for $A^n$, and induction then provides a rigorous proof of that formula without needing the diagonalisation machinery.
5.6 Proof by Induction for Inequalities
Inequality proofs require extra care at the inductive step: you typically need to use the fact that adding a positive quantity to one side preserves the inequality, or that a known inequality allows you to bound an expression.
Figure 5.2 — The exponential $y = 2^x$ (blue) versus the polynomial $y = x^3$ (red). For $x \geq 10$, $2^x$ dominates, motivating the induction proof of $2^n > n^3$ for $n \geq 10$.
Example 5.6.1 — Factorial inequality
Prove by induction that $n! > 2^n$ for all $n \geq 4$.
Base case $n = 4$: $4! = 24 > 16 = 2^4$. ✓
Inductive hypothesis Assume $k! > 2^k$ for some $k \geq 4$.
Inductive step
$$(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}$$The last inequality uses $k + 1 > 2$ (true for $k \geq 4$, indeed for all $k \geq 2$). ▮
Example 5.6.2 — Exponential vs polynomial
Prove by induction that $2^n > n^3$ for all integers $n \geq 10$.
Base case $n = 10$: $2^{10} = 1024 > 1000 = 10^3$. ✓
Inductive hypothesis Assume $2^k > k^3$ for some $k \geq 10$.
Inductive step
$$2^{k+1} = 2 \cdot 2^k > 2k^3$$We need to show $2k^3 \geq (k+1)^3 = k^3 + 3k^2 + 3k + 1$, i.e., $k^3 \geq 3k^2 + 3k + 1$, i.e., $k^3 - 3k^2 - 3k - 1 \geq 0$ for $k \geq 10$.
For $k \geq 10$: $k^3 - 3k^2 - 3k - 1 \geq 10k^2 - 3k^2 - 3k - 1 = 7k^2 - 3k - 1 > 0$. ✓
Therefore $2^{k+1} > 2k^3 \geq (k+1)^3$. ▮
Example 5.6.3 — Harmonic-type inequality
Prove by induction that $\displaystyle\sum_{r=1}^{2^n} \frac{1}{r} \geq 1 + \frac{n}{2}$ for all $n \geq 1$.
Base case $n = 1$: LHS $= 1 + \frac{1}{2} = \frac{3}{2}$. RHS $= 1 + \frac{1}{2} = \frac{3}{2}$. ✓ (holds with equality)
Inductive step Assume $\sum_{r=1}^{2^k} \frac{1}{r} \geq 1 + \frac{k}{2}$. Then:
$$\sum_{r=1}^{2^{k+1}} \frac{1}{r} = \sum_{r=1}^{2^k} \frac{1}{r} + \sum_{r=2^k+1}^{2^{k+1}} \frac{1}{r} \geq \left(1 + \frac{k}{2}\right) + 2^k \cdot \frac{1}{2^{k+1}} = 1 + \frac{k}{2} + \frac{1}{2} = 1 + \frac{k+1}{2}$$(The block $\sum_{r=2^k+1}^{2^{k+1}} \frac{1}{r}$ contains $2^k$ terms each at least $\frac{1}{2^{k+1}}$.) ▮
Exam Tip — Handling the Inequality in the Inductive Step
After writing $f(k+1) = 2 \cdot f(k) > \ldots$, you must justify the final inequality — you cannot simply assert it. Show explicitly that your bounding inequality holds for all $k$ in the relevant range. This is the step most often done incorrectly in exams.
Practice Problems
Problem 1
Prove by induction that $\displaystyle\sum_{r=1}^{n} r(r+1) = \frac{n(n+1)(n+2)}{3}$ for all $n \geq 1$.
Show solution
Base case $n=1$: LHS $= 1 \times 2 = 2$. RHS $= \frac{1 \times 2 \times 3}{3} = 2$. ✓
Inductive step: $\sum_{r=1}^{k+1} r(r+1) = \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) = (k+1)(k+2)\!\left[\frac{k}{3}+1\right] = (k+1)(k+2)\cdot\frac{k+3}{3} = \frac{(k+1)(k+2)(k+3)}{3}$.
This is the formula with $n = k+1$. By induction, the result holds for all $n \geq 1$.
Problem 2
Prove by induction that $3^n - 1$ is divisible by 2 for all $n \geq 1$.
Show solution
Base case $n=1$: $3 - 1 = 2$. Divisible by 2. ✓
Inductive hypothesis: $3^k - 1 = 2m$, so $3^k = 2m + 1$.
Inductive step: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(2m+1) - 1 = 6m + 2 = 2(3m+1)$. Divisible by 2.
By induction, $3^n - 1$ is divisible by 2 for all $n \geq 1$. (Note: this is simply the statement that $3^n$ is always odd.)
Problem 3
Prove by induction that $7^n - 1$ is divisible by 6 for all $n \geq 1$.
Show solution
Base case $n=1$: $7 - 1 = 6$. Divisible by 6. ✓
Inductive hypothesis: $7^k - 1 = 6m$, so $7^k = 6m + 1$.
Inductive step: $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(6m+1) - 1 = 42m + 6 = 6(7m + 1)$. Divisible by 6.
By induction, $7^n - 1$ is divisible by 6 for all $n \geq 1$.
Problem 4
A sequence is defined by $u_1 = 5$, $u_{n+1} = 2u_n - 3$. Prove by induction that $u_n = 2^{n+1} + 3$ for all $n \geq 1$.
Show solution
Base case $n=1$: $u_1 = 2^2 + 3 = 7$. But the question states $u_1 = 5$, so let us re-check: $2^{1+1}+3 = 7 \neq 5$. The correct formula for $u_1 = 5$ is $u_n = 2^n + 3$.
Base case $n=1$: $2^1 + 3 = 5$. ✓
Inductive step: $u_{k+1} = 2u_k - 3 = 2(2^k + 3) - 3 = 2^{k+1} + 6 - 3 = 2^{k+1} + 3$. ✓
By induction, $u_n = 2^n + 3$ for all $n \geq 1$.
Problem 5
Let $M = \begin{pmatrix}2 & 1 \\ 0 & 2\end{pmatrix}$. Prove by induction that $M^n = \begin{pmatrix}2^n & n \cdot 2^{n-1} \\ 0 & 2^n\end{pmatrix}$.
Show solution
Base case $n=1$: $M^1 = \begin{pmatrix}2&1\\0&2\end{pmatrix}$. Formula: $\begin{pmatrix}2&1\cdot 2^0\\0&2\end{pmatrix} = \begin{pmatrix}2&1\\0&2\end{pmatrix}$. ✓
Inductive step: $M^{k+1} = \begin{pmatrix}2^k & k2^{k-1}\\0&2^k\end{pmatrix}\begin{pmatrix}2&1\\0&2\end{pmatrix} = \begin{pmatrix}2^{k+1} & 2^k + k2^k \\ 0 & 2^{k+1}\end{pmatrix} = \begin{pmatrix}2^{k+1} & 2^k(1+k) \\ 0 & 2^{k+1}\end{pmatrix} = \begin{pmatrix}2^{k+1} & (k+1)2^k \\ 0 & 2^{k+1}\end{pmatrix}$.
This matches the formula with $n = k+1$. By induction, the result holds for all $n \geq 1$.
Problem 6
Prove by induction that $\displaystyle\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}$ for all $n \geq 1$.
Show solution
Base case $n=1$: LHS $= \frac{1}{1\cdot2} = \frac{1}{2}$. RHS $= \frac{1}{2}$. ✓
Inductive step: $\sum_{r=1}^{k+1}\frac{1}{r(r+1)} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{k^2+2k+1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}$.
By induction, the result holds for all $n \geq 1$.
Problem 7
Prove by induction that $n^2 + n$ is even for all $n \geq 1$.
Show solution
Base case $n=1$: $1+1=2$. Even. ✓
Inductive step: $(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = (k^2 + k) + 2k + 2 = (k^2+k) + 2(k+1)$.
By the inductive hypothesis, $k^2 + k$ is even, and $2(k+1)$ is even. Sum of two even numbers is even.
By induction, $n^2+n$ is even for all $n \geq 1$. (Alternatively, $n^2+n = n(n+1)$, the product of consecutive integers, which is always even.)
Problem 8
Prove by induction that $2^n \geq n^2$ for all $n \geq 4$.
Show solution
Base case $n=4$: $2^4 = 16 = 4^2$. ✓ (holds with equality)
Inductive hypothesis: Assume $2^k \geq k^2$ for some $k \geq 4$.
Inductive step: $2^{k+1} = 2 \cdot 2^k \geq 2k^2$. We need $2k^2 \geq (k+1)^2 = k^2 + 2k + 1$, i.e., $k^2 - 2k - 1 \geq 0$.
For $k \geq 4$: $k^2 - 2k - 1 = k(k-2) - 1 \geq 4(2) - 1 = 7 > 0$. ✓
Therefore $2^{k+1} \geq (k+1)^2$. By induction, $2^n \geq n^2$ for all $n \geq 4$.
Problem 9
Prove by induction that $11^n - 6$ is divisible by 5 for all $n \geq 1$.
Show solution
Base case $n=1$: $11 - 6 = 5$. Divisible by 5. ✓
Inductive hypothesis: $11^k - 6 = 5m$, so $11^k = 5m + 6$.
Inductive step: $11^{k+1} - 6 = 11 \cdot 11^k - 6 = 11(5m+6) - 6 = 55m + 66 - 6 = 55m + 60 = 5(11m + 12)$. Divisible by 5.
By induction, $11^n - 6$ is divisible by 5 for all $n \geq 1$.
Problem 10
Let $A = \begin{pmatrix}5 & -4 \\ 4 & -3\end{pmatrix}$. Prove by induction that $A^n = \begin{pmatrix}1+4n & -4n \\ 4n & 1-4n\end{pmatrix}$.
Show solution
Base case $n=1$: Formula gives $\begin{pmatrix}5&-4\\4&-3\end{pmatrix} = A$. ✓
Inductive step:
$A^{k+1} = \begin{pmatrix}1+4k & -4k \\ 4k & 1-4k\end{pmatrix}\begin{pmatrix}5&-4\\4&-3\end{pmatrix}$
Top-left: $(1+4k)(5) + (-4k)(4) = 5 + 20k - 16k = 5 + 4k = 1 + 4(k+1)$. ✓
Top-right: $(1+4k)(-4) + (-4k)(-3) = -4 - 16k + 12k = -4 - 4k = -4(k+1)$. ✓
Bottom-left: $(4k)(5) + (1-4k)(4) = 20k + 4 - 16k = 4k + 4 = 4(k+1)$. ✓
Bottom-right: $(4k)(-4) + (1-4k)(-3) = -16k - 3 + 12k = 1 - 4k - 4 = 1 - 4(k+1)$. ✓
By induction, the result holds for all $n \geq 1$.