Proof by Induction: Conquering the Infinite Steps

Hello! Welcome to one of the most elegant and crucial methods in Further Mathematics: Proof by Induction. If you can master this technique, you can prove statements that hold true for infinitely many positive integers—a truly powerful skill!

Don't worry if this seems tricky at first. Proof by Induction follows a fixed, logical structure. We are essentially learning a mathematical formula for building a convincing argument. By the end of these notes, you'll be able to apply this method to sums, sequences, divisibility problems, and even complex numbers!

What is Mathematical Induction? (The Domino Analogy)

Proof by Induction is a method used to prove that a statement, \(P(n)\), is true for all integers \(n\) greater than or equal to some starting integer (usually \(n=1\)).

The Domino Effect Analogy

Imagine you have an infinite line of dominoes, numbered 1, 2, 3, and so on. To prove that all the dominoes will fall down, you only need to prove two things:

  1. Base Case (The first push): You push the first domino (Domino 1).
  2. Inductive Step (The chain reaction): You prove that if any domino (\(k\)) falls, the next domino (\(k+1\)) will also fall.

If both points are true, the entire infinite line must fall!

Quick Review: The Goal
To prove \(P(n)\) is true for all \(n \ge 1\), we must establish the chain reaction: \(P(1) \rightarrow P(2) \rightarrow P(3) \rightarrow \dots \rightarrow P(n)\).

The Three Essential Steps of Proof by Induction

Every single induction proof must rigidly follow these three steps. Make sure you clearly label them in your exam answers!

Step 1: The Base Case (\(n=1\))

We must show that the statement \(P(n)\) is true for the smallest possible integer, usually \(n=1\) (or sometimes \(n=0\) or \(n=2\), depending on the question).

  • Substitute the starting value (e.g., \(n=1\)) into the Left-Hand Side (LHS) of the statement.
  • Substitute the starting value into the Right-Hand Side (RHS) of the statement.
  • Conclude that since LHS = RHS, \(P(1)\) is true.

Step 2: The Inductive Assumption (\(n=k\))

This is where we set up the hypothetical link in the domino chain.

  • We assume that the statement \(P(k)\) is true for some arbitrary positive integer \(k\).
  • Crucially, write out the statement \(P(k)\) clearly. You will use this equation in Step 3.

Common Mistake Alert: Students sometimes try to prove \(P(k)\) is true. You must only assume it. The proof comes in the next step!

Step 3: The Inductive Step (\(n=k+1\))

We now use the assumption \(P(k)\) to prove that the next case, \(P(k+1)\), must also be true.

  • Write out the statement \(P(k+1)\) that you are trying to prove.
  • Start with the LHS of \(P(k+1)\).
  • Manipulate the LHS to show that it contains the assumed statement \(P(k)\).
  • Substitute the RHS of \(P(k)\) into your expression.
  • Simplify the resulting expression until it matches the RHS of \(P(k+1)\).

Final Conclusion: Once Step 3 is complete, you must write a final concluding statement to get the last marks. For example: "Since \(P(1)\) is true, and \(P(k)\) being true implies \(P(k+1)\) is true, by the principle of mathematical induction, \(P(n)\) is true for all positive integers \(n\)."

Application Type 1: Summation and Series

This is the most common type of induction proof, where you prove a formula for the sum of a series (e.g., arithmetic, geometric, or series using $\sum$ notation).

Key Strategy for Sums

When dealing with the LHS of \(P(k+1)\), recognize that the sum up to \(k+1\) is simply the sum up to \(k\) plus the \((k+1)\)-th term.

$$ \text{LHS of } P(k+1) = \sum_{r=1}^{k+1} f(r) = \left( \sum_{r=1}^{k} f(r) \right) + f(k+1) $$

The bracketed part is exactly your assumption \(P(k)\)! This is where you substitute.

Example: Proving the sum of a simple sequence:

