Free worked solutions · 2026 Edition

Chapter 5: Proof worked solutions

Worked solutions to the practice questions in Chapter 5 of The Ultimate Guide for the IB: Mathematics: Analysis and Approaches HL (2026 Edition). Each solution shows every step with the mark it earns, the way an IB mark scheme does.

Chapter 5 of 19
Volume 1
28 practice questions
4 Going further
Free, no sign-up

Start with Basics All 19 chapters

Basics

One idea at a time, in the order the chapter teaches them.

Question 1

[5 marks]

(a) Prove that the sum of any two consecutive odd numbers is a multiple of 4.

[2]

(b) Show that 6\times 7+7 is a perfect square.

[1]

(c) Prove that n(n+1)+(n+1) is a perfect square for every integer n.

[2]

Show solutionHide solution

(a) let the odd numbers be 2n-1 and 2n+1; sum =4n

4n is 4 times an integer, so the sum is a multiple of 4

(b) 42+7=49=7^2

(c) n(n+1)+(n+1)=(n+1)(n+1)

=(n+1)^2, the square of the integer n+1

Note: accept expanding to n^2+2n+1=(n+1)^2.

Final answer

(a) (2m-1)+(2m+1)=4m
(b) 49=7^2
(c) n(n+1)+(n+1)=(n+1)^2

Question 2

[5 marks]

(a) Show that 7^2 is one more than a multiple of 8.

[1]

(b) Prove that the square of every odd integer is one more than a multiple of 8.

[4]

Show solutionHide solution

(a) 49=48+1=8\times 6+1

(b) let the odd integer be 2m+1; (2m+1)^2=4m^2+4m+1

=4m(m+1)+1

m and m+1 are consecutive integers, so m(m+1) is even

m(m+1)=2k for some integer k, so (2m+1)^2=8k+1

Final answer

(a) 49=8\times6+1
(b) (2m+1)^2=4m(m+1)+1, and m(m+1) is even, so the square is 8k+1

Question 3

[7 marks]

Each statement below is not always true. For each one, give a counterexample and explain why it is a counterexample.

(a) “n^2 + n + 11 is a prime number for every n \in \mathbb{N}.”

[2]

(b) “There are no positive integers x and y for which x^2 - y^2 = 21.”

[2]

(c) “2n^2 - 1 is a prime number for every integer n \ge 2.”

[2]

(d) A student checks the statement in part (a) for n = 0, 1, 2, \ldots, 9 and finds a prime number every time. Explain why this does not prove the statement.

[1]

Show solutionHide solution

(a) n = 10

10^2 + 10 + 11 = 121 = 11 \times 11, which is not prime

Note: accept any n giving a composite value, e.g. n = 11: 143 = 11 \times 13. The R1 needs the value and a factorisation (or a factor).

(b) x = 5, y = 2

25 - 4 = 21, so positive integer solutions do exist

Note: accept x = 11, y = 10 (121 - 100 = 21).

(c) n = 5

2(25) - 1 = 49 = 7 \times 7, which is not prime

Note: for n = 2, 3, 4 the values 7, 17, 31 are prime; accept any other valid n, e.g. n = 9: 161 = 7 \times 23.

(d) the statement is about every n \in \mathbb{N} (infinitely many values); checking finitely many cases cannot rule out a failure for a later n (it fails at n = 10)

Final answer

(a) n=10: 121=11^2
(b) x=5,\ y=2
(c) n=5: 49=7^2
(d) finitely many checks never prove a statement for all n

Question 4

[10 marks]

A real number is rational if it can be written as \dfrac{a}{b}, where a, b \in \mathbb{Z} and b \ne 0.

(a) Let q be rational and x be irrational. Prove by contradiction that q + x is irrational.

[3]

(b) Let x be irrational. Prove by contradiction that \dfrac{1}{x} is irrational.

[3]

(c) You are given that \sqrt{7} is irrational. Use parts (a) and (b) to show that \dfrac{1}{2 + \sqrt{7}} is irrational.

[2]

(d) Show that the statement “if x is irrational, then x^2 is irrational” is not always true.

[2]

Show solutionHide solution

(a) assume q + x is rational: q + x = \dfrac{a}{b}, and q = \dfrac{c}{d}, with a, b, c, d \in \mathbb{Z}, b, d \ne 0

x = \dfrac{a}{b} - \dfrac{c}{d} = \dfrac{ad - bc}{bd}, where ad - bc \in \mathbb{Z} and bd \in \mathbb{Z}, bd \ne 0

so x is rational, which contradicts x irrational; hence q + x is irrational

(b) assume \dfrac{1}{x} = \dfrac{a}{b} with a, b \in \mathbb{Z}, b \ne 0; a \ne 0 because \dfrac{1}{x} \ne 0

then x = \dfrac{b}{a} with a \ne 0

so x is rational, a contradiction; hence \dfrac{1}{x} is irrational

(c) 2 is rational and \sqrt{7} is irrational, so 2 + \sqrt{7} is irrational by (a)

hence its reciprocal \dfrac{1}{2 + \sqrt{7}} is irrational by (b)

(d) x = \sqrt{7}

\sqrt{7} is irrational (given), but x^2 = 7 = \dfrac{7}{1} is rational

Note: accept any irrational x with a rational square, e.g. \sqrt{2}, with the reason that it is irrational.

Final answer

(a), (b) contradiction: x would be rational
(c) 2+\sqrt7 is irrational by (a), so its reciprocal is irrational by (b)
(d) x=\sqrt7, x^2=7

Question 5

[9 marks]

Let Q be one more than the product of the six smallest prime numbers.

(a) Show that Q = 30\,031 and that Q = 59 \times 509.

[2]

(b) Explain why none of the six smallest primes is a factor of Q.

[1]

(c) Prove by contradiction that there are infinitely many prime numbers.

[5]

(d) In the proof in part (c), a number N is formed from a list of primes. Use parts (a) and (b) to explain why the proof does not claim that N itself is prime.

[1]

