Strand 3 — Number

Proof by Induction (Higher Level)

5th Year · 6th Year (Leaving Cert)

✓Understand the Principle of Mathematical Induction and its application.
✓Apply mathematical induction to prove statements involving divisibility for natural numbers.
✓Apply mathematical induction to prove series identities for natural numbers.
✓Apply mathematical induction to prove inequalities for natural numbers.
✓Construct clear, logical, and rigorous proofs by induction, adhering to correct mathematical notation.

Key concepts

Principle of Mathematical Induction

Mathematical induction is a powerful method used to prove that a statement P(n) is true for all natural numbers n (or for all natural numbers greater than or equal to some initial integer). It is based on a 'domino effect' principle and involves three crucial steps: 1. **Base Case (n=1 or initial value)**: Show that the statement P(n) is true for the first value of n (usually n=1, but sometimes n=0 or some other integer k₀, as specified in the problem). 2. **Inductive Hypothesis (Assume true for n=k)**: Assume that the statement P(n) is true for some arbitrary natural number k, where k is greater than or equal to the base case value. This assumption is critical for the next step. 3. **Inductive Step (Prove true for n=k+1)**: Using the Inductive Hypothesis, prove that the statement P(n) is true for the next natural number, n=k+1. This is the core of the proof, showing that if it's true for k, it must also be true for k+1. Once these three steps are successfully completed, the Principle of Mathematical Induction allows us to conclude that the statement P(n) is true for all natural numbers n (or for all n from the base case onwards).

Proof by Induction for Divisibility

To prove that an expression P(n) is divisible by some integer m for all n ∈ ℕ (or n ≥ k₀), we follow the standard induction steps: 1. **Base Case**: Show P(k₀) is divisible by m. 2. **Inductive Hypothesis**: Assume P(k) is divisible by m for some integer k ≥ k₀. This means P(k) = mj for some integer j. 3. **Inductive Step**: Show that P(k+1) is divisible by m. The key here is to algebraically manipulate P(k+1) to incorporate the expression P(k) from the inductive hypothesis. Often, this involves splitting P(k+1) into terms, one of which is a multiple of P(k), or substituting P(k) = mj.

Proof by Induction for Series Identities

To prove a formula for the sum of a series, S(n), for all n ∈ ℕ (or n ≥ k₀), we use induction: 1. **Base Case**: Show that the formula holds for S(k₀). 2. **Inductive Hypothesis**: Assume the formula holds for S(k) for some integer k ≥ k₀. That is, assume S(k) = (the given formula for k). 3. **Inductive Step**: Show that the formula holds for S(k+1). The sum S(k+1) can be written as S(k) + (the (k+1)-th term of the series). Substitute the inductive hypothesis for S(k) and then algebraically simplify the expression to show it matches the given formula for (k+1).

Proof by Induction for Inequalities

To prove an inequality P(n) > Q(n) (or P(n) ≥ Q(n)) for all n ∈ ℕ (or n ≥ k₀), the inductive process is: 1. **Base Case**: Show that the inequality holds for n=k₀. 2. **Inductive Hypothesis**: Assume the inequality holds for some integer k ≥ k₀. That is, assume P(k) > Q(k). 3. **Inductive Step**: Show that P(k+1) > Q(k+1). This often requires careful algebraic manipulation. You might start with P(k+1) and use the inductive hypothesis P(k) > Q(k) to establish a new inequality. Sometimes, it's helpful to show that P(k+1) - Q(k+1) > 0, or to show that P(k+1) > some intermediate expression that is known to be greater than Q(k+1). Be careful with multiplying or dividing inequalities by negative numbers.

Key facts to remember

1Mathematical induction is a three-step proof technique: Base Case, Inductive Hypothesis, Inductive Step.
2The Base Case establishes the truth of the statement for the initial value of n (often n=1).
3The Inductive Hypothesis assumes the statement is true for an arbitrary integer k.
4The Inductive Step uses the Inductive Hypothesis to prove the statement for n=k+1.
5For divisibility proofs, manipulate P(k+1) to explicitly show a factor of the divisor, often by substituting P(k) = mj.
6For series identities, P(k+1) is typically formed by adding the (k+1)-th term to P(k).
7For inequality proofs, careful algebraic manipulation and justification of intermediate inequalities are essential.
8Always conclude your proof by explicitly stating that the statement is true for all relevant n by the Principle of Mathematical Induction.

Worked examples

Example 1

Prove by induction that 7ⁿ - 1 is divisible by 6 for all natural numbers n.

ILet P(n) be the statement '7ⁿ - 1 is divisible by 6'.

II**Base Case (n=1)**: P(1): 7¹ - 1 = 7 - 1 = 6. Since 6 is divisible by 6, P(1) is true.

III**Inductive Hypothesis**: Assume P(k) is true for some arbitrary natural number k. That is, assume 7ᵏ - 1 is divisible by 6. This means 7ᵏ - 1 = 6m for some integer m. From this, we can write 7ᵏ = 6m + 1.

