[qdeck ” ]
[h] IB Mathematics AA HL Flashcards- Proof by Induction, Contradiction
[q] Proof by Induction, Contradiction
INDUCTION
A way of proving a statement/theorem. It does this by assuming it’s true for a natural no. K, then if you show that this also implies it’s also true for K+1. If you show it is true for the first case n = 1, then you have shown that it has been proven for every natural number.
PROCESS
1. BASIS STEP: Show statement is true for S(1) [when n = 1].
2. INDUCTIVE STEP: The implication of S(k) ⇒ S(k+1) is shown to be true for any k.
[q] Example 1
Prove S(n) = 1 + 2 + 3 + … + n = \( \frac{n(n+1)}{2} \) by induction:
→ BASIS STEP: Need to show for S(1):
\( 1 = \frac{1(1+1)}{2} ⇒ 1 = \frac{2}{2} ⇒ 1 = 1 + 1 \) ✓
→ INDUCTIVE: Assume true for S(k) = \( \frac{k(k+1)}{2} \). Now, need to show that it is true for S(k+1). i.e.:
S(k+1) = \( \frac{(k+1)((k+1)+1)}{2} \).
S(k+1) = 1 + 2 + 3 + … + k + (k+1), and from assumption
\( \frac{k(k+1)}{2} \) + (k+1)
(combine)
= \( \frac{k(k+1) + 2(k+1)}{2} \)
= \( \frac{(k+1)(k+2)}{2} \) as required
→ STATEMENT: As S(1) true, and S(k) true ⇒ S(k+1) true…proven for all n∈N.
[a] Example 2
Prove that the sum of the first n odd numbers sum to n²:
→ BASIS STEP: Need to show for S(1):
\( 1 = 1² \) ✓
→ INDUCTIVE: Assume that S(k) = 1 + 3 + 5 + … + (2k-1) = k² is true. Need to show that this implies
S(k+1) = 1 + 3 + … + (2k-1) + (2k+1) = (k+1)²
Expand
k² + (2k+1) = \( k² + 2k + 1 = (k+1)² \) as req’d.
→ STATEMENT: As S(1)…, by mathematical induction, proven for all n∈N.
NOTE
Sometimes the theorem starts at a different integer. Adjust the basis step:
[q] Example 3
Prove by induction: 3ⁿ < n! for all integers n > 6:
→ BASIS STEP: Show true for S(7):
3⁷ = 2187, 7! = 5040 ⇒ 2187 < 5040 ✓
→INDUCTIVE: Assume 3ᵏ < k! (for k > 6), need to show 3ᵏ⁺¹ < (k+1)!.
3ᵏ⁺¹ = 3 ⋅ 3ᵏ < k! ⋅ (k+1).
As 3 < k+1 (because k > 6) and 3ᵏ < k!
(by assumption). Then 3ᵏ⋅3 < k!⋅(k+1), and ∴ 3ᵏ⁺¹ < (k+1)! as required.
STATEMENT: As S(1) true, and S(k) true ⇒ S(k+1) true…proven for all n > 6
NOTE
The ‘statements’ are abbreviated above. You must learn how to write full, rigorous, inductive statements.
[a] CONTRADICTION
If you have a statement, then assume it is false, then show through some method that there is a contradiction, then the statement has been proven to always be true.
[q] Example 3
Prove that: if n is odd, then n² is always odd.
→ ASSUME FALSE: Assume that n² is even, i.e. n² = 2A, with A ∈ Z.
→ SHOW CONTRADICTION: So n×n = 2A, but n’s are odd, so this can be written (2k+1)(2k+1) = 2A ⇒ 4k² + 4k + 1 = 2A ⇒ 2(2k² + 2k) + 1 = 2A, which can’t be true. Hence, if n is odd, n² is odd.
[a] Example 5
Prove √2 is irrational:
→ ASSUME FALSE: Assume rational, i.e.: √2 = a/b, a,b ∈ Z, a & b share no common factor.
→ SHOW CONTRADICTION: If √2 = a/b ⇒ 2 = a²/b² ⇒ 2b² = a², meaning a² is even, so a is even. So, let a = 2m ⇒ 2b² = (2m)² = 2b² = 4m² ⇒ b² = 2m². Therefore, b² is even and b is even. If a & b are even, this means they DO in fact share a common factor (2). So, √2 must be irrational.
[q] Example 6
Prove this is false: “If n ∈ N, then n² + 1 is prime”:
→ Whilst this is true for many values of n [1 → 1² + 1 → 2, prime], [4 → 17, prime], [20 → 20² + 1 → 401, prime].
We just need to find one counterexample. For n = 5, 5² + 1 = 26, not prime. Hence, statement is false.
[a] Example 7
Disprove “all prime numbers are odd numbers”:
→ Nearly all primes are odd, but 2 is even and prime.
[q] Example 8
Show that “If p is prime, 2p + 1 is prime” is false:
→ True for primes such as 2 (5), 5 (11), 23 (47), but we have a counterexample with p = 7, as 2p + 1 = 15 which is not prime.
[a] AHL 1.15 Proof by mathematical induction AA HL Paper 1
[x] Exit text
(enter text or “Add Media”; select text to format)
[/qdeck]