Show solutionHide solution

(a) the six smallest primes are 2, 3, 5, 7, 11, 13; their product is 30\,030, so Q = 30\,031

59 \times 509 = 29\,500 + 531 = 30\,031

(b) each of these primes divides 30\,030, so each leaves remainder 1 when it divides Q = 30\,031

(c) assume there are only finitely many primes, p_1, p_2, \ldots, p_m

let N = p_1 p_2 \cdots p_m + 1

each p_i divides p_1 p_2 \cdots p_m, so p_i leaves remainder 1 when it divides N; no p_i is a factor of N

N > 1, so N is prime or has a prime factor, and this prime is not in the list

this contradicts the list containing all the primes; hence there are infinitely many primes

(d) N need not be prime: 30\,031 = 59 \times 509 is not prime, but its prime factors 59 and 509 are new primes not in the list; the proof only needs a prime factor of N outside the list

Final answer

(a) 30\,031=59\times509
(b) each prime leaves remainder 1
(c) Euclid's argument
(d) N need not be prime: 30\,031 is not

Question 6

[9 marks]

(a) Use mathematical induction to show that, for every positive integer n,

\sum_{r=1}^{n} r(3r - 1) = n^2(n + 1).

[7]

(b) Hence find the value of 1 \times 2 + 2 \times 5 + 3 \times 8 + \ldots + 20 \times 59.

[2]

Show solutionHide solution

(a) n = 1: LHS = 1 \times 2 = 2, RHS = 1^2 \times 2 = 2, so true for n = 1

assume true for n = k: \displaystyle\sum_{r=1}^{k} r(3r - 1) = k^2(k + 1)

Note: do not award the M1 for “let n = k” or “assume true for n”; the statement must be assumed for n = k.

consider n = k + 1: \displaystyle\sum_{r=1}^{k+1} r(3r - 1) = k^2(k + 1) + (k + 1)\big(3(k + 1) - 1\big)

= (k + 1)(k^2 + 3k + 2)

= (k + 1)(k + 1)(k + 2)

= (k + 1)^2\big((k + 1) + 1\big), so true for n = k + 1

Since P(1) is true and P(k) true implies P(k+1) true, P(n) is true for all n \in \mathbb{Z}^{+} by mathematical induction

Note: award the final R1 only if the M1 for the assumption and the M1 for the inductive step were awarded and the basis is shown.

(b) the rth term is r(3r - 1) with r = 20 last (20 \times 59), so n = 20 (M1)

20^2 \times 21 = 8400

Final answer

(a) step: k^2(k+1)+(k+1)(3k+2)=(k+1)^2(k+2)
(b) 8400

Question 7

[8 marks]

Let f(n) = 7^{n} + 5, where n \in \mathbb{Z}^{+}.

(a) Show that f(1) and f(2) are both divisible by 6.

[1]

(b) Show that f(k + 1) = 7f(k) - 30.

[2]

(c) Hence prove by mathematical induction that f(n) is divisible by 6 for all n \in \mathbb{Z}^{+}.

[5]

Show solutionHide solution

(a) f(1) = 12 = 6 \times 2 and f(2) = 54 = 6 \times 9

(b) f(k + 1) = 7 \times 7^{k} + 5

= 7(7^{k} + 5) - 35 + 5 = 7f(k) - 30

A1AG

(c) f(1) = 12 = 6 \times 2, so true for n = 1

assume true for n = k: 7^{k} + 5 = 6m for some m \in \mathbb{Z}

Note: do not award the M1 for “let n = k” or “assume true for n”; the statement must be assumed for n = k.

consider n = k + 1: f(k + 1) = 7f(k) - 30 = 7(6m) - 30

= 6(7m - 5), which is divisible by 6 since 7m - 5 \in \mathbb{Z}, so true for n = k + 1

Since true for n = 1 and true for n = k implies true for n = k + 1, f(n) is divisible by 6 for all n \in \mathbb{Z}^{+} by mathematical induction

Note: award the final R1 only if the M1 for the assumption and the M1 for the inductive step were awarded and the basis is shown.

Final answer

(a) 12 and 54
(b) f(k+1)=7f(k)-30
(c) 7(6m)-30=6(7m-5)

Question 8

[8 marks]

(a) Show that 3^{n} > 5n + 2 is false for n = 1 and for n = 2.

[1]

(b) Prove by mathematical induction that 3^{n} > 5n + 2 for all integers n \ge 3.

[7]

Show solutionHide solution

(a) 3 < 7 and 9 < 12

(b) n = 3: 27 > 17, so true for n = 3

assume true for n = k, k \ge 3: 3^{k} > 5k + 2

Note: do not award the M1 for “let n = k” or “assume true for n”; the statement must be assumed for n = k.

consider n = k + 1: 3^{k+1} = 3 \times 3^{k} > 3(5k + 2)

= 15k + 6

= 5(k + 1) + 2 + (10k - 1)

> 5(k + 1) + 2 since 10k - 1 > 0 for k \ge 3, so true for n = k + 1

Since true for n = 3 and true for n = k implies true for n = k + 1 (k \ge 3), the statement is true for all integers n \ge 3 by mathematical induction

Note: award the final R1 only if the M1 for the assumption and the M1 for the inductive step were awarded and the basis is shown.

Note: the basis must be n = 3; a basis at n = 1 earns no marks for the basis or the conclusion.

Final answer

(a) 3<7, 9<12
(b) basis n=3: 27>17; step 3^{k+1}>15k+6=5(k+1)+2+(10k-1)

Question 9

[10 marks]

A sequence is defined by u_1 = 5 and u_{n+1} = 4u_n - 6, for n \in \mathbb{Z}^{+}.

(a) Find u_2, u_3 and u_4.

[2]

(b) Prove by mathematical induction that u_n = 3 \times 4^{n-1} + 2 for all n \in \mathbb{Z}^{+}.

[6]

(c) Find the least value of n for which u_n > 10^{6}.

[2]

Show solutionHide solution

