[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]