Proof

Introduction to Proof by Mathematical Induction

Welcome to one of the most powerful and elegant topics in Further Mathematics: Proof by Mathematical Induction! In pure mathematics, observing that a pattern works for the first few numbers isn't enough to guarantee it works forever. We need iron-clad certainty. Mathematical induction gives us a way to prove that a mathematical statement is true for all positive integers \(n \ge 1\).

Don't worry if the idea of mathematical proof sounds intimidating at first. Induction follows a very structured, step-by-step recipe that you can master with practice!

The Domino Analogy

Imagine an infinitely long line of dominoes standing on end:

• Base Case: You knock over the 1st domino.
• Inductive Step: You ensure that whenever any domino (say, the \(k\)-th domino) falls, it is guaranteed to knock over the next domino (the \((k+1)\)-th domino).

What happens to the entire line? Every single domino falls! That is precisely how mathematical induction works.

Did You Know? The earliest known implicit use of mathematical induction appears in the work of the Persian mathematician Al-Karaji around 1000 AD, who used it to prove the binomial theorem and sums of integral cubes!

Key Takeaway: Induction proves a rule for infinite cases by proving two things: it starts at the beginning (\(n=1\)), and the truth of any step guarantees the truth of the very next step (\(n=k \implies n=k+1\)).

The 4 Essential Steps of Proof by Induction

Every proof by mathematical induction for CCEA A2 Further Mathematics must follow these four clear steps. Memorize this structure!

Step 1: The Base Case (The First Domino)
Show that the statement is true for the smallest allowed value of \(n\) (usually \(n = 1\)). Substitute \(n = 1\) into both the left-hand side (LHS) and the right-hand side (RHS), and show they are equal.

Step 2: The Inductive Hypothesis (The Assumption)
State clearly: "Assume the statement is true for \(n = k\), where \(k \ge 1\) is an integer." Write down what the formula looks like when you replace \(n\) with \(k\).

Step 3: The Inductive Step (The Chain Reaction)
Using your assumption from Step 2, prove that the statement must also be true for \(n = k + 1\). This is where the algebraic heavy lifting happens!

Step 4: The Golden Conclusion
Exam boards require a complete concluding sentence. Write:
"Since the statement is true for \(n = 1\), and if true for \(n = k\) it is shown to be true for \(n = k + 1\), the statement is true for all positive integers \(n \ge 1\) by mathematical induction."

Memory Aid (B-A-S-C):
• Base case (\(n=1\))
• Assume for \(n=k\)
• Show for \(n=k+1\)
• Conclude clearly

Type 1: Summation of Series

In this classic question type, you are asked to prove a formula for the sum of a sequence of terms up to \(n\).

Worked Example: Sum of Squares

Prove by mathematical induction that for all integers \(n \ge 1\):
\(\sum_{r=1}^{n} r^2 = 1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{1}{6}n(n+1)(2n+1)\)

Step 1: Base Case (\(n = 1\))
LHS: \(\sum_{r=1}^{1} r^2 = 1^2 = 1\)
RHS: \(\frac{1}{6}(1)(1+1)(2(1)+1) = \frac{1}{6}(1)(2)(3) = 1\)
Since \(\text{LHS} = \text{RHS}\), the statement is true for \(n = 1\).

Step 2: Inductive Hypothesis
Assume the statement is true for \(n = k\), so:
\(\sum_{r=1}^{k} r^2 = \frac{1}{6}k(k+1)(2k+1)\)

Step 3: Inductive Step (\(n = k + 1\))
We want to show that \(\sum_{r=1}^{k+1} r^2 = \frac{1}{6}(k+1)((k+1)+1)(2(k+1)+1) = \frac{1}{6}(k+1)(k+2)(2k+3)\).

Starting with the sum up to \(k+1\):
\(\sum_{r=1}^{k+1} r^2 = \left(\sum_{r=1}^{k} r^2\right) + (k+1)^2\)

Substitute our inductive hypothesis:
\(= \frac{1}{6}k(k+1)(2k+1) + (k+1)^2\)

Algebra Tip: Do NOT expand everything! Instead, factor out the common term \(\frac{1}{6}(k+1)\):
\(= \frac{1}{6}(k+1)\left[ k(2k+1) + 6(k+1) \right]\)
\(= \frac{1}{6}(k+1)\left[ 2k^2 + k + 6k + 6 \right]\)
\(= \frac{1}{6}(k+1)\left[ 2k^2 + 7k + 6 \right]\)
Factor the quadratic \((2k^2 + 7k + 6) = (k+2)(2k+3)\):
\(= \frac{1}{6}(k+1)(k+2)(2k+3)\)
This matches the target formula for \(n = k+1\)!

Step 4: Conclusion
Since the result is true for \(n = 1\), and if true for \(n = k\) it has been proved true for \(n = k + 1\), by mathematical induction the result is true for all positive integers \(n \ge 1\).

Key Takeaway for Series: Always write \(\sum_{r=1}^{k+1} f(r) = \left(\sum_{r=1}^k f(r)\right) + f(k+1)\). Factor out common expressions (especially fractions) rather than multiplying out polynomials.

Type 2: Divisibility Proofs

Divisibility proofs ask you to prove that an expression \(f(n)\) is a multiple of a fixed integer \(d\) for all \(n \ge 1\). That is, \(f(n) = d \cdot M\) where \(M\) is an integer.

Strategy for Divisibility

The standard trick is to examine \(f(k+1)\) and rewrite it so that you can substitute \(f(k)\) back in.

Worked Example: Divisibility by 8