(a) u_2 = 14, u_3 = 50

u_4 = 194

(b) n = 1: 3 \times 4^{0} + 2 = 5 = u_1, so true for n = 1

assume true for n = k: u_k = 3 \times 4^{k-1} + 2

Note: do not award the M1 for “let n = k” or “assume true for n”; the statement must be assumed for n = k.

consider n = k + 1: u_{k+1} = 4u_k - 6 = 4\left(3 \times 4^{k-1} + 2\right) - 6

= 3 \times 4^{k} + 8 - 6

= 3 \times 4^{(k+1)-1} + 2, so true for n = k + 1

Since P(1) is true and P(k) true implies P(k+1) true, P(n) is true for all n \in \mathbb{Z}^{+} by mathematical induction

Note: award the final R1 only if the M1 for the assumption and the M1 for the inductive step were awarded and the basis is shown.

(c) 3 \times 4^{n-1} + 2 > 10^{6} \Rightarrow 3 \times 4^{n-1} > 999\,998; \ 3 \times 4^{9} = 786\,432, 3 \times 4^{10} = 3\,145\,728

n - 1 = 10, so n = 11 (u_{10} = 786\,434, u_{11} = 3\,145\,730)

Final answer

(a) 14,\ 50,\ 194
(b) 4(3\times4^{k-1}+2)-6=3\times4^k+2
(c) n=11

Tutorial

Exam-style questions on each question type, with the marks the IB would give.

Question 10

[5 marks]

(a) Show that (n+3)^2 - (n-1)^2 \equiv 8(n+1).

[2]

(b) Hence prove that the difference of the squares of two odd integers that differ by 4 is a multiple of 8 but is never a multiple of 16.

[3]

Show solutionHide solution

(a) (n+3)^2 - (n-1)^2 = (n^2+6n+9) - (n^2-2n+1).

[1]

= 8n + 8 = 8(n+1).

[1]

(b) The odd integers are n-1 and n+3, so n is even; let n = 2m.

[1]

Then the difference is 8(2m+1), which is a multiple of 8.

[1]

Since 2m+1 is odd, 8(2m+1) = 16m + 8 leaves remainder 8 on division by 16, so it is never a multiple of 16.

[1]

Final answer

(a) 8(n+1)
(b) n=2m: 8(2m+1)=16m+8, remainder 8 on division by 16

Question 11

[4 marks]

Alex claims that n^2 + 3n + 1 is prime for every positive integer n.

(a) Find a counterexample and show that it is one.

[3]

(b) Explain why checking n=1,2,3,4,5 would not have been enough to prove Alex's claim, even though it holds for all of them.

[1]

Show solutionHide solution

; (a) n=6: 36+18+1 = 55.

[1]

55 = 5\times11, so it is not prime.

[1]

Hence the claim is false.

[1]

(b) A finite number of successful cases proves nothing about all n: (n=1,\dots,5 give 5,11,19,29,41, all prime) yet n=6 fails.

[1]

Final answer

(a) n=6: 55=5\times11
(b) 5,\,11,\,19,\,29,\,41 are prime, but finitely many cases prove nothing

Question 12

[7 marks]

Consider the equation 4x^3 + 6x - 5 = 0.

(a) Use your GDC to find the real solution(s) of the equation, correct to 3 s.f.

[2]

(b) Prove by contradiction that the equation has no integer solution.

[5]

Show solutionHide solution

; (a) GDC: graph y = 4x^3+6x-5 (or use the numerical solver). The graph crosses the x-axis once.

[1]

x \approx 0.650.

[1]

(b) Assume there is an integer solution x = a, so 4a^3 + 6a - 5 = 0.

[1]

Then 4a^3 + 6a = 5, i.e. 2(2a^3+3a) = 5.

[1]

2a^3+3a is an integer, so the left side is even.

[1]

The right side, 5, is odd.

[1]

An even number cannot equal an odd number: a contradiction. So there is no integer solution.

[1]

Final answer

(a) x\approx0.650 (one real root)
(b) 2(2a^3+3a)=5: even = odd

Question 13

[6 marks]

The positive real numbers a and b satisfy a^2 + b^2 = 8. Prove by contradiction that a + b \leq 4.

[6]

Show solutionHide solution

; Assume a + b > 4.

[1]

Both sides are positive, so squaring preserves the inequality: (a+b)^2 > 16.

[1]

a^2 + 2ab + b^2 > 16, and since a^2+b^2 = 8, this gives 2ab > 8.

[1]

Now (a-b)^2 \geq 0 gives a^2 + b^2 \geq 2ab, i.e. 2ab \leq 8.

[1]

So 2ab > 8 and 2ab \leq 8 cannot both hold: a contradiction.

[1]

Hence a + b \leq 4.

[1]

Final answer

assume a+b>4, so 2ab>8; but (a-b)^2\ge0 gives 2ab\le8. Equality at a=b=2

Question 14

[6 marks]

Prove by mathematical induction that

\sum_{r=1}^{n} r\cdot3^{\,r} = \frac{(2n-1)\,3^{\,n+1}+3}{4} \quad\text{for all } n\in\mathbb{Z}^+.

[6]

Show solutionHide solution

; Base (n=1): LHS =3, RHS =\dfrac{(1)(9)+3}{4} = 3.

[1]

Assume \displaystyle\sum_{r=1}^{k} r\cdot3^r = \frac{(2k-1)3^{k+1}+3}{4} for some k\in\mathbb{Z}^+.

[1]

Step: add the term (k+1)3^{k+1}: \;\dfrac{(2k-1)3^{k+1}+3}{4} + (k+1)3^{k+1}.

[1]

Factor out 3^{k+1}: \;\dfrac{3^{k+1}\bigl[(2k-1)+4(k+1)\bigr]+3}{4} = \dfrac{3^{k+1}(6k+3)+3}{4}.

[1]

= \dfrac{3^{k+1}\cdot3(2k+1)+3}{4} = \dfrac{(2k+1)3^{k+2}+3}{4} = \dfrac{\bigl(2(k+1)-1\bigr)3^{(k+1)+1}+3}{4}.

