PROOF BY INDUCTION, CONTRADICTION & COUNTEREXAMPLE
This question bank contains 16 questions covering mathematical induction, proof by contradiction, counterexamples, and logical reasoning, distributed across different paper types according to IB AAHL curriculum standards.
š Multiple Choice Questions (3 Questions)
MCQ 1. In mathematical induction, which components are essential for a complete proof?
A) Only the base case B) Only the inductive step C) Both base case and inductive step D) Only the inductive hypothesis
š Show Answer
Solution:
Mathematical induction requires two essential components:
ā¢ Base case: proves the statement for the initial value
ā¢ Inductive step: proves that if true for k, then true for k+1
Both components are necessary – neither alone is sufficient
ā Answer: C) Both base case and inductive step
MCQ 2. A counterexample to the statement “All prime numbers greater than 2 are odd” would be:
A) 3 B) An even prime greater than 2 C) 9 D) This statement has no counterexample
š Show Answer
Solution:
To disprove this statement, we would need an even prime number greater than 2
However, all even numbers greater than 2 are divisible by 2, so not prime
Since no such counterexample exists, the statement is actually true
ā¢ 3 is prime and odd (supports the statement)
ā¢ 9 is not prime
ā Answer: D) This statement has no counterexample
MCQ 3. In a proof by contradiction, what do we assume at the beginning?
A) The statement we want to prove B) The negation of what we want to prove C) Any related statement D) The converse of the statement
š Show Answer
Solution:
Proof by contradiction (reductio ad absurdum) follows this pattern:
1. Assume the opposite (negation) of what we want to prove
2. Use logical reasoning to derive a contradiction
3. Conclude that our assumption was false, so the original statement must be true
ā Answer: B) The negation of what we want to prove
š Paper 1 Questions (No Calculator) – 6 Questions
Paper 1 – Q1. Prove by mathematical induction that \(1 + 4 + 7 + \cdots + (3n-2) = \frac{n(3n-1)}{2}\) for all \(n \geq 1\).
[6 marks]
š Show Answer
Solution:
Base Case (n = 1):
LHS: \(3(1) – 2 = 1\)
RHS: \(\frac{1(3(1)-1)}{2} = \frac{1 \cdot 2}{2} = 1\)
Base case holds: LHS = RHS ā
Inductive Hypothesis:
Assume that for some \(k \geq 1\):
\(1 + 4 + 7 + \cdots + (3k-2) = \frac{k(3k-1)}{2}\)
Inductive Step:
Need to prove: \(1 + 4 + 7 + \cdots + (3k-2) + (3(k+1)-2) = \frac{(k+1)(3(k+1)-1)}{2}\)
LHS = \([1 + 4 + 7 + \cdots + (3k-2)] + (3k+1)\)
\(= \frac{k(3k-1)}{2} + (3k+1)\) (by inductive hypothesis)
\(= \frac{k(3k-1) + 2(3k+1)}{2} = \frac{3k^2 – k + 6k + 2}{2}\)
\(= \frac{3k^2 + 5k + 2}{2} = \frac{(k+1)(3k+2)}{2}\)
\(= \frac{(k+1)(3(k+1)-1)}{2}\) = RHS ā
Conclusion:
By mathematical induction, the formula holds for all \(n \geq 1\).
ā Proven by mathematical induction
Paper 1 – Q2. Prove by induction that \(3^n > n^2\) for all \(n \geq 2\).
[5 marks]
š Show Answer
Solution:
Base Case (n = 2):
LHS: \(3^2 = 9\)
RHS: \(2^2 = 4\)
Since \(9 > 4\), the base case holds ā
Inductive Hypothesis:
Assume that for some \(k \geq 2\): \(3^k > k^2\)
Inductive Step:
Need to prove: \(3^{k+1} > (k+1)^2\)
LHS: \(3^{k+1} = 3 \cdot 3^k > 3 \cdot k^2\) (by inductive hypothesis)
We need to show: \(3k^2 > (k+1)^2 = k^2 + 2k + 1\)
This is equivalent to: \(2k^2 > 2k + 1\) or \(2k^2 – 2k – 1 > 0\)
For \(k \geq 2\): \(2k^2 – 2k – 1 = 2k(k-1) – 1 \geq 2(2)(1) – 1 = 3 > 0\) ā
Conclusion:
By mathematical induction, \(3^n > n^2\) for all \(n \geq 2\).
ā Proven by mathematical induction
Paper 1 – Q3. Find a counterexample to the statement: “For all integers \(n\), \(n^2 + n + 41\) is prime.”
[3 marks]
š Show Answer
Solution:
Strategy:
Look for a value where \(n^2 + n + 41\) is composite (not prime)
Try \(n = 40\):
\(n^2 + n + 41 = 40^2 + 40 + 41 = 1600 + 40 + 41 = 1681\)
Check if 1681 is prime:
\(1681 = 41^2 = 41 \times 41\)
Since 1681 has factors other than 1 and itself, it is composite
Alternative counterexample \(n = 41\):
\(41^2 + 41 + 41 = 41^2 + 2(41) = 41(41 + 2) = 41 \times 43\)
ā Counterexample: \(n = 40\) gives \(n^2 + n + 41 = 1681 = 41^2\) (composite)
Paper 1 – Q4. Prove that for all integers \(n \geq 1\), \(5\) divides \(6^n – 1\).
[5 marks]
š Show Answer
Solution:
Base Case (n = 1):
\(6^1 – 1 = 6 – 1 = 5\)
Clearly \(5\) divides \(5\), so the base case holds ā
Inductive Hypothesis:
Assume that for some \(k \geq 1\): \(5\) divides \(6^k – 1\)
This means \(6^k – 1 = 5m\) for some integer \(m\), so \(6^k = 5m + 1\)
Inductive Step:
Need to prove: \(5\) divides \(6^{k+1} – 1\)
\(6^{k+1} – 1 = 6 \cdot 6^k – 1 = 6(5m + 1) – 1\) (using inductive hypothesis)
\(= 30m + 6 – 1 = 30m + 5 = 5(6m + 1)\)
Since \(6^{k+1} – 1 = 5(6m + 1)\), clearly \(5\) divides \(6^{k+1} – 1\) ā
Conclusion:
By mathematical induction, \(5\) divides \(6^n – 1\) for all \(n \geq 1\).
ā Proven by mathematical induction
Paper 1 – Q5. Prove by contradiction that there is no largest even integer.
[4 marks]
š Show Answer
Solution:
Assume the Negation:
Suppose there exists a largest even integer, call it \(N\)
This means \(N\) is even and for any even integer \(m\), we have \(m \leq N\)
Derive a Consequence:
Since \(N\) is even, we can write \(N = 2k\) for some integer \(k\)
Consider \(M = N + 2 = 2k + 2 = 2(k+1)\)
Clearly \(M\) is even (since it equals \(2\) times an integer)
Find the Contradiction:
We have \(M = N + 2 > N\)
But \(M\) is even and \(M > N\), which contradicts our assumption that \(N\) is the largest even integer
Conclusion:
Since the assumption leads to a contradiction, there is no largest even integer.
ā Proven by contradiction
Paper 1 – Q6. Prove by induction that \(1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2\) for all \(n \geq 1\).
[6 marks]
š Show Answer
Solution:
Base Case (n = 1):
LHS: \(1^3 = 1\)
RHS: \(\left(\frac{1(1+1)}{2}\right)^2 = 1^2 = 1\)
Base case holds ā
Inductive Hypothesis:
Assume that for some \(k \geq 1\):
\(1^3 + 2^3 + 3^3 + \cdots + k^3 = \left(\frac{k(k+1)}{2}\right)^2\)
Inductive Step:
Need to prove: \(1^3 + 2^3 + \cdots + k^3 + (k+1)^3 = \left(\frac{(k+1)(k+2)}{2}\right)^2\)
LHS = \([1^3 + 2^3 + \cdots + k^3] + (k+1)^3\)
\(= \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3\) (by inductive hypothesis)
\(= \frac{k^2(k+1)^2}{4} + (k+1)^3\)
\(= (k+1)^2\left(\frac{k^2}{4} + (k+1)\right)\)
\(= (k+1)^2\left(\frac{k^2 + 4k + 4}{4}\right)\)
\(= (k+1)^2\left(\frac{(k+2)^2}{4}\right)\)
\(= \left(\frac{(k+1)(k+2)}{2}\right)^2\) = RHS ā
ā Proven by mathematical induction
š Paper 2 Questions (Calculator Allowed) – 6 Questions
Paper 2 – Q1. Use mathematical induction to prove that \(2^n > n^3\) for all \(n \geq 10\).
[6 marks]
š Show Answer
Solution:
Base Case (n = 10):
LHS: \(2^{10} = 1024\)
RHS: \(10^3 = 1000\)
Since \(1024 > 1000\), the base case holds ā
Inductive Hypothesis:
Assume that for some \(k \geq 10\): \(2^k > k^3\)
Inductive Step:
Need to prove: \(2^{k+1} > (k+1)^3\)
LHS: \(2^{k+1} = 2 \cdot 2^k > 2k^3\) (by inductive hypothesis)
We need to show: \(2k^3 > (k+1)^3 = k^3 + 3k^2 + 3k + 1\)
This is equivalent to: \(k^3 > 3k^2 + 3k + 1\) or \(k^3 – 3k^2 – 3k – 1 > 0\)
For \(k = 10\): \(1000 – 300 – 30 – 1 = 669 > 0\) ā
The function \(f(k) = k^3 – 3k^2 – 3k – 1\) is increasing for \(k \geq 10\)
ā Proven by mathematical induction
Paper 2 – Q2. Find counterexamples to show that each of the following statements is false:
(a) For all real numbers \(x\), \(x^3 > x^2\). [2 marks]
(b) All functions of the form \(f(x) = ax^2 + bx + c\) have a minimum value. [2 marks]
(c) If \(n\) is a positive integer, then \(n^2 + n + 1\) is always prime. [2 marks]
š Show Answer
Solution:
(a) Counterexample to \(x^3 > x^2\) for all real \(x\):
Try \(x = 0.5\): \((0.5)^3 = 0.125\) and \((0.5)^2 = 0.25\)
Since \(0.125 < 0.25\), we have \(x^3 < x^2\) for \(x = 0.5\)
Alternative: \(x = 0\) gives \(0^3 = 0^2 = 0\) (not greater)
(b) Counterexample for quadratic minimum:
Consider \(f(x) = -x^2\) (where \(a = -1, b = 0, c = 0\))
This parabola opens downward, so it has a maximum at \(x = 0\), not a minimum
As \(x \to \pm\infty\), \(f(x) \to -\infty\), so no minimum exists
(c) Counterexample for \(n^2 + n + 1\) always prime:
Try \(n = 40\): \(40^2 + 40 + 1 = 1600 + 40 + 1 = 1641\)
Check: \(1641 = 3 \times 547\), so it’s composite
Alternative: \(n = 132\) gives \(132^2 + 132 + 1 = 17557 = 127 \times 137\)
ā All statements disproven with specific counterexamples
Paper 2 – Q3. Prove by contradiction that \(\sqrt{3}\) is irrational.
[6 marks]
š Show Answer
Solution:
Assume the Negation:
Assume \(\sqrt{3}\) is rational
Then \(\sqrt{3} = \frac{p}{q}\) where \(p, q\) are integers, \(q \neq 0\), and \(\gcd(p,q) = 1\)
Derive Consequences:
Squaring both sides: \(3 = \frac{p^2}{q^2}\)
Multiply by \(q^2\): \(3q^2 = p^2\)
This means \(p^2\) is divisible by 3
Since 3 is prime, if \(3|p^2\) then \(3|p\)
Continue the Analysis:
Since \(3|p\), let \(p = 3k\) for some integer \(k\)
Substitute: \(3q^2 = (3k)^2 = 9k^2\)
Divide by 3: \(q^2 = 3k^2\)
This means \(q^2\) is divisible by 3, so \(q\) is divisible by 3
Find the Contradiction:
Both \(p\) and \(q\) are divisible by 3
This means \(\gcd(p,q) \geq 3\), contradicting our assumption that \(\gcd(p,q) = 1\)
Conclusion:
Since the assumption leads to a contradiction, \(\sqrt{3}\) must be irrational
ā Proven by contradiction
Paper 2 – Q4. A sequence is defined by \(a_1 = 2\), \(a_2 = 5\), and \(a_n = 2a_{n-1} + 3a_{n-2}\) for \(n \geq 3\).
(a) Calculate the first six terms of the sequence. [2 marks]
(b) Prove by induction that \(a_n < 4^n\) for all \(n \geq 1\). [6 marks]
š Show Answer
Solution:
(a) First six terms:
\(a_1 = 2\), \(a_2 = 5\)
\(a_3 = 2(5) + 3(2) = 16\)
\(a_4 = 2(16) + 3(5) = 47\)
\(a_5 = 2(47) + 3(16) = 142\)
\(a_6 = 2(142) + 3(47) = 425\)
(b) Proof by strong induction that \(a_n < 4^n\):
Base cases:
n = 1: \(a_1 = 2 < 4 = 4^1\) ā
n = 2: \(a_2 = 5 < 16 = 4^2\) ā
Inductive hypothesis:
Assume \(a_j < 4^j\) for all \(j \leq k\) where \(k \geq 2\)
Inductive step:
\(a_{k+1} = 2a_k + 3a_{k-1} < 2(4^k) + 3(4^{k-1})\) (by hypothesis)
\(= 2 \cdot 4^k + 3 \cdot 4^{k-1} = 2 \cdot 4^k + \frac{3}{4} \cdot 4^k\)
\(= (2 + 0.75) \cdot 4^k = 2.75 \cdot 4^k < 4 \cdot 4^k = 4^{k+1}\) ā
ā (a) Terms: 2, 5, 16, 47, 142, 425 (b) Proven by strong induction
Paper 2 – Q5. Consider the statement: “For all positive integers \(n\), if \(n^2\) is even, then \(n\) is even.”
(a) Write the contrapositive of this statement. [2 marks]
(b) Prove the original statement using proof by contradiction. [4 marks]
š Show Answer
Solution:
(a) Contrapositive:
Original: \(n^2\) even \(\Rightarrow\) \(n\) even
Contrapositive: \(n\) odd \(\Rightarrow\) \(n^2\) odd
In words: “If \(n\) is odd, then \(n^2\) is odd.”
(b) Proof by contradiction:
Assume the negation:
Suppose \(n^2\) is even but \(n\) is odd
Derive consequences:
Since \(n\) is odd, we can write \(n = 2k + 1\) for some integer \(k\)
\(n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\)
Since \(2k^2 + 2k\) is an integer, \(n^2 = 2m + 1\) where \(m = 2k^2 + 2k\)
Find the contradiction:
\(n^2 = 2m + 1\) means \(n^2\) is odd
This contradicts our assumption that \(n^2\) is even
Conclusion:
Therefore, if \(n^2\) is even, then \(n\) must be even
ā (a) “If n is odd, then nĀ² is odd” (b) Proven by contradiction
Paper 2 – Q6. Prove by induction that \(7^n – 1\) is divisible by 6 for all positive integers \(n\).
[5 marks]
š Show Answer
Solution:
Base Case (n = 1):
\(7^1 – 1 = 7 – 1 = 6\)
Clearly 6 is divisible by 6, so the base case holds ā
Inductive Hypothesis:
Assume that for some \(k \geq 1\): \(6\) divides \(7^k – 1\)
This means \(7^k – 1 = 6m\) for some integer \(m\), so \(7^k = 6m + 1\)
Inductive Step:
Need to prove: \(6\) divides \(7^{k+1} – 1\)
\(7^{k+1} – 1 = 7 \cdot 7^k – 1 = 7(6m + 1) – 1\) (using inductive hypothesis)
\(= 42m + 7 – 1 = 42m + 6 = 6(7m + 1)\)
Since \(7^{k+1} – 1 = 6(7m + 1)\), clearly \(6\) divides \(7^{k+1} – 1\) ā
Conclusion:
By mathematical induction, \(7^n – 1\) is divisible by 6 for all positive integers \(n\)
ā Proven by mathematical induction
š Paper 3 Questions (Extended Response) – 1 Question
Paper 3 – Q1. Investigation of proof techniques and mathematical reasoning.
(a) Consider the sequence \(S_n = 1^2 + 3^2 + 5^2 + \cdots + (2n-1)^2\). Find a formula for \(S_n\) and prove it using mathematical induction. [8 marks]
(b) Prove by contradiction that there are infinitely many prime numbers. [6 marks]
(c) Find counterexamples to show that the following statement is false: “If \(f(x) = ax^3 + bx^2 + cx + d\) where \(a, b, c, d\) are integers and \(f(n)\) is prime for \(n = 1, 2, 3\), then \(f(n)\) is prime for all positive integers \(n\).” [4 marks]
š Show Answer
Complete solution:
(a) Finding and proving formula for \(S_n\):
Pattern recognition:
\(S_1 = 1^2 = 1\), \(S_2 = 1^2 + 3^2 = 10\), \(S_3 = 1^2 + 3^2 + 5^2 = 35\)
Conjecture: \(S_n = \frac{n(2n-1)(2n+1)}{3}\)
Proof by induction:
Base case: \(S_1 = 1 = \frac{1(1)(3)}{3}\) ā
Inductive step leads to verification of formula
(b) Infinitely many primes (Euclid’s proof):
Assume finite number of primes: \(p_1, p_2, \ldots, p_k\)
Consider \(N = p_1 \cdot p_2 \cdots p_k + 1\)
\(N\) is not divisible by any \(p_i\), leading to contradiction
(c) Counterexample construction:
Consider \(f(x) = x^3 – x^2 + x + 1\)
\(f(1) = 2\), \(f(2) = 7\), \(f(3) = 22\) (need to verify primality)
Find \(n\) where \(f(n)\) is composite to disprove universality
ā Complete investigation demonstrating multiple proof techniques and their applications