Prove by mathematical induction that \(f(n) = 3^{2n} - 1\) is divisible by \(8\) for all integers \(n \ge 1\).

Step 1: Base Case (\(n = 1\))
\(f(1) = 3^{2(1)} - 1 = 3^2 - 1 = 9 - 1 = 8\)
Since \(8 = 8 \times 1\), which is divisible by \(8\), the statement is true for \(n = 1\).

Step 2: Inductive Hypothesis
Assume the statement is true for \(n = k\), which means:
\(f(k) = 3^{2k} - 1 = 8M\) for some integer \(M\).
Rearranging this gives: \(3^{2k} = 8M + 1\).

Step 3: Inductive Step (\(n = k + 1\))
Consider \(f(k+1)\):
\(f(k+1) = 3^{2(k+1)} - 1 = 3^{2k+2} - 1\)
Use index laws to break up the power: \(3^{2k+2} = 3^{2k} \times 3^2 = 9 \times 3^{2k}\).
So:
\(f(k+1) = 9(3^{2k}) - 1\)

Substitute \(3^{2k} = 8M + 1\) from our hypothesis:
\(f(k+1) = 9(8M + 1) - 1\)
\(f(k+1) = 72M + 9 - 1\)
\(f(k+1) = 72M + 8\)
Factor out \(8\):
\(f(k+1) = 8(9M + 1)\)

Since \(M\) is an integer, \((9M + 1)\) is also an integer. Therefore, \(f(k+1)\) is a multiple of \(8\).

Step 4: Conclusion
Since the statement is true for \(n = 1\), and if true for \(n = k\) it is shown to be true for \(n = k + 1\), by mathematical induction \(3^{2n} - 1\) is divisible by \(8\) for all positive integers \(n \ge 1\).

Alternative Method (Subtraction Trick):
You can also calculate \(f(k+1) - f(k)\) or \(f(k+1) - (\text{constant}) \cdot f(k)\). Showing this difference is divisible by the divisor immediately proves \(f(k+1)\) is also divisible.

Key Takeaway for Divisibility: Use index rules like \(a^{k+1} = a \cdot a^k\) to isolate the power from the \(n = k\) case, then substitute your assumption.

Type 3: Matrix Powers

You can also use induction to prove a formula for the power of a matrix \(M^n\).

Quick Review: Matrix Multiplication

To multiply two \(2 \times 2\) matrices:
\(\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} w & x \\ y & z \end{pmatrix} = \begin{pmatrix} aw+by & ax+bz \\ cw+dy & cx+dz \end{pmatrix}\)

Worked Example: Power of a Matrix

Prove by mathematical induction that for all integers \(n \ge 1\):
If \(A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}\), then \(A^n = \begin{pmatrix} 1 & 2n \\ 0 & 1 \end{pmatrix}\).

Step 1: Base Case (\(n = 1\))
For \(n = 1\):
\(A^1 = \begin{pmatrix} 1 & 2(1) \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} = A\)
Thus, the result is true for \(n = 1\).

Step 2: Inductive Hypothesis
Assume the result is true for \(n = k\):
\(A^k = \begin{pmatrix} 1 & 2k \\ 0 & 1 \end{pmatrix}\)

Step 3: Inductive Step (\(n = k + 1\))
We must show that \(A^{k+1} = \begin{pmatrix} 1 & 2(k+1) \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2k+2 \\ 0 & 1 \end{pmatrix}\).

Using matrix power properties, \(A^{k+1} = A^k \cdot A\):
\(A^{k+1} = \begin{pmatrix} 1 & 2k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}\)

Multiplying the two matrices row-by-column:
Top-left element: \((1)(1) + (2k)(0) = 1 + 0 = 1\)
Top-right element: \((1)(2) + (2k)(1) = 2 + 2k = 2(k+1)\)
Bottom-left element: \((0)(1) + (1)(0) = 0 + 0 = 0\)
Bottom-right element: \((0)(2) + (1)(1) = 0 + 1 = 1\)

Putting it together:
\(A^{k+1} = \begin{pmatrix} 1 & 2(k+1) \\ 0 & 1 \end{pmatrix}\)
This is the required form for \(n = k + 1\).

Step 4: Conclusion
Since the result is true for \(n = 1\), and if true for \(n = k\) it is shown to be true for \(n = k + 1\), the result is true for all positive integers \(n \ge 1\) by mathematical induction.

Key Takeaway for Matrices: Express \(A^{k+1}\) as \(A^k A\) (or \(A A^k\)), substitute your matrix formula from the assumption, and perform the matrix multiplication carefully.

Common Mistakes to Avoid

• Writing the conclusion improperly: Omitting the conclusion or missing the phrase "if true for \(n = k\)" costs easy marks. Memorize the exact wording!

• Circular logic: Never assume \(n = k + 1\) is true at the start of your inductive step. You must start with the LHS of the \((k+1)\) case and derive the RHS using the \(n = k\) assumption.

• Multiplying out unnecessarily: In series proofs, do not expand cubic or quartic expressions into long polynomial forms. Look for common brackets to factorize.

• Index errors in divisibility: Remember that \(a^{k+1} = a^k \cdot a^1\) and \(a^{2(k+1)} = a^{2k+2} = a^{2k} \cdot a^2\). A common mistake is writing \(a^{2(k+1)}\) as \(a^{2k+1}\).

Quick Review Checklist

• Have I verified the base case explicitly for \(n = 1\) (or the base value specified)?
• Have I written "Assume true for \(n = k\)"?
• Have I clearly shown where the assumption is used in the \(n = k + 1\) proof?
• Have I written the full standard 4-part conclusion?