[1]

True for n=1 and P(k)\Rightarrow P(k+1), so by induction true for all n\in\mathbb{Z}^+.

[1]

Final answer

step: \dfrac{(2k-1)3^{k+1}+3}{4}+(k+1)3^{k+1}=\dfrac{(2k+1)3^{k+2}+3}{4}

Question 15

[6 marks]

Prove by mathematical induction that 9^{\,n+1} + 8n - 9 is divisible by 16 for all n \in \mathbb{Z}^+.

[6]

Show solutionHide solution

; Base (n=1): 81 + 8 - 9 = 80 = 16\times5, divisible by 16.

[1]

Assume 9^{k+1} + 8k - 9 = 16m for some k\in\mathbb{Z}^+ and m\in\mathbb{Z}, so 9^{k+1} = 16m - 8k + 9.

[1]

Step: 9^{k+2} + 8(k+1) - 9 = 9\cdot9^{k+1} + 8k - 1.

[1]

= 9(16m - 8k + 9) + 8k - 1.

[1]

= 144m - 72k + 81 + 8k - 1 = 144m - 64k + 80 = 16(9m - 4k + 5), divisible by 16.

[1]

True for n=1 and P(k)\Rightarrow P(k+1), so true for all n\in\mathbb{Z}^+.

[1]

Final answer

basis 80=16\times5; step: 9(16m-8k+9)+8k-1=16(9m-4k+5)

Question 16

[7 marks]

(a) Show that 6! < 3^6 but 7! > 3^7.

[2]

(b) Hence prove by mathematical induction that n! > 3^n for all integers n\geq7.

[5]

Show solutionHide solution

; (a) 6! = 720 < 729 = 3^6.

[1]

7! = 5040 > 2187 = 3^7.

[1]

(b) Base (n=7): 7! = 5040 > 2187 = 3^7 by (a).

[1]

Assume k! > 3^k for some integer k\geq7.

[1]

Step: (k+1)! = (k+1)\,k! > (k+1)\,3^k.

[1]

Since k\geq7, k+1\geq8 > 3, so (k+1)3^k > 3\cdot3^k = 3^{k+1}.

[1]

True for n=7 and P(k)\Rightarrow P(k+1) for k\geq7, so true for all integers n\geq7.

[1]

Final answer

(a) 720<729, 5040>2187
(b) (k+1)!>(k+1)3^k>3^{k+1}, as k+1\ge8>3

Question 17

[6 marks]

Let f(x) = \ln(1+2x) for x > -\tfrac12. Prove by mathematical induction that

f^{(n)}(x) = \frac{(-1)^{n-1}\,2^n\,(n-1)!}{(1+2x)^n} \quad\text{for all } n\in\mathbb{Z}^+,

where f^{(n)} denotes the nth derivative of f.

[6]

Show solutionHide solution

; Base (n=1): f'(x) = \dfrac{2}{1+2x}, and the formula gives \dfrac{(-1)^0\,2^1\,0!}{(1+2x)^1} = \dfrac{2}{1+2x}.

[1]

Assume f^{(k)}(x) = (-1)^{k-1}2^k(k-1)!\,(1+2x)^{-k} for some k\in\mathbb{Z}^+.

[1]

Step: differentiate with the chain rule:

f^{(k+1)}(x) = (-1)^{k-1}2^k(k-1)!\cdot(-k)(1+2x)^{-k-1}\cdot2.

[1]

= (-1)^{k-1}(-1)\,2^{k+1}\,k\,(k-1)!\,(1+2x)^{-(k+1)}.

[1]

= \dfrac{(-1)^{k}\,2^{k+1}\,k!}{(1+2x)^{k+1}}, which is the formula with n=k+1.

[1]

True for n=1 and P(k)\Rightarrow P(k+1), so true for all n\in\mathbb{Z}^+.

[1]

Final answer

step: differentiate (-1)^{k-1}2^k(k-1)!(1+2x)^{-k} to get (-1)^k2^{k+1}k!(1+2x)^{-(k+1)}

Question 18

[8 marks]

Let g(x)=\dfrac{1}{3x+2}, for x>-\frac23.

(a) Find g'(x) and g''(x).

[2]

(b) Use mathematical induction to show that, for every positive integer n, g^{(n)}(x)=\dfrac{(-3)^n\,n!}{(3x+2)^{n+1}}.

[6]

Show solutionHide solution

(a) g(x)=(3x+2)^{-1}, so g'(x)=-3(3x+2)^{-2}.

g''(x)=18(3x+2)^{-3}.

(b) Let P(n) be the statement g^{(n)}(x)=(-3)^n\,n!\,(3x+2)^{-(n+1)}. For n=1: (-3)^1\,1!\,(3x+2)^{-2}=-3(3x+2)^{-2}=g'(x), so P(1) is true.

Assume P(k) is true for some k\in\mathbb{Z}^+: g^{(k)}(x)=(-3)^k\,k!\,(3x+2)^{-(k+1)}.

Differentiate the assumed formula with the chain rule, the inner derivative being 3: g^{(k+1)}(x)=(-3)^k\,k!\times\bigl(-(k+1)\bigr)\times3\times(3x+2)^{-(k+2)}.

=(-3)^k(-3)(k+1)\,k!\,(3x+2)^{-(k+2)}.

=(-3)^{k+1}(k+1)!\,(3x+2)^{-((k+1)+1)}, which is P(k+1).

Since P(1) is true, and P(k) true implies P(k+1) true, P(n) is true for all n\in\mathbb{Z}^+ by mathematical induction.

Final answer

(a) g'(x)=-3(3x+2)^{-2}, g''(x)=18(3x+2)^{-3}
(b) step: (-3)^kk!\times\bigl(-(k+1)\bigr)\times3\times(3x+2)^{-(k+2)}=(-3)^{k+1}(k+1)!\,(3x+2)^{-(k+2)}