Prove that \( \sum_{r=1}^{n} r^2 = \frac{1}{6}n(n+1)(2n+1) \) for all integers \(n \ge 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 LHS = RHS, \(P(1)\) is true.

Step 2: Assumption (\(n=k\))
Assume that \(P(k)\) is true for some positive integer \(k\):
$$ \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 \(P(k+1)\) is true. Start with the LHS of \(P(k+1)\):
$$ \text{LHS} = \sum_{r=1}^{k+1} r^2 = \left( \sum_{r=1}^{k} r^2 \right) + (k+1)^2 $$ Substitute the assumption \(P(k)\):
$$ \text{LHS} = \frac{1}{6}k(k+1)(2k+1) + (k+1)^2 $$ Now, factor out the common term, \((k+1)\):
$$ \text{LHS} = (k+1) \left[ \frac{1}{6}k(2k+1) + (k+1) \right] $$ $$ \text{LHS} = (k+1) \left[ \frac{2k^2+k}{6} + \frac{6(k+1)}{6} \right] $$ $$ \text{LHS} = \frac{1}{6}(k+1) \left[ 2k^2+k + 6k+6 \right] $$ $$ \text{LHS} = \frac{1}{6}(k+1) (2k^2+7k+6) $$ Factor the quadratic \(2k^2+7k+6 = (k+2)(2k+3)\):
$$ \text{LHS} = \frac{1}{6}(k+1)(k+2)(2k+3) $$ This matches the RHS of \(P(k+1)\), since replacing \(n\) with \(k+1\) gives \( \frac{1}{6}(k+1)((k+1)+1)(2(k+1)+1) = \frac{1}{6}(k+1)(k+2)(2k+3) \).
Therefore, \(P(k+1)\) is true.

Key Takeaway for Sums: Always look for the $P(k)$ part inside the $P(k+1)$ expression. Factorisation is your best friend when simplifying the algebra.

Application Type 2: Divisibility Proofs

In these problems, you are asked to prove that an expression (usually involving exponents) is always divisible by a certain integer.

Example from the Syllabus: Prove that \( 7^n + 4^{n+1} \) is divisible by 6 for all positive integers \(n\).

The 'M' Factor Trick for Divisibility

When proving that \(f(n)\) is divisible by \(M\), the goal in Step 3 is to manipulate \(f(k+1)\) so that one part is exactly \(f(k)\) and the remaining part is clearly a multiple of \(M\).

Step 1: Base Case (\(n=1\))
\( 7^1 + 4^{1+1} = 7 + 4^2 = 7 + 16 = 23 \). Wait, 23 is not divisible by 6!

Did you know? Always check the question context. If the statement is wrong, you cannot prove it! Let's correct the example (as used in standard Further Maths resources) to one that is provable: \( 7^n + 4^{n+1} \) is divisible by 3. (Note: The syllabus example is $7^n + 4^{n+1}$ is divisible by 6, but this is only true for $n$ even or $n$ starting at 0. Let's use the standard technique for divisibility by a factor $M$.)

Let's use the syllabus example $7^n + 4^{n+1}$ is divisible by 6, assuming $n \ge 1$. (We must rely on algebraic manipulation, as the base case $n=1$ yields 23, which suggests the base case must be $n=2$ or the question implicitly assumes $n \ge 2$, or the intended expression was $7^n - 4^{n+1}$).

For the sake of demonstrating the method, let's assume the question meant $7^n - 4^n$ is divisible by 3, which is a simpler but robust example.

Prove that \( P(n): 7^n - 4^n \) is divisible by 3 for all integers \(n \ge 1\).

Step 1: Base Case (\(n=1\))
\( 7^1 - 4^1 = 3 \). Since 3 is divisible by 3, \(P(1)\) is true.

Step 2: Assumption (\(n=k\))
Assume that \(P(k)\) is true for some positive integer \(k\). That is, \( 7^k - 4^k \) is divisible by 3. We can write this as:
$$ 7^k - 4^k = 3M $$ where \(M\) is some integer. Rearrange this: \( 7^k = 4^k + 3M \). (This rearrangement is key!)

Step 3: Inductive Step (\(n=k+1\))
We examine \(P(k+1): 7^{k+1} - 4^{k+1}\).
$$ 7^{k+1} - 4^{k+1} = 7 \cdot 7^k - 4 \cdot 4^k $$ Substitute the expression for \( 7^k \) from the assumption in Step 2:
$$ 7^{k+1} - 4^{k+1} = 7 (4^k + 3M) - 4 \cdot 4^k $$ Expand and rearrange to isolate multiples of 3:
$$ 7 \cdot 4^k + 7 \cdot 3M - 4 \cdot 4^k $$ Combine the terms involving \(4^k\):
$$ (7-4) \cdot 4^k + 21M $$ $$ 3 \cdot 4^k + 21M $$ Factor out the required multiple, 3:
$$ 3 (4^k + 7M) $$ Since \(k\) and \(M\) are integers, \((4^k + 7M)\) is an integer. Thus, \( 7^{k+1} - 4^{k+1} \) is a multiple of 3.
Therefore, \(P(k+1)\) is true.

