Mathematical induction is a method of proof that shows a statement is true for every natural number, without having to check them one at a time. Think of it like a row of dominoes: if you push the first one over and prove that any falling domino must hit the next one, every domino in the infinite chain will fall. In the Leaving Certificate Higher Level exam, you must use this to prove identities (such as the sum of the first n natural numbers and the sum of a finite geometric series), inequalities (such as n! > 2ⁿ, 2ⁿ ≥ n² for n ≥ 4, and (1+x)ⁿ ≥ 1+nx for x > −1), divisibility results (such as 3 being a factor of 4ⁿ − 1), and the proof of De Moivre's Theorem.
The Four-Step Method
Every proof by induction must follow a strict structure. Learn this skeleton: 1. Base Case: Verify the statement holds for the smallest value in the domain. If the question says n ∈ ℕ, start at n = 1. If it says n ≥ 4, start at n = 4. Show LHS = RHS. 2. Inductive Hypothesis: Assume the statement is true for n = k. Write it out: 'Assume the statement is true for n = k, i.e., [your equation/inequality].' 3. Inductive Step: Show the statement is true for n = k + 1. First, write the target statement for k + 1 (the 'Required to prove' line). Then, start from the left-hand side or the k+1 term, substitute your hypothesis, and use algebra to reach the target. 4. Conclusion: Write: 'Since the statement is true for the base case, and its truth for n = k implies its truth for n = k + 1, the statement is true for all n in the given domain by the principle of mathematical induction.'
Sum Identities
For sum identities (like the sum of the first n squares), the proof always uses the same algebraic move. In the inductive step, you add the (k+1)-th term to the sum of the first k terms (which you replace using the hypothesis). Immediately factor out the (k+1) term. This leaves you with a simpler quadratic to solve or factorise to match the RHS target.
Divisibility Results
For divisibility proofs, define your hypothesis as an equation: for example, 4ᵏ − 1 = 3A, where A ∈ ℤ. Rearrange this to make the power the subject: 4ᵏ = 3A + 1. In the inductive step, substitute this rearranged form for 4ᵏ. This allows you to factor out the divisor (in this case, 3) at the end, confirming the new expression is also a multiple of the divisor.
Inequalities and Bernoulli
For inequalities like 2ⁿ ≥ n² for n ≥ 4, scale the hypothesis up by multiplying by the base (e.g., multiply by 2). Then, prove the small 'bridging' inequality separately (e.g., 2k² ≥ (k+1)²). Show 2k² ≥ k² + 2k + 1 ⇔ (k-1)² ≥ 2. Since k ≥ 4, (k-1)² ≥ 9 > 2, the bridge holds. Bernoulli's inequality (1+x)ⁿ ≥ 1+nx (x > −1) follows a similar logic: multiply the hypothesis by (1+x) (noting 1+x > 0 since x > −1) and use the fact that kx² ≥ 0 to finish.
De Moivre's Theorem
To prove (cos θ + i sin θ)ⁿ = cos nθ + i sin nθ for n ∈ ℕ: 1. Base case n=1 is trivial. 2. Assume it is true for n=k. 3. For n=k+1, multiply (cos kθ + i sin kθ) by (cos θ + i sin θ). Expanding gives cos kθ cos θ + i cos kθ sin θ + i sin kθ cos θ + i² sin kθ sin θ, and since i² = −1 this becomes (cos kθ cos θ − sin kθ sin θ) + i(sin kθ cos θ + cos kθ sin θ). Use the compound angle formulae from your log tables to write this as cos(k+1)θ + i sin(k+1)θ. Do not quote De Moivre itself here or the proof is circular.
Key terms
- Natural Numbers (ℕ)
- The set {1, 2, 3, 4, …}. In this syllabus, ℕ starts at 1, so the base case is usually n = 1 unless restricted (e.g., n ≥ 4).
- Base Case
- The start of the chain where you verify the statement for the smallest valid n.
- Inductive Hypothesis
- The formal assumption that the statement is true for an arbitrary integer n = k.
- Divisibility
- If a is divisible by b, then a = bA for some integer A. This equation is the substitution tool for divisibility proofs.
Check yourself
In a divisibility proof, how do you write the hypothesis for 4ᵏ − 1 divisible by 3?
4ᵏ − 1 = 3A, where A ∈ ℤ, and therefore 4ᵏ = 3A + 1.
Why is the base case mandatory?
Without it, the chain P(k) ⇒ P(k+1) only says 'if it works, the next works'; the base case provides the actual starting point.
For the sum 1 + 2 + … + n = n(n+1)/2, write the line after substituting the hypothesis into the k+1 case.
k(k+1)/2 + (k+1).