Mastery

Full exam questions that mix question types, at Paper 1 and Paper 2 standard.

Question 19

[6 marks]

Consider any five consecutive integers, n-2, n-1, n, n+1 and n+2.

(a) Show that these five integers always add up to a multiple of 5.

[2]

(b) Show that the squares of these five integers always add up to a multiple of 5.

[4]

Show solutionHide solution

(a)

(n-2)+(n-1)+n+(n+1)+(n+2) = 5n

which is always divisible by 5.

[2]

(b)

Squaring each integer in turn gives n^2 \mp 4n + 4, n^2 \mp 2n + 1 and n^2 for the middle one. The terms in n cancel in pairs, leaving

5n^2 + 2(4) + 2(1) = 5n^2 + 10 = 5\left(n^2+2\right).

Since n^2 + 2 \in \mathbb{Z}, the sum has 5 as a factor.

[4]

Final answer

(a) 5n
(b) 5n^2+10=5(n^2+2)

Question 20

[6 marks]

Let a and b be integers such that a^{2} + b^{2} is divisible by 4.

Using proof by contradiction, show that a and b cannot both be odd.

[6]

Show solutionHide solution

Suppose, for a contradiction, that a and b are both odd. Then they can be written

a = 2m + 1, \qquad b = 2p + 1, \qquad m,\,p \in \mathbb{Z}

so that

a^{2} + b^{2} = (2m + 1)^{2} + (2p + 1)^{2} = 4m^{2} + 4m + 1 + 4p^{2} + 4p + 1

= 4\left(m^{2} + m + p^{2} + p\right) + 2

The bracket is an integer, so a^{2} + b^{2} leaves remainder 2 on division by 4, and is therefore not divisible by 4.

This contradicts the assumption that 4 divides a^{2} + b^{2}. Hence a and b cannot both be odd.

[6]

Final answer

(2m+1)^2+(2p+1)^2=4(m^2+m+p^2+p)+2, which is not divisible by 4

Question 21

[6 marks]

Prove by contradiction that r^2 - 8s - 13 \neq 0, for any r, s \in \mathbb{Z}.

[6]

Show solutionHide solution

Assume, for contradiction, that r^2 - 8s - 13 = 0, where r, s \in \mathbb{Z}.

Since

r^2 = 8s + 13 = 2(4s + 6) + 1,

r^2 is odd, so r is odd.

Let r = 2k + 1, where k \in \mathbb{Z}. Then

(2k+1)^2 = 8s + 13

4k^2 + 4k + 1 = 8s + 13

4k^2 + 4k = 8s + 12

2k^2 + 2k = 4s + 6

k^2 + k = 2s + 3.

The left-hand side k^2 + k = k(k+1) is a product of two consecutive integers and is therefore even, while the right-hand side 2s + 3 is odd.

This is a contradiction, since an even number cannot equal an odd number.

Therefore, if r, s \in \mathbb{Z}, then

r^2 - 8s - 13 \neq 0. \quad \textbf{[6]}

Final answer

r is odd, r=2k+1, so k^2+k=2s+3: even = odd

Question 22

[6 marks]

Using proof by contradiction, establish that x + \dfrac{16}{x} \geq 8 for every x \in \mathbb{R} with x > 0.

[6]

Show solutionHide solution

Suppose, for a contradiction, that there is some x \in \mathbb{R} with x > 0 for which

x + \frac{16}{x} < 8

Because x > 0, multiplying through by x leaves the inequality unchanged in direction:

x^{2} + 16 < 8x

Rearranging:

x^{2} - 8x + 16 < 0

(x - 4)^{2} < 0

This is impossible: the square of a real number is never negative.

The assumption therefore fails, and so x + \dfrac{16}{x} \geq 8 for every x \in \mathbb{R} with x > 0.

[6]

Final answer

assume x+\frac{16}{x}<8, so (x-4)^2<0

Question 23

[5 marks]

Using proof by contradiction, establish that \sqrt{5xy} \leq \dfrac{1}{2}\left(5x + y\right) for all x,\,y \in \mathbb{R}^{+}.

[5]

Show solutionHide solution

Suppose, for a contradiction, that there exist x,\,y \in \mathbb{R}^{+} with

\sqrt{5xy} > \frac{1}{2}\left(5x + y\right)

Both sides are positive (as x,\,y > 0), so squaring preserves the inequality:

5xy > \frac{1}{4}\left(5x + y\right)^{2}

20xy > \left(5x + y\right)^{2} = 25x^{2} + 10xy + y^{2}

0 > 25x^{2} - 10xy + y^{2}

0 > \left(5x - y\right)^{2}

A square of a real number cannot be negative, so this is a contradiction.

Hence \sqrt{5xy} \leq \dfrac{1}{2}\left(5x + y\right) for all x,\,y \in \mathbb{R}^{+}.

[5]

Final answer

assume \sqrt{5xy}>\frac12(5x+y), so (5x-y)^2<0

Question 24

[7 marks]

Prove by mathematical induction that

\sum_{r=1}^{n} (2r - 1)\,3^{r-1} = (n - 1)\,3^{n} + 1

for all n \in \mathbb{Z}^+.

[7]

Show solutionHide solution

Let P(n) be the proposition that \displaystyle\sum_{r=1}^{n} (2r-1)\,3^{r-1} = (n-1)\,3^{n} + 1.

Base case. For n = 1:

\text{LHS} = (2 - 1)\,3^{0} = 1, \qquad \text{RHS} = 0 \times 3 + 1 = 1

so P(1) is true. M1A1

Inductive step. Assume P(k) is true for some k \in \mathbb{Z}^+:

\sum_{r=1}^{k} (2r-1)\,3^{r-1} = (k-1)\,3^{k} + 1 \quad \textbf{M1}

Adding the (k+1)th term, (2k+1)\,3^{k}:

\sum_{r=1}^{k+1} (2r-1)\,3^{r-1} = (k-1)\,3^{k} + 1 + (2k+1)\,3^{k} \quad \textbf{M1}

