IB Mathematics AA Proof by Induction Study Notes
IB Mathematics AA Proof by Induction Study Notes
IB Mathematics AA Proof by Induction Study Notes Offer a clear explanation of Proof by Induction , including various formula, rules, exam style questions as example to explain the topics. Worked Out examples and common problem types provided here will be sufficient to cover for topic Proof by Induction.
Proof by Mathematical Induction
Proof by Mathematical Induction
Mathematical induction is a method used to prove that a statement holds true for all natural numbers \( n \in \mathbb{N} \).
Steps of Induction:
- Base Case: Prove the statement is true for \( n = 1 \) (or starting value).
- Inductive Hypothesis: Assume the statement is true for some integer \( n = k \). (This is the assumption step.)
- Inductive Step: Use the assumption to prove the statement is true for \( n = k + 1 \).
If both steps are valid, the statement is true for all \( n \in \mathbb{N} \) by the principle of mathematical induction.
Example
Prove that for all natural numbers \( n \geq 1 \), the following identity holds:
\( 1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2} \)
▶️ Answer/Explanation
Base Case (n = 1):
LHS = 1, RHS = \( \frac{1(1 + 1)}{2} = 1 \)
Base case is true.
Inductive Hypothesis:
Assume the formula holds for \( n = k \):
\( 1 + 2 + \cdots + k = \frac{k(k + 1)}{2} \)
Inductive Step:
Show that it holds for \( n = k + 1 \):
\( 1 + 2 + \cdots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2} \)
Start with the LHS:
\( \left(\frac{k(k + 1)}{2}\right) + (k + 1) \)
\( = \frac{k(k + 1) + 2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2} \)
Conclusion:
The identity holds for \( n = k + 1 \). Hence, by mathematical induction, the formula holds for all \( n \in \mathbb{N} \).
Proof by Contradiction
Proof by Contradiction
Proof by contradiction is a logical method where we assume the opposite (negation) of what we want to prove, and then show that this assumption leads to a contradiction. This contradiction implies that the original statement must be true.
Steps in a Proof by Contradiction:
- Step 1: Assume that the statement you want to prove is false.
- Step 2: Using this assumption, apply logical reasoning, algebra, or other techniques to derive consequences.
- Step 3: Show that this assumption leads to a contradiction (e.g., something that is clearly false or violates known facts).
- Step 4: Conclude that the original statement must be true because the assumption of it being false is invalid.
Note: This method is especially useful in proving statements involving irrational numbers, uniqueness, or impossibilities.
Example
Prove that √3 is irrational.
▶️ Answer/Explanation
Assume √3 is rational. Then we can write \( \sqrt{3} = \frac{a}{b} \), where a and b are integers with no common factors.
Squaring both sides: \( 3 = \frac{a^2}{b^2} \Rightarrow a^2 = 3b^2 \).
This means \( a^2 \) is divisible by 3, so a is divisible by 3. Let \( a = 3k \).
Then \( a^2 = 9k^2 \Rightarrow 3b^2 = 9k^2 \Rightarrow b^2 = 3k^2 \).
So b is also divisible by 3, contradicting that a and b have no common factors.
Conclusion: Our assumption is wrong. So, √3 is irrational.
Example
Prove that the cube root of 5 is irrational.
▶️ Answer/Explanation
Assume \( \sqrt[3]{5} = \frac{a}{b} \), in lowest terms.
Cubing both sides: \( 5 = \frac{a^3}{b^3} \Rightarrow a^3 = 5b^3 \).
This implies a³ is divisible by 5, so a is divisible by 5. Let \( a = 5k \).
Then \( a^3 = 125k^3 \Rightarrow 5b^3 = 125k^3 \Rightarrow b^3 = 25k^3 \).
So b is also divisible by 5, contradicting the assumption that a/b is in lowest terms.
Conclusion: ∛5 is irrational.
Example
Prove that there are infinitely many prime numbers. (Euclid’s proof)
▶️ Answer/Explanation
Assume there are finitely many primes: \( p_1, p_2, …, p_n \).
Let \( N = p_1 p_2 \cdots p_n + 1 \).
N is not divisible by any of the primes \( p_1 \) to \( p_n \).
So N is either prime itself or divisible by a new prime.
This contradicts the assumption that we had listed all primes.
Conclusion: There must be infinitely many prime numbers.
Example
Prove that if \( a \) is rational and \( b \) is irrational, then \( a + b \) is irrational.
▶️ Answer/Explanation
Assume \( a + b \) is rational.
Then \( b = (a + b) – a \) is the difference of two rational numbers.
But the difference of two rational numbers is rational.
This contradicts the assumption that \( b \) is irrational.
Conclusion: Therefore, \( a + b \) must be irrational.
Counterexample
Counterexample
A counterexample disproves a general statement by showing that the statement does not hold in at least one specific case. This method is useful for testing universal claims.
For example, to disprove a claim like “All even numbers are divisible by 4”, it’s enough to find one even number that is not divisible by 4.
Example 1
Consider the set \( P \) of numbers of the form \( n^2 + 41n + 41 \), where \( n \in \mathbb{N} \). Show that not all elements of \( P \) are prime.
▶️ Answer/Explanation
Let \( n = 41 \).
Then \( P = 41^2 + 41 \cdot 41 + 41 = 1681 + 1681 + 41 = 3403 \).
Check if 3403 is a prime number.
It turns out that \( 3403 = 37 \times 91.97 \), so it is not a prime.
Conclusion: \( n = 41 \) gives a number that is not prime. Hence, not all elements of \( P \) are prime.
Example 2
Show that the statement “There are no positive integer solutions to the equation \( x^2 + y^2 = 10 \)” is not always true.
▶️ Answer/Explanation
Try \( x = 1 \), \( y = 3 \): then \( x^2 + y^2 = 1^2 + 3^2 = 1 + 9 = 10 \).
So \( (x, y) = (1, 3) \) is a valid solution with positive integers.
Conclusion: The statement is false. A counterexample is \( x = 1, y = 3 \).