Mini-Lesson

Proof

2 missions. Guess, learn, then check. Your place is saved.

Mission 1Why does toppling one domino prove a formula for every $n$ n?
Mission 2How can assuming something false prove something true?

The specification points and sources are listed under the lesson: see Sources.

Mission 1

Why does toppling one domino prove a formula for every $n$ n?

Make a guess: Why does toppling one domino prove a formula for every $n$ n?

Proof · mathematical induction

The structure of an induction proof

To prove a statement $P (n)$ P(n) for all $n \in Z^{+}$ n ∈ ℤ⁺:
Basis: show $P (1)$ P(1) is true.
Assumption: assume $P (k)$ P(k) is true for some $k \in Z^{+}$ k ∈ ℤ⁺.
Inductive step: using that assumption, show $P (k + 1)$ P(k+1) is true.
Conclusion: "Since $P (1)$ P(1) is true, and $P (k)$ P(k) true implies $P (k + 1)$ P(k+1) true, $P (n)$ P(n) is true for all $n \in Z^{+}$ n ∈ ℤ⁺ by mathematical induction." Markschemes reward a clear concluding statement.

Worked example Proof · mathematical induction

Induction for a sum

Question

Prove by induction that

r = 1 \sum n r (r + 1) = \frac{n ( n + 1 ) ( n + 2 )}{3}

for all

n \in Z^{+}

.

1
Basis, $n = 1$ n = 1: LHS $= 1 \times 2 = 2$ = 1 × 2 = 2 and RHS $= \frac{1 \times 2 \times 3}{3} = 2$ = (1 × 2 × 3)/3 = 2, so $P (1)$ P(1) is true
2
Assume $P (k)$ P(k): $r = 1 \sum k r (r + 1) = \frac{k ( k + 1 ) ( k + 2 )}{3}$ Σ_(r=1)^k r(r+1) = (k(k+1)(k+2))/3
3
Add the next term, $(k + 1) (k + 2)$ (k+1)(k+2): $r = 1 \sum k + 1 r (r + 1) = \frac{k ( k + 1 ) ( k + 2 )}{3} + (k + 1) (k + 2)$ Σ_(r=1)^(k+1) r(r+1) = (k(k+1)(k+2))/3 + (k+1)(k+2)
4
Take out the common factor: $= \frac{( k + 1 ) ( k + 2 ) ( k + 3 )}{3}$ = ((k+1)(k+2)(k+3))/3, which is the formula with $n = k + 1$ n = k+1, so $P (k + 1)$ P(k+1) is true
5
Write the conclusion sentence

Answer

True for

n = 1

;

P (k) \Rightarrow P (k + 1)

; so true for all

n \in Z^{+}

by induction.

⚠️ Watch out

factorise, do not expand. Expanding to a cubic in

k

makes it hard to see that you have reached the

n = k + 1

form.

Quick check

?In a proof that

r = 1 \sum n \frac{1}{r ( r + 1 )} = \frac{n}{n + 1}

, you assume the sum of the first

k

terms is

\frac{k}{k + 1}

. Which expression do you add to get the sum of the first

k + 1

terms?

Proof · mathematical induction

Divisibility and other contexts