= 3^{k}\left[(k-1) + (2k+1)\right] + 1 = 3k \times 3^{k} + 1 = k \times 3^{k+1} + 1 = \big((k+1) - 1\big)\,3^{k+1} + 1 \quad \textbf{A1}

which is P(k+1).

Conclusion. P(1) is true and P(k) \Rightarrow P(k+1), so by mathematical induction P(n) is true for all n \in \mathbb{Z}^+.

R1[7]

Final answer

step: (k-1)3^k+1+(2k+1)3^k=k\times3^{k+1}+1

Question 25

[7 marks]

Using mathematical induction, together with the identity \displaystyle\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} for 1 \le r \le n-1, prove that

\sum_{r=0}^{n}\binom{n}{r} = 2^{n} \quad \text{for all } n \in \mathbb{Z}^{+}.

[7]

Show solutionHide solution

Proof by induction:

Base case n = 1: \displaystyle\sum_{r=0}^{1}\binom{1}{r} = 1 + 1 = 2 = 2^{1}, so the result holds for n = 1.

Assume the result is true for n = k, that is

\sum_{r=0}^{k}\binom{k}{r} = 2^{k} \quad \text{for some } k \in \mathbb{Z}^{+}.

Consider n = k + 1. The first and last terms are both 1, and the rest are split using the given identity:

\sum_{r=0}^{k+1}\binom{k+1}{r} = 1 + \sum_{r=1}^{k}\left[\binom{k}{r-1} + \binom{k}{r}\right] + 1

Separating the two sums:

= \left[1 + \sum_{r=1}^{k}\binom{k}{r-1}\right] + \left[\sum_{r=1}^{k}\binom{k}{r} + 1\right] = \sum_{r=0}^{k-1}\binom{k}{r} + \binom{k}{k} + \binom{k}{0} + \sum_{r=1}^{k}\binom{k}{r}

Each bracket is a full sum \displaystyle\sum_{r=0}^{k}\binom{k}{r}, so by the inductive hypothesis:

\sum_{r=0}^{k+1}\binom{k+1}{r} = 2^{k} + 2^{k} = 2^{k+1}

Hence the result is true for n = k + 1 whenever it is true for n = k. Since it is true for n = 1, it is true for all n \in \mathbb{Z}^{+} by mathematical induction.

R1[7]

Final answer

split with Pascal's identity: 2^k+2^k=2^{k+1}

Question 26

[7 marks]

Use mathematical induction to establish that 9^{2n} - 5^{2n} is divisible by 56 for every n \in \mathbb{Z}^{+}.

[7]

Show solutionHide solution

Base case. For n = 1:

9^{2} - 5^{2} = 81 - 25 = 56

which is divisible by 56, so the statement holds for n = 1.

Inductive step. Assume it holds for n = k, that is

9^{2k} - 5^{2k} = 56s \quad \text{for some } s \in \mathbb{Z}

Then for n = k + 1:

9^{2(k+1)} - 5^{2(k+1)} = 81 \cdot 9^{2k} - 25 \cdot 5^{2k}

= 56 \cdot 9^{2k} + 25 \cdot 9^{2k} - 25 \cdot 5^{2k}

= 56 \cdot 9^{2k} + 25\left(9^{2k} - 5^{2k}\right)

= 56 \cdot 9^{2k} + 25(56s) = 56\left(9^{2k} + 25s\right)

Since 9^{2k} + 25s \in \mathbb{Z}, the expression is divisible by 56, so the statement holds for n = k + 1.

Conclusion. True for n = 1, and true for k implies true for k + 1; by induction it is true for every n \in \mathbb{Z}^{+}.

[7]

Final answer

81\times9^{2k}-25\times5^{2k}=56\times9^{2k}+25(56s)

Question 27

[7 marks]

Sam claims that \log_{2}(n+1) \leq n for every n \in \mathbb{Z}^{+}.

(a) Show that \log_{2}(n+2) \leq 1 + \log_{2}(n+1) for n \in \mathbb{Z}^{+}.

[2]

(b) Use mathematical induction, together with the result of part (a), to prove Sam's claim.

[5]

Show solutionHide solution

(a) 1 + \log_2(n+1) = \log_2\left(2(n+1)\right) = \log_2(2n+2)

Since n + 2 \leq 2n + 2 for n \geq 0 and \log_2 is increasing,

\log_2(n+2) \leq \log_2(2n+2) = 1 + \log_2(n+1) \qquad \blacksquare

AG[2]

(b) Base case n = 1: \log_2 2 = 1 \leq 1, true.

Assume \log_2(k+1) \leq k for some k \in \mathbb{Z}^{+}.

Then, using (a),

\log_2(k+2) \leq 1 + \log_2(k+1) \leq 1 + k = (k+1)

so the statement holds for n = k+1.

True for n = 1, and true for n = k \Rightarrow true for n = k+1; hence by induction true for all n \in \mathbb{Z}^{+}.

R1[5]

Final answer

(a) 1+\log_2(n+1)=\log_2(2n+2)\ge\log_2(n+2)
(b) \log_2(k+2)\le1+\log_2(k+1)\le k+1

Question 28

[15 marks]

The Fibonacci sequence is defined by F_1 = 1, F_2 = 1 and F_{n+2} = F_{n+1} + F_n for n\in\mathbb{Z}^+.

(a) Write down F_3, F_4, \ldots, F_8.

[1]

(b) Prove by mathematical induction that \displaystyle\sum_{r=1}^{n}F_r = F_{n+2} - 1 for all n\in\mathbb{Z}^+.

[5]

(c) Prove by mathematical induction that F_{n+2}F_n - F_{n+1}^{\,2} = (-1)^{n+1} for all n\in\mathbb{Z}^+.

[6]

(d) Use the result of part (c) to prove by contradiction that, for every n\in\mathbb{Z}^+, F_n and F_{n+1} have no common factor greater than 1.

[3]

Show solutionHide solution