Conclusion: By induction, \( 7^n - 4^n \) is divisible by 3 for all integers \(n \ge 1\).

Divisibility Trick Summary

1. In Step 2, rearrange the assumption \(P(k)\) to isolate the most complicated exponential term (e.g., \(7^k\)).
2. In Step 3, write \(P(k+1)\) using the definition (e.g., $7^{k+1} = 7 \cdot 7^k$).
3. Substitute the isolated term from Step 2.
4. Collect the terms and factor out the required divisor \(M\).

Application Type 3: Algebraic and Complex Number Proofs

Induction can be used to prove general algebraic results, including those concerning complex numbers. The most famous example in this module is proving De Moivre’s Theorem for positive integers \(n\), as specified in the syllabus (FP2.4).

Prove that \(P(n): (\cos \theta + i \sin \theta)^n = \cos n\theta + i \sin n\theta \) for all positive integers \(n\).

Prerequisite Knowledge: You must know the trigonometric addition formulae:
\( \cos(A+B) = \cos A \cos B - \sin A \sin B \)
\( \sin(A+B) = \sin A \cos B + \cos A \sin B \)

Step 1: Base Case (\(n=1\))
LHS: \( (\cos \theta + i \sin \theta)^1 = \cos \theta + i \sin \theta \)
RHS: \( \cos (1\theta) + i \sin (1\theta) = \cos \theta + i \sin \theta \)
Since LHS = RHS, \(P(1)\) is true.

Step 2: Assumption (\(n=k\))
Assume that \(P(k)\) is true for some positive integer \(k\):
$$ (\cos \theta + i \sin \theta)^k = \cos k\theta + i \sin k\theta $$

Step 3: Inductive Step (\(n=k+1\))
We examine the LHS of \(P(k+1)\):
$$ \text{LHS} = (\cos \theta + i \sin \theta)^{k+1} $$ Split the exponent:
$$ \text{LHS} = (\cos \theta + i \sin \theta)^k \cdot (\cos \theta + i \sin \theta)^1 $$ Substitute the assumption \(P(k)\) into the first bracket:
$$ \text{LHS} = (\cos k\theta + i \sin k\theta) (\cos \theta + i \sin \theta) $$ Expand the brackets (like multiplying two complex numbers):
$$ \text{LHS} = \cos k\theta \cos \theta + i \cos k\theta \sin \theta + i \sin k\theta \cos \theta + i^2 \sin k\theta \sin \theta $$ Since \(i^2 = -1\), rearrange into real and imaginary parts:
$$ \text{LHS} = (\cos k\theta \cos \theta - \sin k\theta \sin \theta) + i (\sin k\theta \cos \theta + \cos k\theta \sin \theta) $$ Now, apply the trig addition formulae (this is the key simplification!):
$$ \text{LHS} = \cos (k\theta + \theta) + i \sin (k\theta + \theta) $$ Factor out \(\theta\):
$$ \text{LHS} = \cos ((k+1)\theta) + i \sin ((k+1)\theta) $$ This is exactly the RHS of \(P(k+1)\). Therefore, \(P(k+1)\) is true.

Key Takeaway for De Moivre's Proof: The structure is simple: separate the exponent, substitute \(P(k)\), expand, group real/imaginary parts, and simplify using the angle addition formulas.

Common Pitfalls to Avoid

Making your induction proofs fully rigorous requires attention to detail. Here are things markers look for:

  • Starting Point: Always verify the base case \(n=1\). If the statement is only true for \(n \ge 2\), the base case must be \(n=2\).
  • Clear Labelling: Label your three steps (Base Case, Assumption, Inductive Step).
  • Using the Assumption: You must explicitly use your \(P(k)\) assumption in the algebra for the \(P(k+1)\) step. If you don't, you haven't performed a proof by induction.
  • Concluding Statement: Do not forget the final concluding sentence referencing the Principle of Mathematical Induction (PMI).

★ Comprehensive Key Takeaway ★

Proof by Induction is a three-step journey proving a statement holds true for all integers \(n \ge n_0\):

  1. Foundation (\(n_0\)): Show the statement holds for the first case.
  2. Bridge (\(k\)): Assume the statement holds for an arbitrary integer \(k\).
  3. Leap (\(k+1\)): Use the bridge to show the statement holds for the next integer, \(k+1\).

Master the algebraic manipulation required for each type (substitution for sums, rearrangement for divisibility, trig identities for complex numbers).