IV**Inductive Step (Prove P(k+1) is true)**: We need to show that 7ᵏ⁺¹ - 1 is divisible by 6. Consider the expression for P(k+1): 7ᵏ⁺¹ - 1 = 7 * 7ᵏ - 1 Substitute 7ᵏ = 6m + 1 from the Inductive Hypothesis: = 7 * (6m + 1) - 1 = 42m + 7 - 1 = 42m + 6 Factorise out 6: = 6(7m + 1) Since m is an integer, (7m + 1) is also an integer. Therefore, 6(7m + 1) is divisible by 6.

V**Conclusion**: 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 natural numbers n. That is, 7ⁿ - 1 is divisible by 6 for all n ∈ ℕ.

Answer

Proven by induction.

For divisibility proofs, always aim to substitute the inductive hypothesis (e.g., 7ᵏ = 6m + 1) into the expression for P(k+1) to reveal the common factor.

Example 2

Prove by induction that the sum of the first n odd natural numbers is n². That is, 1 + 3 + 5 + ... + (2n - 1) = n² for all n ∈ ℕ.

ILet P(n) be the statement '1 + 3 + 5 + ... + (2n - 1) = n²'.

II**Base Case (n=1)**: P(1): The sum of the first 1 odd natural number is 1. The formula gives 1² = 1. Since 1 = 1, P(1) is true.

III**Inductive Hypothesis**: Assume P(k) is true for some arbitrary natural number k. That is, assume 1 + 3 + 5 + ... + (2k - 1) = k².

IV**Inductive Step (Prove P(k+1) is true)**: We need to show that 1 + 3 + 5 + ... + (2(k+1) - 1) = (k+1)². Consider the sum for n=k+1: 1 + 3 + 5 + ... + (2k - 1) + (2(k+1) - 1) = 1 + 3 + 5 + ... + (2k - 1) + (2k + 2 - 1) = 1 + 3 + 5 + ... + (2k - 1) + (2k + 1) Using the Inductive Hypothesis, we can replace the sum up to (2k - 1) with k²: = k² + (2k + 1) Factorise the expression: = (k + 1)² This matches the right-hand side of the formula for n=k+1.

V**Conclusion**: 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 natural numbers n. That is, 1 + 3 + 5 + ... + (2n - 1) = n² for all n ∈ ℕ.

Answer

Proven by induction.

For series identities, the (k+1)-th term is found by replacing 'n' with 'k+1' in the general term of the series.

Example 3

Prove by induction that 2ⁿ > n for all natural numbers n.

ILet P(n) be the statement '2ⁿ > n'.

II**Base Case (n=1)**: P(1): 2¹ > 1. Since 2 > 1, P(1) is true.

III**Inductive Hypothesis**: Assume P(k) is true for some arbitrary natural number k. That is, assume 2ᵏ > k.

IV**Inductive Step (Prove P(k+1) is true)**: We need to show that 2ᵏ⁺¹ > k+1. From the Inductive Hypothesis, we know 2ᵏ > k. Multiply both sides of the inequality by 2 (which is a positive number, so the inequality sign does not change): 2 * 2ᵏ > 2 * k 2ᵏ⁺¹ > 2k Now, we need to show that 2k ≥ k+1 for k ∈ ℕ. Subtract k from both sides: k ≥ 1. Since k is a natural number, k ≥ 1 is always true. Therefore, 2k ≥ k+1. Since 2ᵏ⁺¹ > 2k and 2k ≥ k+1, it follows that 2ᵏ⁺¹ > k+1.

V**Conclusion**: 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 natural numbers n. That is, 2ⁿ > n for all n ∈ ℕ.

Answer

Proven by induction.

For inequalities, you often need to establish an intermediate inequality (like 2k ≥ k+1 here) to bridge the gap between 2ᵏ⁺¹ and k+1.

Common mistakes

✗Failing to clearly state the Inductive Hypothesis, or assuming P(k+1) is true instead of proving it.
✗Making algebraic errors when manipulating expressions for P(k+1), especially when substituting the Inductive Hypothesis.
✗Not checking the base case, or choosing an incorrect starting value for n.
✗Forgetting to use the Inductive Hypothesis in the Inductive Step, which is the core of the proof.
✗Incorrectly manipulating inequalities, such as multiplying by a negative number without reversing the inequality sign.
✗Not providing sufficient justification for steps, particularly in inequality proofs where intermediate steps might need explanation.

Exam tips

★Clearly label each of the three steps of induction: 'Base Case', 'Inductive Hypothesis', and 'Inductive Step'.
★Show all algebraic working in full detail. Examiners award marks for clear, logical steps.
★For divisibility questions, explicitly write down the assumption P(k) = mj (where m is the divisor) as this helps guide the substitution in the Inductive Step.
★For inequality questions, be prepared to show that (LHS for k+1) - (RHS for k+1) > 0, or to construct a chain of inequalities that leads to the desired result.
★Practise a wide variety of questions from each subtopic (divisibility, series, inequalities) to become proficient with different manipulation techniques and common pitfalls.

Ready to practise?

Try a problem on this topic

Snap a photo or type a question — get step-by-step working instantly.

Solve a problem →← Maths curriculum