; (a) 2,\ 3,\ 5,\ 8,\ 13,\ 21.

[1]

(b) Base (n=1): LHS =F_1=1; RHS =F_3-1 = 2-1 = 1.

[1]

Assume \displaystyle\sum_{r=1}^{k}F_r = F_{k+2}-1 for some k\in\mathbb{Z}^+.

[1]

Step: \displaystyle\sum_{r=1}^{k+1}F_r = F_{k+2} - 1 + F_{k+1}.

[1]

= (F_{k+2}+F_{k+1}) - 1 = F_{k+3} - 1, which is the statement with n=k+1.

[1]

True for n=1 and P(k)\Rightarrow P(k+1), so true for all n\in\mathbb{Z}^+.

[1]

(c) Base (n=1): F_3F_1 - F_2^2 = 2 - 1 = 1 = (-1)^2.

[1]

Assume F_{k+2}F_k - F_{k+1}^2 = (-1)^{k+1} for some k\in\mathbb{Z}^+.

[1]

Step: F_{k+3}F_{k+1} - F_{k+2}^2 = (F_{k+2}+F_{k+1})F_{k+1} - F_{k+2}^2.

[1]

= F_{k+2}(F_{k+1} - F_{k+2}) + F_{k+1}^2 = -F_{k+2}F_k + F_{k+1}^2, using F_{k+2}-F_{k+1}=F_k.

[1]

= -\bigl(F_{k+2}F_k - F_{k+1}^2\bigr) = -(-1)^{k+1} = (-1)^{k+2}, using the assumption.

[1]

This is the statement with n=k+1. True for n=1 and P(k)\Rightarrow P(k+1), so true for all n\in\mathbb{Z}^+.

[1]

(d) Assume that some integer d>1 divides both F_n and F_{n+1}.

[1]

Then d divides F_{n+2}F_n and F_{n+1}^2, hence divides F_{n+2}F_n - F_{n+1}^2 = \pm1 by (c).

[1]

An integer d>1 cannot divide \pm1: a contradiction, so there is no common factor greater than 1.

[1]

Final answer

(a) 2,\,3,\,5,\,8,\,13,\,21
(b) \sum F_r=F_{n+2}-1 by induction
(c) F_{n+2}F_n-F_{n+1}^2=(-1)^{n+1} by induction
(d) a common factor d>1 would divide \pm1: contradiction

Going further

Beyond the syllabus: the worked examples and investigations of the chapter's Going further pages.

G1 Cauchy–Schwarz from a discriminant

G1 Worked example

[9 marks]

Use the Cauchy–Schwarz inequality, \left(a_1b_1+a_2b_2\right)^2\le\left(a_1^2+a_2^2\right)\left(b_1^2+b_2^2\right), with equality exactly when (a_1,a_2) is a multiple of (b_1,b_2).

(a) Real numbers x and y satisfy x+y=5. By taking a_1=\sqrt2\,x, a_2=\sqrt3\,y, b_1=\dfrac1{\sqrt2} and b_2=\dfrac1{\sqrt3}, show that 2x^2+3y^2\ge30.

[3]

(b) Find the values of x and y for which 2x^2+3y^2=30.

[2]

(c) Check your answers to (a) and (b) by writing 2x^2+3y^2 as a quadratic in x only.

[2]

(d) Show that if p,q>0 and x+y=s, then px^2+qy^2\ge\dfrac{pq\,s^2}{p+q}.

[2]

Show solutionHide solution

(a) a_1b_1+a_2b_2=x+y=5

a_1^2+a_2^2=2x^2+3y^2 and b_1^2+b_2^2=\frac12+\frac13=\frac56

25\le\left(2x^2+3y^2\right)\times\frac56, so 2x^2+3y^2\ge30

A1AG

(b) equality when \left(\sqrt2\,x,\sqrt3\,y\right)=\lambda\left(\frac1{\sqrt2},\frac1{\sqrt3}\right), that is 2x=3y=\lambda

\frac\lambda2+\frac\lambda3=5 gives \lambda=6: x=3, y=2

(c) y=5-x: 2x^2+3(5-x)^2=5x^2-30x+75

=5(x-3)^2+30\ge30, with equality at x=3, y=2

(d) take a_1=\sqrt p\,x, a_2=\sqrt q\,y, b_1=\frac1{\sqrt p}, b_2=\frac1{\sqrt q}: s^2\le\left(px^2+qy^2\right)\left(\frac1p+\frac1q\right)

\frac1p+\frac1q=\frac{p+q}{pq}, so px^2+qy^2\ge\dfrac{pq\,s^2}{p+q}

A1AG

Note: with p=2, q=3, s=5 this gives \frac{6\times25}{5}=30, as in (a).

Final answer

(b) x=3, y=2

G1 Investigation

[12 marks]

This investigation proves the Cauchy–Schwarz inequality for two and three pairs of numbers without a discriminant, and then uses it.

(a) For a=(1,3), b=(2,5), and then for a=(2,-1), b=(4,-2), compare \left(a_1b_1+a_2b_2\right)^2 with \left(a_1^2+a_2^2\right)\left(b_1^2+b_2^2\right).

[2]

(b) Show that \left(a_1^2+a_2^2\right)\left(b_1^2+b_2^2\right)-\left(a_1b_1+a_2b_2\right)^2=\left(a_1b_2-a_2b_1\right)^2. Hence prove the inequality for two pairs, and state when equality holds.

[3]

(c) Write \displaystyle\left(\sum_{i=1}^{3}a_i^2\right)\left(\sum_{i=1}^{3}b_i^2\right)-\left(\sum_{i=1}^{3}a_ib_i\right)^2 as a sum of three squares. Hence state the condition for equality when there are three pairs.

[3]

(d) Find the least value of x^2+y^2+z^2 when x+2y+2z=9, and the values of x, y and z for which it occurs. Interpret your answer geometrically.

[4]

Show solutionHide solution

(a) (2+15)^2=289 and (1+9)(4+25)=290: just below