Divisibility: to prove $f (n)$ f(n) is divisible by $d$ d, assume $f (k) = d M$ f(k) = dM for some integer $M$ M. Write $f (k + 1)$ f(k+1) in terms of $f (k)$ f(k), then show it is $d$ d times an integer.
Induction also proves results for derivatives, such as $\frac{d ^{n}}{d x ^{n}} (x e^{x}) = (x + n) e^{x}$ dⁿ/dxⁿ(xe^x) = (x+n)e^x, and for complex numbers (De Moivre's theorem).
The basis need not be $n = 1$ n = 1. For example, $n! > 2^{n}$ n! > 2ⁿ is false for $n = 3$ n = 3 ( $6 < 8$ 6 < 8) but true from $n = 4$ n = 4, so its basis is $n = 4$ n = 4.

Worked example Proof · mathematical induction

Induction for divisibility

Question

Prove by induction that

3^{2 n} - 1

is divisible by 8 for all

n \in Z^{+}

.

1
Basis, $n = 1$ n = 1: $3^{2} - 1 = 8$ 3² − 1 = 8, which is divisible by 8
2
Assume $3^{2 k} - 1 = 8 M$ 3^2k − 1 = 8M for some $M \in Z$ M ∈ ℤ
3
Write the next case using the old one: $3^{2 (k + 1)} - 1 = 9 \times 3^{2 k} - 1 = 9 (3^{2 k} - 1) + 8$ 3^(2(k+1)) − 1 = 9 × 3^2k − 1 = 9(3^2k − 1) + 8
4
Substitute: $= 9 (8 M) + 8 = 8 (9 M + 1)$ = 9(8M) + 8 = 8(9M + 1), and $9 M + 1$ 9M + 1 is an integer, so 8 divides it
5
Write the conclusion sentence

Answer

P (1)

true and

P (k) \Rightarrow P (k + 1)

, so

3^{2 n} - 1

is divisible by 8 for all

n \in Z^{+}

.

⚠️ Watch out

3^{2 (k + 1)} = 3^{2 k + 2} = 9 \times 3^{2 k}

, not

3^{2 k} + 2

or

6 \times 3^{2 k}

.

Calculate

?In a proof that

6^{n} + 4

is divisible by 5, a student writes

6^{k + 1} + 4 = 6 (6^{k} + 4) - c

. Find

c

.

Quick check

?To prove

\frac{d ^{n}}{d x ^{n}} (x e^{x}) = (x + n) e^{x}

for all

n \in Z^{+}

, you assume

\frac{d ^{k}}{d x ^{k}} (x e^{x}) = (x + k) e^{x}

. Differentiating

(x + k) e^{x}

once, which line correctly finds

\frac{d ^{k + 1}}{d x ^{k + 1}} (x e^{x})

?

Sort it

?A student writes an induction proof. Is each line a required part of a valid proof, or a flaw?

Tap a statement, then tap the group it belongs in. Then press Check.

Calculate

?The inequality

2^{n} > n^{2}

holds for every integer

n \geq N

, and

N

is chosen as small as possible. An induction proof would use

n = N

as its basis. Find

N

.

Mission check

?Why does toppling one domino prove a formula for every

n

?

Mission 2

How can assuming something false prove something true?

Make a guess: How can assuming something false prove something true?

Proof · contradiction and counterexample

Proof by contradiction

To prove a statement, assume its negation (the opposite) is true.
Use valid steps to reach a contradiction: something impossible, or something that clashes with the assumption.
Valid steps cannot turn a true statement into an impossible one, so the assumption must be false. Hence the original statement is true.
Typical uses: a number is irrational (assume it equals $\frac{p}{q}$ p/q in lowest terms), there are infinitely many of something (assume a finite list).

Worked example Proof · contradiction and counterexample

$3$ √3 is irrational

Question

Prove by contradiction that

3

is irrational.

1
Assume $3 = \frac{p}{q}$ √3 = p/q with $p, q \in Z^{+}$ p, q ∈ ℤ⁺ and no common factor (lowest terms)
2
Square and rearrange: $p^{2} = 3 q^{2}$ p² = 3q², so $p^{2}$ p² is a multiple of 3. Since 3 is prime, $p$ p is a multiple of 3
3
Write $p = 3 m$ p = 3m: $9 m^{2} = 3 q^{2}$ 9m² = 3q², so $q^{2} = 3 m^{2}$ q² = 3m², and $q$ q is a multiple of 3 too
4
Then $p$ p and $q$ q share the factor 3, contradicting "lowest terms"

Answer

The assumption is false, so

3

is irrational.

⚠️ Watch out

the step "

p^{2}

is a multiple of 3, so

p

is" needs 3 to be prime. Say so. The same argument fails for

4

, because

p^{2}

a multiple of 4 does not force

p

to be one.

Quick check

?You want to prove by contradiction: "if

a

is rational and

b

is irrational, then

a + b

is irrational". What should the first line assume?

Worked example Proof · contradiction and counterexample

Euclid: there are infinitely many primes

Question

Prove by contradiction that there are infinitely many prime numbers.

1
Assume there are finitely many primes, and list them all: $p_{1}, p_{2}, \dots, p_{n}$ p₁, p₂, …, pₙ
2
Form $N = p_{1} p_{2} \dots p_{n} + 1$ N = p₁ p₂ ⋯ pₙ + 1. Then $N > 1$ N > 1
3
Dividing $N$ N by any $p_{i}$ pᵢ leaves remainder 1, so no prime on the list divides $N$ N
4
But $N > 1$ N > 1 has at least one prime factor, and it is not on the list: a contradiction

Answer

The assumption is false, so there are infinitely many primes.

⚠️ Watch out

the proof does not say

N

itself is prime. It says

N

has a prime factor missing from the list.

Calculate

?Use your GDC or technology to find the smallest prime factor of

2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1

.

Quick check

?To prove

35

is irrational, assume

35 = \frac{p}{q}

in lowest terms. Cubing gives

p^{3} = 5 q^{3}

, so 5 divides

p^{3}

and, as 5 is prime, 5 divides

p

. Writing

p = 5 m

, which equation follows?

Proof · contradiction and counterexample

Disproof by counterexample

A statement claimed for all values is disproved by one counterexample: a value for which it is false.
Give the value and show why it fails. Stating the value alone does not earn the marks.
Example: " $x^{2} + y^{2} = 10$ x² + y² = 10 has no positive integer solutions" is false, since $x = 1$ x = 1, $y = 3$ y = 3 gives $1 + 9 = 10$ 1 + 9 = 10.
Checking many cases that work never proves an "all" statement; one failure disproves it.

Calculate

?Find the smallest

n \in N

for which

n^{2} + 41 n + 41

is not prime.

Sort it

?Is each statement about positive integers always true, or is there a counterexample?

Tap a statement, then tap the group it belongs in. Then press Check.

Mission check

?How can assuming something false prove something true?

Recap

Big ideas

Basis, assumption $P (k)$ P(k), inductive step $P (k) \Rightarrow P (k + 1)$ P(k) ⇒ P(k+1), then the conclusion sentence.
For sums, add the $(k + 1)$ (k+1)th term to the assumed sum and factorise towards the $n = k + 1$ n = k + 1 form.
For divisibility, write $f (k + 1)$ f(k+1) in terms of $f (k)$ f(k) and show it is a multiple of the divisor; the basis can be a value other than 1.
Contradiction: assume the negation of the conclusion, reach an impossibility, conclude the statement is true.
Classic results: $3$ √3 (and $2$ √2, $35$ ∛5) is irrational; there are infinitely many primes; rational + irrational is irrational.
One counterexample, with the reason it fails, disproves an "all" statement; examples alone never prove one.

🏆

Mini-lesson complete!

⭐⭐⭐

You've worked through Proof for IB Diploma Mathematics: Analysis & Approaches HL. 🎉

Mission 1Why does toppling one domino prove a formula for every $n$ n?
Mission 2How can assuming something false prove something true?

Your stars: 0 / 0

Next: more IB Mathematics: Analysis & Approaches · HL lessons and games on the IB Mathematics: Analysis & Approaches · HL page.

📣 Smashed it? Share your score

Challenge a mate to beat your stars, or show a parent how you got on.

→ Back to IB Mathematics: Analysis & Approaches · HL

Specification points and sources for this lesson are listed at the bottom of the page.

Proof

Why does toppling one domino prove a formula for every nn?

The structure of an induction proof

Induction for a sum

Divisibility and other contexts

Induction for divisibility

How can assuming something false prove something true?

Proof by contradiction

3​√3 is irrational

Euclid: there are infinitely many primes

Disproof by counterexample

Big ideas

Mini-lesson complete!

📣 Smashed it? Share your score

Why does toppling one domino prove a formula for every $n$ n?

$3$ √3 is irrational