(8+2)^2=100 and 5\times20=100: equal, and here b=2a

(b) the product is a_1^2b_1^2+a_1^2b_2^2+a_2^2b_1^2+a_2^2b_2^2 and the square is a_1^2b_1^2+2a_1a_2b_1b_2+a_2^2b_2^2

difference =a_1^2b_2^2-2a_1a_2b_1b_2+a_2^2b_1^2=\left(a_1b_2-a_2b_1\right)^2

a square is never negative, so the inequality holds; equality exactly when a_1b_2=a_2b_1, that is when one pair is a multiple of the other

(c) \left(a_1b_2-a_2b_1\right)^2+\left(a_1b_3-a_3b_1\right)^2+\left(a_2b_3-a_3b_2\right)^2

M1A1

equality exactly when all three brackets are 0, that is when (a_1,a_2,a_3) and (b_1,b_2,b_3) are multiples of one another

(d) (1\times x+2y+2z)^2\le\left(1^2+2^2+2^2\right)\left(x^2+y^2+z^2\right)

81\le9\left(x^2+y^2+z^2\right), so the least value is 9

equality when (x,y,z)=\lambda(1,2,2); then 9\lambda=9, so (x,y,z)=(1,2,2)

x^2+y^2+z^2 is the squared distance from the origin, so (1,2,2) is the point of the plane x+2y+2z=9 nearest the origin, at distance 3

Final answer

(a) 289<290; 100=100
(d) 9, at (1,2,2): the nearest point of the plane to the origin, distance 3

G2 Which totals can you make?

G2 Worked example

[9 marks]

Stamps are sold in values of 5c and 8c. A total of n cents, n\in\mathbb{N}, is called makeable if n=5x+8y for some x,y\in\mathbb{N}.

(a) Show that 27 is not makeable.

[2]

(b) Show that 28, 29, 30, 31 and 32 are all makeable.

[1]

(c) Prove by induction that, for every integer m\ge28, the five totals m,m+1,m+2,m+3,m+4 are all makeable. Deduce that every total of 28c or more is makeable.

[4]

(d) List the totals that are not makeable, and state how many there are.

[2]

Show solutionHide solution

(a) 27-8y for y=0,1,2,3 is 27,19,11,3

none is a multiple of 5, and y\ge4 makes 27-8y negative, so 27 is not makeable

(b) 28=5\times4+8, 29=5+8\times3, 30=5\times6, 31=5\times3+8\times2, 32=8\times4

(c) P(m): m,\dots,m+4 are all makeable. P(28) is true by (b)

assume P(k) for some k\ge28

k+1,\dots,k+4 are makeable by P(k), and k+5 is k with one more 5c stamp, so P(k+1) is true

P(28) is true and P(k) implies P(k+1), so P(m) is true for all m\ge28; each total n\ge28 is the first of the five in P(n), so it is makeable

(d) 1,2,3,4,6,7,9,11,12,14,17,19,22,27

14 totals

Final answer

(d) 1,2,3,4,6,7,9,11,12,14,17,19,22,27: 14 totals

G2 Investigation

[13 marks]

Let a and b be positive integers with no common factor other than 1. A total n\in\mathbb{N} is called makeable if n=ax+by for some x,y\in\mathbb{N}.

(a) For each of (a,b)=(3,5), (4,7) and (5,7), list the totals that are not makeable and write down the largest, L.

[3]

(b) Conjecture a formula for L in terms of a and b.

[1]

(c) Suppose that the a consecutive totals m,m+1,\dots,m+a-1 are all makeable. Prove by induction that every total n\ge m is makeable.

[4]

(d) You may use the fact that, for c\in\mathbb{Z}^+, if b is a factor of ac then b is a factor of c, and if a is a factor of bc then a is a factor of c. Prove by contradiction that ab-a-b is not makeable.

[4]

(e) For (a,b)=(4,6), which have a common factor, explain why there is no largest total that is not makeable.

[1]

Show solutionHide solution

(a) (3,5): 1,2,4,7, so L=7

(4,7): 1,2,3,5,6,9,10,13,17, so L=17

(5,7): 1,2,3,4,6,8,9,11,13,16,18,23, so L=23

(b) L=ab-a-b (check: 15-8=7, 28-11=17, 35-12=23)

(c) P(j): the a totals j,j+1,\dots,j+a-1 are all makeable. P(m) is given

assume P(k) for some k\ge m

k+1,\dots,k+a-1 are makeable by P(k), and k+a=a(x+1)+by if k=ax+by, so P(k+1) is true

so P(j) is true for all j\ge m, and each n\ge m is the first total in P(n), so it is makeable

(d) assume ab-a-b=ax+by with x,y\in\mathbb{N}

then ab=a(x+1)+b(y+1), so a(x+1)=b(a-y-1), and b is a factor of a(x+1)

by the given fact b is a factor of x+1\ge1, so x+1\ge b; in the same way a is a factor of y+1, so y+1\ge a

then a(x+1)+b(y+1)\ge ab+ab=2ab>ab, a contradiction, so ab-a-b is not makeable

(e) 4x+6y is always even, so no odd total is makeable, and there are odd totals as large as you like

Final answer

(a) 7, 17, 23
(b) L=ab-a-b
(e) every makeable total is even

TI-84 Plus CE keystrokes

The GDC panels in the book give keystrokes for the TI-Nspire CX II and the Casio fx-CG50. These are the TI-84 Plus CE keystrokes for the same calculator jobs. The full list of TI-84 keystrokes is in Chapter 19.

Job	TI-84 Plus CE keystrokes
Solve an equation	`MATH, Numeric Solver (MATH, 0:Solver on older OS versions): enter the equation, then SOLVE. Or graph both sides and use 2nd TRACE (CALC), 5:intersect`

From the book

The Ultimate Guide for the IB: Mathematics: Analysis and Approaches HL

Chapter 5 teaches proof from the basics to full exam questions: how the IB asks it, every question type with a marked example, and these practice questions in three steps.

About the book