DP Maths AA HL - Number and Algebra - Binomial Theorem

DP Maths AA HL - Number and Algebra - Binomial Theorem - Full notes

RevisionPrep

DP Maths AA HL | Binomial Theorem

Binomial Theorem

This topic contains 3 notes:

1.6 Proof and Binomial Theorem
1.10 Counting Principles
1.15 Further Proof

DP MATHEMATICS AA · TOPIC 1: NUMBER AND ALGEBRA

1.6

Proof and the Binomial Theorem

Full notes for HL · Syllabus SL 1.6, 1.9

Contents

1	What is a proof?
2	Notation and the language of proof
3	Writing deductive proofs
4	Proving identities
5	Pascal's triangle and binomial expansions
6	Factorials and binomial coefficients
7	The binomial theorem
8	Finding a specific term or coefficient
9	Products of expansions and approximations
10	Direct proofs with integers
11	Proving algebraic identities
12	Proofs involving inequalities
13	Errors in proof
14	Patterns in Pascal's triangle
15	Expansions with fractions and negative terms
16	Finding coefficients with x in both terms
17	Products of two expansions
18	Approximations using the binomial theorem
19	Binomial coefficients in counting and probability
20	Mixed review and exam practice
21	Exam-style questions with markscheme
22	Common misconceptions and links
23	Check your understanding
24	Summary and topic map
25	Answers to practice exercises

These are full teaching notes. Read each section in order, try the Think about it question before you read on, and work through every worked example before attempting the Quick check.

Before you start

Rate yourself on each statement now, and again after you've worked through the notes. Shade R (not yet), A (getting there) or G (confident).

I can…	R	A	G
explain the difference between checking examples and proving a statement
use the notation ≡, ⇒, ⇔, ∀, ∈, ℤ, ℚ, ℝ correctly
write deductive proofs about integers (odd, even, consecutive, multiples)
prove algebraic identities working from one side to the other
expand (a + b)n using Pascal's triangle and the binomial theorem
evaluate nCr with and without technology
find a specific term, coefficient or constant term
use expansions to find coefficients in products and to approximate

This booklet covers SL 1.6, 1.9, which is common to SL and HL. HL students extend this topic in booklets 1.10, 1.15.

Guiding questions

What makes a mathematical argument a proof? How can large powers of a binomial be expanded efficiently, and why do Pascal's triangle and nCr give the same numbers?

How this topic is examined

Proof is assessed through 'show that' and 'prove that' questions on both papers; clear communication earns marks. The binomial theorem appears very frequently on Paper 1, usually asking for a specific term, a coefficient, or an unknown constant given a coefficient.

In a proof, start from one side and reach the other, writing each step on a new line, define every variable with its set (n ∈ ℤ), and finish with a concluding statement.

Command term	What the examiner wants
Write down	an answer with little or no working; it should be obtainable by inspection
Find / Calculate / Determine	obtain the answer showing relevant working
Solve	find the values of the unknowns, using algebra or technology as allowed
Show that	obtain the given result; every step must be shown and the result must not be assumed
Hence / Hence or otherwise	use the previous result (or another valid method)
Sketch	a diagram showing the general shape and key features, labelled
Prove	a formal, rigorous argument from accepted facts
Justify / Explain	give valid reasons or evidence

How to use these notes

Each section teaches one part of the syllabus. You'll see these boxes throughout; each has one job:

Box	What it's for
Think about it	a question to get you thinking before a section
Why it works	a derivation or proof of a key result, so you understand where formulas come from
Key point	a result or idea you must not forget
Common mistake	an error examiners see every year, and how to avoid it
GDC tip	how to use your graphic display calculator efficiently on Paper 2
In the real world	where the mathematics is used outside the classroom
Worked example	a full solution with IB-style marks (M1 method, A1 answer, R1 reasoning, AG answer given); examples are graded basic, standard and exam level
Practice exercise	graded questions for each section; full answers are at the end of the booklet
Quick check	short questions to check the key ideas

1 What is a proof?

Showing that something is always true.

Think about it

The numbers 3, 5, 7, 11 and 13 are all prime. Does checking many odd numbers prove that every odd number greater than 1 is prime?

In everyday life we often accept a claim after seeing many examples. In mathematics this is not enough: a proof is a logical argument that shows a statement is true in every possible case, starting from definitions and results already known to be true.

Checking examples can suggest a pattern (this is called a conjecture), but cannot prove it, because there are infinitely many cases. However, a single counterexample is enough to show a general statement is false: 9 is odd and not prime, so the statement in the box above is false.

Famous conjectures show why proof matters. The expression n2 + n + 41 gives primes for n = 0, 1, 2, ..., 39, but fails at n = 40 (402 + 40 + 41 = 1681 = 412). A pattern that holds for forty cases still was not true in general.

Key point

Examples can suggest a result; only a proof establishes it. One counterexample is enough to disprove a general claim.

2 Notation and the language of proof

Symbols you must read and write correctly.

Symbol	Meaning	Example
⇒	implies	x = 2 ⇒ x2 = 4
⇔	if and only if (implies in both directions)	x + 3 = 5 ⇔ x = 2
≡	is identically equal to (true for all values)	(x + 1)2 ≡ x2 + 2x + 1
∀	for all	∀x ∈ ℝ, x2 ≥ 0
∈	is an element of	3 ∈ ℤ
ℤ, ℕ, ℚ, ℝ	integers, natural numbers, rationals, reals	√2 ∈ ℝ but √2 ∉ ℚ

Note that x2 = 4 does not imply x = 2 (x could be −2), so the arrow goes only one way in that example. Using ⇔ when only ⇒ is valid is a common logical error.

Useful general forms (with n, m ∈ ℤ): an even number 2n; an odd number 2n + 1; consecutive integers n, n + 1, n + 2; consecutive even numbers 2n, 2n + 2; a multiple of k kn; a number that leaves remainder r when divided by k: kn + r. To refer to two unrelated odd numbers, use two different letters: 2m + 1 and 2n + 1.

Practice exercise 1

1. Write a general expression for three consecutive odd numbers.

2. Is it true that x2 = 9 ⇔ x = 3? Explain.

3. Give a counterexample to 'all prime numbers are odd'.

4. Write a general number that leaves remainder 2 when divided by 5.

3 Writing deductive proofs

Clear structure, one step per line.

A deductive proof moves step by step from what is known to what is to be shown. A good proof: (1) defines the variables and their sets; (2) writes the given information algebraically; (3) manipulates it with valid algebra, one step per line; (4) interprets the result; (5) ends with a clear concluding statement linked back to the question.

WORKED EXAMPLE 1 Sum of consecutive integers (basic)

Prove that the sum of any three consecutive integers is a multiple of 3.

Solution

Let the integers be n, n + 1, n + 2, where n ∈ ℤM1

Sum = 3n + 3 = 3(n + 1)A1

Since n + 1 ∈ ℤ, the sum is a multiple of 3R1

WORKED EXAMPLE 2 Squares of odd numbers (standard)

Prove that the square of any odd number is odd.

Solution

Let the odd number be 2n + 1, n ∈ ℤM1

(2n + 1)2 = 4n2 + 4n + 1 = 2(2n2 + 2n) + 1A1

2n2 + 2n ∈ ℤ, so the square has the form 2k + 1 and is oddR1

WORKED EXAMPLE 3 Difference of squares of consecutive odd numbers (exam level)

Prove that the difference between the squares of two consecutive odd numbers is a multiple of 8.

Solution

Let the numbers be 2n + 1 and 2n + 3, n ∈ ℤM1

(2n + 3)2 − (2n + 1)2 = (4n2 + 12n + 9) − (4n2 + 4n + 1)M1

= 8n + 8 = 8(n + 1)A1

n + 1 ∈ ℤ, so the difference is a multiple of 8R1

WORKED EXAMPLE 4 Using a counterexample (standard)

Disprove: 'For all real numbers x, x3 ≥ x.'

Solution

Take x = ½: x3 = 1/8 < ½A1

So the statement is falseR1

Common mistake

Starting from the result to be proved and working backwards to something true. This assumes what you are trying to prove; begin from the given facts instead.

Practice exercise 2

1. Prove that the sum of two odd numbers is even.

2. Prove that the product of two consecutive integers is even.

3. Prove that the sum of four consecutive integers is never a multiple of 4.

4. Disprove: 'if n is prime, then 2n + 1 is prime'.

5. Prove that (n + 1)2 − (n − 1)2 is a multiple of 4 for all n ∈ ℤ.

4 Proving identities

Work on one side until it becomes the other.

An identity is true for all values of the variable, indicated by ≡. To prove an identity, start with one side (usually the more complicated one, often the left-hand side, LHS), manipulate it, and show that it equals the other side (RHS). Do not move terms across the ≡ sign as if solving an equation, and do not work on both sides at once.

An equation, by contrast, is true only for particular values: x2 = 4 is an equation; (x + 2)2 ≡ x2 + 4x + 4 is an identity.

WORKED EXAMPLE 5 An algebraic identity (basic)

Prove that (n + 3)2 − (n − 3)2 ≡ 12n.

Solution

LHS = (n2 + 6n + 9) − (n2 − 6n + 9)M1

= 12n = RHSA1

WORKED EXAMPLE 6 A fraction identity (standard)

Show that 1/(x − 1) − 1/(x + 1) ≡ 2/(x2 − 1).

Solution

LHS = ((x + 1) − (x − 1)) ÷ ((x − 1)(x + 1))M1

= 2 ÷ (x2 − 1) = RHSA1

WORKED EXAMPLE 7 Finding constants in an identity (exam level)

Find a, b and c such that 2x2 + 12x + 7 ≡ a(x + b)2 + c.

Solution

Expand: a(x + b)2 + c = ax2 + 2abx + ab2 + cM1

Compare coefficients: a = 2; 2ab = 12 so b = 3; ab2 + c = 7 so c = −11A1 A1

a = 2, b = 3, c = −11A1

Practice exercise 3

1. Prove that (a + b)2 − (a − b)2 ≡ 4ab.

2. Show that x/(x + 2) + 2/(x − 2) ≡ (x2 + 4)/(x2 − 4).

3. Find p and q such that x2 − 8x + 20 ≡ (x − p)2 + q, and hence show x2 − 8x + 20 > 0 for all x.

5 Pascal's triangle and binomial expansions

Patterns in the coefficients.

A binomial is an expression with two terms, such as a + b or 2x − 3. Expanding powers of (a + b) by repeated multiplication reveals a pattern: (a + b)2 = a2 + 2ab + b2; (a + b)3 = a3 + 3a2b + 3ab2 + b3; (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4.

The coefficients form Pascal's triangle, in which every row starts and ends with 1 and each inner number is the sum of the two numbers above it. This happens because each term of (a + b)n+1 = (a + b)(a + b)n comes from two terms of the row above.

In the expansion of (a + b)n: there are n + 1 terms; the powers of a decrease from n to 0 while the powers of b increase from 0 to n; the powers in each term add to n; and the coefficients are symmetric.

n	Coefficients in (a + b)n	Sum
0	1	1
1	1 1	2
2	1 2 1	4
3	1 3 3 1	8
4	1 4 6 4 1	16
5	1 5 10 10 5 1	32
6	1 6 15 20 15 6 1	64

Notice that each row sums to 2n: substituting a = b = 1 into (a + b)n gives 2n.

WORKED EXAMPLE 8 Using Pascal's triangle (basic)

Expand (x + 3)4.

Solution

Coefficients 1, 4, 6, 4, 1M1

x4 + 4x3(3) + 6x2(9) + 4x(27) + 81M1

= x4 + 12x3 + 54x2 + 108x + 81A1

WORKED EXAMPLE 9 A negative term (standard)

Expand (2x − 1)4.

Solution

Coefficients 1, 4, 6, 4, 1 with a = 2x, b = −1M1

(2x)4 + 4(2x)3(−1) + 6(2x)2(−1)2 + 4(2x)(−1)3 + (−1)4M1

= 16x4 − 32x3 + 24x2 − 8x + 1A1

With a negative second term, the signs alternate.

Practice exercise 4

1. Write down row 7 of Pascal's triangle.

2. Expand (1 + x)5.

3. Expand (3 − x)3.

4. Expand (x + 2/x)4 and simplify each term.

6 Factorials and binomial coefficients

Counting choices.

The factorial of a non-negative integer is n! = n × (n − 1) × ... × 2 × 1, with 0! = 1 by definition. Factorials grow very fast: 10! = 3 628 800.

The binomial coefficient nCr (read 'n choose r') counts the number of ways of choosing r objects from n different objects, ignoring order. It equals the entry in position r (counting from r = 0) of row n of Pascal's triangle:

Why do choices give binomial coefficients? Expanding (a + b)n means choosing either a or b from each of the n brackets. The term an−rbr arises each time b is chosen from exactly r of the brackets, and there are nCr ways to make that choice.

Properties: nC0 = nCn = 1; nC1 = n; nCr = nC(n − r) (symmetry); and nCr + nC(r + 1) = (n + 1)C(r + 1) (Pascal's rule).

WORKED EXAMPLE 10 Evaluating without a calculator (basic)

Find 8C3.

Solution

8! ÷ (3! 5!) = (8 × 7 × 6) ÷ (3 × 2 × 1)M1

= 56A1

WORKED EXAMPLE 11 Solving with binomial coefficients (exam level)

Solve nC2 = 45.

Solution

n(n − 1)/2 = 45, so n2 − n − 90 = 0M1

(n − 10)(n + 9) = 0A1

n ∈ ℕ, so n = 10A1

GDC tip

Use the nCr function (in the probability menu) for binomial coefficients. On Paper 1, cancel factorials by hand: nCr = n(n − 1)...(n − r + 1)/r!.

Practice exercise 5

1. Evaluate 6C2 and 10C7.

2. Simplify (n + 1)!/(n − 1)!.

3. Solve nC2 = 28.

4. Show that 5C2 + 5C3 = 6C3.

7 The binomial theorem

A formula for every expansion.

For n ∈ ℕ, the binomial theorem gives the full expansion:

The general term, called the (r + 1)th term, is:

WORKED EXAMPLE 12 Using the theorem (standard)

Find the first three terms, in ascending powers of x, of (2 + 3x)6.

Solution

26 + 6C1 × 25(3x) + 6C2 × 24(3x)2M1

= 64 + 6 × 32 × 3x + 15 × 16 × 9x2A1

= 64 + 576x + 2160x2A1

Common mistake

Forgetting to raise the coefficient of x to the power: (3x)2 = 9x2, not 3x2.

Practice exercise 6

1. Find the first three terms of (1 − 2x)8.

2. Find the first three terms of (3 + x/2)5 in ascending powers of x.

3. Write down the term in x4 in (1 + x)9.

8 Finding a specific term or coefficient

Write the general term, then solve for r.

To find the term in a particular power of x: write the general term; collect all powers of x into a single power xf(r); set f(r) equal to the required power and solve for r; then evaluate. The constant term (term independent of x) is found by setting the power of x equal to 0.

WORKED EXAMPLE 13 A specific coefficient (standard)

Find the coefficient of x3 in the expansion of (3 − 2x)7.

Solution

General term: 7Cr 37−r(−2x)r; need r = 3M1

7C3 × 34 × (−2)3 = 35 × 81 × (−8)A1

= −22 680A1

WORKED EXAMPLE 14 Term independent of x (exam level)

Find the constant term in the expansion of (x2 + 2/x)6.

Solution

General term: 6Cr (x2)6−r(2/x)r = 6Cr 2r x12−3rM1

12 − 3r = 0, so r = 4A1

6C4 × 24 = 15 × 16 = 240A1

WORKED EXAMPLE 15 Finding an unknown constant (exam level)

The coefficient of x2 in (1 + kx)5 is 40. Find the possible values of k.

Solution

5C2 k2 = 40M1

10k2 = 40, k2 = 4A1

k = ±2A1

Practice exercise 7

1. Find the coefficient of x5 in (x − 2)8.

2. Find the constant term in (2x − 1/x)6.

3. Find the term in x2 in (x + 3/x)6.

4. The coefficient of x3 in (2 + ax)5 is 1080. Find a.

5. Find n if the coefficient of x2 in (1 + 3x)n is 252.

9 Products of expansions and approximations

Combining expansions; using the first few terms.

To find a coefficient in a product such as (1 + 2x)(1 − x)6, list the terms of each factor that can multiply to give the required power, then add their products.

When x is small, higher powers of x are tiny, so the first few terms of a binomial expansion give a good approximation: 1.026 = (1 + 0.02)6 ≈ 1 + 6(0.02) + 15(0.02)2 = 1.126 (actual 1.126 16...).

WORKED EXAMPLE 16 Coefficient in a product (exam level)

Find the coefficient of x2 in (1 + 2x)(1 − x)6.

Solution

(1 − x)6 = 1 − 6x + 15x2 − ...A1

x2 terms: 1 × 15x2 + 2x × (−6x)M1

= 15 − 12 = 3A1

WORKED EXAMPLE 17 Approximation (standard)

Use the first three terms of (1 − x/2)8 to estimate 0.998.

Solution

(1 − x/2)8 ≈ 1 − 4x + 7x2M1

0.99 = 1 − x/2 gives x = 0.02M1

≈ 1 − 0.08 + 0.0028 = 0.9228A1

Practice exercise 8

1. Find the coefficient of x3 in (2 − x)(1 + x)5.

2. Use (1 + x)10 to estimate 1.00310 to 6 d.p.

3. Find the coefficient of x in (x + 1/x)3(x + 2).

10 Direct proofs with integers

Even, odd and consecutive numbers.

To prove statements about integers, represent them algebraically: an even number is 2n, an odd number 2n + 1, consecutive integers n and n + 1, and a multiple of 3 is 3n (n ∈ ℤ). Then manipulate the expression to show the required form.

WORKED EXAMPLE 18 Sum of consecutive odd numbers (standard)

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

Solution

(2n + 1) + (2n + 3) = 4n + 4M1

= 4(n + 1), a multiple of 4A1 AG

WORKED EXAMPLE 19 Difference of squares (exam level)

Prove that the difference between the squares of two consecutive integers is always odd.

Solution

(n + 1)2 − n2 = 2n + 1M1 A1

2n + 1 is odd for all integers nR1 AG

Practice exercise 9

1. Prove that the product of two odd numbers is odd.

2. Prove that the sum of three consecutive integers is divisible by 3.

3. Prove that n2 + n is always even.

11 Proving algebraic identities

Left-hand side to right-hand side.

An identity (≡) holds for all values of the variable. Prove it by starting with one side (usually the more complicated) and transforming it into the other, step by step. Do not start by assuming the result, and do not work on both sides at once unless each step is reversible.

WORKED EXAMPLE 20 Expanding (standard)

Prove that (a + b)2 − (a − b)2 ≡ 4ab.

Solution

LHS = a2 + 2ab + b2 − a2 + 2ab − b2M1

= 4ab = RHSA1 AG

WORKED EXAMPLE 21 Fractions (exam level)

Prove that 1/n − 1/(n + 1) ≡ 1/(n(n + 1)).

Solution

LHS = ((n + 1) − n)/(n(n + 1))M1

= 1/(n(n + 1)) = RHSA1 AG

Practice exercise 10

1. Prove that (x + 3)2 − (x − 3)2 ≡ 12x.

2. Prove that n3 − n ≡ (n − 1)n(n + 1), and hence that n3 − n is always divisible by 6.

12 Proofs involving inequalities

Using squares.

Many inequalities follow from the fact that a square is never negative. For example, completing the square shows that x2 − 6x + 10 = (x − 3)2 + 1 > 0 for all x.

WORKED EXAMPLE 22 Completing the square (standard)

Prove that x2 + 4x + 7 > 0 for all real x.

Solution

x2 + 4x + 7 = (x + 2)2 + 3M1 A1

(x + 2)2 ≥ 0, so the expression ≥ 3 > 0R1 AG

WORKED EXAMPLE 23 Arithmetic-geometric mean (exam level)

Prove that for positive a and b, (a + b)/2 ≥ √(ab).

Solution

(√a − √b)2 ≥ 0M1

a − 2√(ab) + b ≥ 0A1

so (a + b)/2 ≥ √(ab)AG

Practice exercise 11

1. Prove that a2 + b2 ≥ 2ab for all real a, b.

2. Prove that 2x2 − 4x + 5 > 0 for all x.

13 Errors in proof

What does not count as a proof.

Checking a few examples does not prove a general statement (but one counterexample disproves it). Starting from the result and deriving a true statement is not valid unless every step is reversible. Dividing by an expression that could be zero is a common hidden error.

WORKED EXAMPLE 24 Spot the error (standard)

A student 'proves' 1 = 2: let a = b; then a2 = ab, so a2 − b2 = ab − b2, (a + b)(a − b) = b(a − b), a + b = b, 2b = b, 2 = 1. Find the error.

Solution

Dividing by a − b, which is 0R1

The step from (a + b)(a − b) = b(a − b) to a + b = b is invalidR1

Practice exercise 12

1. Give a counterexample to 'n2 + n + 41 is prime for every positive integer n'.

2. Why does checking n = 1, 2, ..., 100 not prove a statement for all n?

14 Patterns in Pascal's triangle

Symmetry, sums and diagonals.

Each row of Pascal's triangle is symmetric (nCr = nC(n − r)), each entry is the sum of the two above (nCr + nC(r + 1) = (n + 1)C(r + 1)), and the entries in row n sum to 2n. The diagonals contain the natural numbers, the triangular numbers and the tetrahedral numbers.

WORKED EXAMPLE 25 Row sum (standard)

Show that nC0 + nC1 + ... + nCn = 2n.

Solution

Substitute a = b = 1 in (a + b)n = Σ nCr an−rbrM1

2n = Σ nCrAG

WORKED EXAMPLE 26 Alternating sum (exam level)

Find nC0 − nC1 + nC2 − ... + (−1)nnCn for n ≥ 1.

Solution

Substitute a = 1, b = −1M1

(1 − 1)n = 0A1

Practice exercise 13

1. Evaluate 6C0 + 6C1 + ... + 6C6.

2. Verify Pascal's rule for 7C3 + 7C4.

3. Find the sum of the even-position entries of row 8 (8C0 + 8C2 + ... + 8C8).

15 Expansions with fractions and negative terms

Careful with signs and powers.

When terms such as 2/x or −x/3 appear, raise the whole term (including its sign and coefficient) to the power. Write the general term and simplify the powers of x before substituting.

WORKED EXAMPLE 27 Fractional term (standard)

Find the first four terms of (2 − x/4)6.

Solution

64 + 6(32)(−x/4) + 15(16)(x2/16) + 20(8)(−x3/64)M1

= 64 − 48x + 15x2 − 2.5x3A1 A1

Practice exercise 14

1. Expand (1 − 2x)5.

2. Find the first three terms of (3 + x/3)4.

16 Finding coefficients with x in both terms

Solve for r.

For (axp + b/xq)n, the general term has power of x equal to p(n − r) − qr. Set this equal to the required power and solve for r; if r is not a whole number between 0 and n, no such term exists.

WORKED EXAMPLE 28 A coefficient with x in both terms (exam level)

Find the coefficient of x6 in (x2 + 3/x)9.

Solution

Power: 2(9 − r) − r = 18 − 3r = 6, r = 4M1 A1

9C4 × 34 = 126 × 81 = 10 206A1

WORKED EXAMPLE 29 No such term (standard)

Show that (x + 1/x2)7 has no constant term.

Solution

Power 7 − 3r = 0 gives r = 7/3M1

Not an integer: no constant termR1

Practice exercise 15

1. Find the constant term in (2x − 1/x2)6.

2. Find the coefficient of x5 in (x2 − 2/x)7.

17 Products of two expansions

Combine contributions.

To find a coefficient in a product such as (2 + x)(1 − x)8, expand each factor only as far as needed and add the contributions that give the required power.

WORKED EXAMPLE 30 Product (exam level)

Find the coefficient of x3 in (2 + x)(1 − x)8.

Solution

(1 − x)8 = 1 − 8x + 28x2 − 56x3 + ...A1

2(−56) + 1(28)M1

= −84A1

Practice exercise 16

1. Find the coefficient of x2 in (1 + 3x)(2 − x)5.

2. Find the coefficient of x in (x + 1/x)(1 + x)4.

18 Approximations using the binomial theorem

Small x.

When x is small, the first few terms of (1 + x)n give a good approximation. Choose x so that the bracket matches the number to be estimated.

WORKED EXAMPLE 31 Estimate (standard)

Use the expansion of (1 + x)8 to estimate 1.0038 to 6 decimal places.

Solution

1 + 8(0.003) + 28(0.003)2 + 56(0.003)3M1

= 1 + 0.024 + 0.000252 + 0.0000015 = 1.024254A1

Practice exercise 17

1. Estimate 0.985 using three terms.

2. Estimate 2.014 using (2 + x)4.

19 Binomial coefficients in counting and probability

Same numbers, new contexts.

nCr counts the ways to choose r items from n. In probability, the chance of exactly r successes in n independent trials with probability p is nCr pr(1 − p)n−r, which are the terms of (q + p)n.

WORKED EXAMPLE 32 Coins (standard)

A fair coin is tossed 8 times. Find P(exactly 5 heads).

Solution

8C5 (0.5)8M1

= 56/256 = 0.219A1

Practice exercise 18

1. How many ways can a committee of 4 be chosen from 10 people?

2. A die is rolled 4 times. Find P(exactly one six).

20 Mixed review and exam practice

Bringing the ideas together.

WORKED EXAMPLE 33 Paper 1 question (exam level)

The coefficient of x2 in (1 + ax)n is 45 and the coefficient of x is 10. Find a and n.

Solution

na = 10; n(n − 1)a2/2 = 45M1

(n − 1)a = 9, so a = 1A1

a = 1, n = 10A1

WORKED EXAMPLE 34 Proof question (exam level)

Prove that the square of any odd number is one more than a multiple of 8.

Solution

(2n + 1)2 = 4n2 + 4n + 1 = 4n(n + 1) + 1M1 A1

n(n + 1) is even, so 4n(n + 1) is a multiple of 8R1 AG

Practice exercise 19

1. Find the term in x4 in (3x − 2)6.

2. Prove that the sum of any five consecutive integers is divisible by 5.

21 Exam-style questions with markscheme

Attempt each question under timed conditions before reading the markscheme.

Question 1 (Paper 1 style) (about 15 minutes)

(a) Prove that the difference between the squares of any two consecutive integers is odd. [3]

(b) Find the coefficient of x4 in the expansion of (2x − 3)6. [3]

Markscheme

Part	Answer	Marks
(a)	(n + 1)2 − n2	M1
	= 2n + 1	A1
	2n + 1 is odd for n ∈ ℤ	R1
(b)	6C2 (2x)4(−3)2	M1
	15 × 16 × 9	A1
	2160	A1
(c)	5C2 k2 = 40	M1
	k2 = 4	A1
	k = ±2	A1

Examiner's comments. In (b), the most common error was choosing r = 4 instead of r = 2: the power of x comes from (2x)6−r.

Question 2 (Paper 1 style) (about 12 minutes)

Consider the expansion of (x + a/x2)9, a > 0.

(a) Write down the general term. [2]

(b) The constant term is 5376. Find a. [4]

Markscheme

Part	Answer	Marks
(a)	9Cr x9−r(a/x2)r	A1
	= 9Cr ar x9−3r	A1
(b)	9 − 3r = 0, r = 3	M1 A1
	84a3 = 5376	M1
	a = 4	A1

Examiner's comments. Collecting powers of x into a single exponent is the key step.

22 Common misconceptions and links

Students often think…	Actually…
checking examples proves a statement	a proof must cover every case
the rth term uses nCr	the (r + 1)th term uses nCr
(a − b)n has all positive terms	signs alternate
⇒ and ⇔ mean the same	⇔ requires both directions

How 1.6 connects to the rest of the course

Topic	Connection
1.10 Counting principles (HL)	nCr, permutations, extended binomial
1.15 Further proof (HL)	induction and contradiction
4.7 Binomial distribution	nCr in probability
2.12 Polynomials (HL)	expansions

23 Check your understanding

Section A: multiple choice

1. 5C2 =

A. 10 B. 20 C. 5 D. 25

2. The number of terms in (x + y)7 is

A. 7 B. 6 C. 8 D. 14

3. A counterexample shows a statement is

A. true B. false C. an identity D. proven for all cases

4. The constant term of (x + 1/x)4 is

A. 4 B. 1 C. 0 D. 6

5. 0! =

A. 0 B. 1 C. undefined D. ∞

6. ≡ means

A. identically equal for all values B. approximately equal C. implies D. not equal

Section B: structured

7. Prove that the product of two odd numbers is odd. [3]

8. Expand (1 + 2x)5 fully. [3]

9. Find the term in x5 in (x − 2)8. [2]

Answers

1. A 2. C 3. B 4. D 5. B 6. A

7. (2m + 1)(2n + 1) = 2(2mn + m + n) + 1: odd.

8. 1 + 10x + 40x2 + 80x3 + 80x4 + 32x5.

9. 8C3 x5(−2)3 = −448x5.

24 Summary and topic map

Idea	Remember
Proof	general argument; counterexample disproves
Notation	⇒, ⇔, ≡, ∀, ∈, ℤ, ℝ
Identities	LHS to RHS; compare coefficients
Pascal's triangle	each entry is the sum of the two above
nCr	n!/(r!(n − r)!)
General term	nCr an−rbr is term r + 1
Products	add contributions from each pair of terms

Before the exam, make sure you…

•define variables with their sets
•end proofs with a conclusion
•include signs and coefficients in powers
•solve for r from the power of x

Proof and the Binomial Theorem on one page

Cover this page with a sheet of paper and try to rebuild it from memory. Whatever you can't recall is what to revise next.

Figure 1. Topic map for Proof and the Binomial Theorem.

25 Answers to practice exercises

Check your working against these answers. Full methods are expected in the exam.

Practice exercise 1

1. 2n + 1, 2n + 3, 2n + 5

2. No: x2 = 9 ⇒ x = ±3, so only x = 3 ⇒ x2 = 9 holds

3. 2

4. 5n + 2, n ∈ ℤ

Practice exercise 2

1. (2m + 1) + (2n + 1) = 2(m + n + 1)

2. n(n + 1): one of the two is even, so the product is even

3. 4n + 6 = 4(n + 1) + 2: remainder 2 when divided by 4

4. n = 7: 2n + 1 = 15, not prime

5. = 4n

Practice exercise 3

1. expand and simplify the LHS

2. common denominator (x + 2)(x − 2): numerator x(x − 2) + 2(x + 2) = x2 + 4

3. p = 4, q = 4; (x − 4)2 ≥ 0 so the expression ≥ 4 > 0

Practice exercise 4

1. 1 7 21 35 35 21 7 1

2. 1 + 5x + 10x2 + 10x3 + 5x4 + x5

3. 27 − 27x + 9x2 − x3

4. x4 + 8x2 + 24 + 32/x2 + 16/x4

Practice exercise 5

1. 15; 120

2. n(n + 1)

3. n = 8

4. 10 + 10 = 20 = 6C3

Practice exercise 6

1. 1 − 16x + 112x2

2. 243 + 202.5x + 67.5x2

3. 126x4

Practice exercise 7

1. −448

2. −160

3. 135x2

4. a = 3

5. 9n(n − 1)/2 = 252: n = 8

Practice exercise 8

1. 2 × 10 − 10 = 10

2. 1 + 0.03 + 0.000 405 = 1.030 405 (actual 1.030 408)

3. (x3 + 3x + 3/x + 1/x3)(x + 2): only 3x × 2 gives an x term, so the coefficient is 6

Practice exercise 9

1. (2a + 1)(2b + 1) = 2(2ab + a + b) + 1

2. n + (n + 1) + (n + 2) = 3(n + 1)

3. n(n + 1) is a product of consecutive integers, one of which is even

Practice exercise 10

1. expand: 12x

2. factorize; product of three consecutive integers is divisible by 2 and 3

Practice exercise 11

1. (a − b)2 ≥ 0

2. 2(x − 1)2 + 3 > 0

Practice exercise 12

1. n = 40: 1681 = 412

2. the statement could fail for a larger n

Practice exercise 13

1. 64

2. 35 + 35 = 70 = 8C4

3. 128

Practice exercise 14

1. 1 − 10x + 40x2 − 80x3 + 80x4 − 32x5

2. 81 + 36x + 6x2

Practice exercise 15

1. 6 − 3r = 0: r = 2: 15 × 16 × 1 = 240

2. 14 − 3r = 5: r = 3: 35 × (−8) = −280

Practice exercise 16

1. (2 − x)5: 32 − 80x + 80x2: 80 + 3(−80) = −160

2. 1 × 1 (from x × 1) + (1/x)(6x2): 1 + 6 = 7

Practice exercise 17

1. 1 − 0.1 + 0.004 = 0.904

2. 16 + 0.32 + 0.0024 = 16.3224

Practice exercise 18

1. 210

2. 4 × (1/6)(5/6)3 = 0.386

Practice exercise 19

1. 15 × 81 × 4 x4 = 4860x4

2. 5n + 10 = 5(n + 2)

DP MATHEMATICS AA · TOPIC 1: NUMBER AND ALGEBRA

1.10

Counting Principles and the Extended Binomial Theorem

Full notes for HL · Syllabus AHL 1.10

Contents

1	The multiplication and addition principles
2	Factorials and arrangements
3	Permutations
4	Arrangements with identical objects
5	Combinations
6	Restrictions: together, apart and fixed positions
7	Selections with conditions
8	The extended binomial theorem
9	Validity and approximations
10	The product and addition principles
11	Permutations with restrictions
12	Combinations with restrictions
13	Arrangements with identical objects
14	Circular arrangements
15	Counting in probability
16	The binomial theorem and counting
17	Further extended binomial expansions
18	Mixed review: worked problems
19	Additional exam-style practice
20	Exam-style questions with markscheme
21	Common misconceptions and links
22	Check your understanding
23	Summary and topic map
24	Answers to practice exercises

These are full teaching notes. Read each section in order, try the Think about it question before you read on, and work through every worked example before attempting the Quick check.

Before you start

Rate yourself on each statement now, and again after you've worked through the notes. Shade R (not yet), A (getting there) or G (confident).

I can…	R	A	G
apply the multiplication and addition principles
use factorials to count arrangements of distinct objects
use nPr for ordered selections and n!/(p!q!) for identical objects
use nCr for unordered selections
solve counting problems with restrictions (together, apart, fixed positions, at least)
expand (a + b)n for negative and fractional n
state and justify the interval of validity
use extended expansions to approximate roots

This booklet covers Additional Higher Level (AHL) content (AHL 1.10). It is studied by HL students only.

Guiding questions

How can we count possibilities without listing them all? When does order matter? How can the binomial theorem be extended beyond positive whole numbers?

How this topic is examined

Counting questions appear on Papers 1 and 2, nearly always with a restriction: people who must sit together or apart, committees with conditions, arrangements of letters. The extended binomial theorem is tested on Paper 1: the first few terms, the interval of validity, and approximations.

Before counting, decide whether order matters (permutation) or not (combination). Deal with restrictions first, then count the rest. Explain your method briefly: examiners award method marks for a correct strategy.

Command term	What the examiner wants
Write down	an answer with little or no working; it should be obtainable by inspection
Find / Calculate / Determine	obtain the answer showing relevant working
Solve	find the values of the unknowns, using algebra or technology as allowed
Show that	obtain the given result; every step must be shown and the result must not be assumed
Hence / Hence or otherwise	use the previous result (or another valid method)
Sketch	a diagram showing the general shape and key features, labelled
Prove	a formal, rigorous argument from accepted facts
Justify / Explain	give valid reasons or evidence

How to use these notes

Each section teaches one part of the syllabus. You'll see these boxes throughout; each has one job:

Box	What it's for
Think about it	a question to get you thinking before a section
Why it works	a derivation or proof of a key result, so you understand where formulas come from
Key point	a result or idea you must not forget
Common mistake	an error examiners see every year, and how to avoid it
GDC tip	how to use your graphic display calculator efficiently on Paper 2
In the real world	where the mathematics is used outside the classroom
Worked example	a full solution with IB-style marks (M1 method, A1 answer, R1 reasoning, AG answer given); examples are graded basic, standard and exam level
Practice exercise	graded questions for each section; full answers are at the end of the booklet
Quick check	short questions to check the key ideas

1 The multiplication and addition principles

AND means multiply; OR means add.

Think about it

A café offers 3 starters, 5 mains and 4 desserts. How many different three-course meals are possible? How many meals are possible if you choose a starter or a dessert, but not both, with a main?

Multiplication principle: if one task can be done in m ways and a second, independent task can be done in n ways, then the two tasks together can be done in m × n ways. This extends to any number of tasks. The café meal can be chosen in 3 × 5 × 4 = 60 ways.

Addition principle: if a task can be done in m ways or in n ways, where the two sets of ways do not overlap (mutually exclusive), it can be done in m + n ways. A main with either a starter or a dessert: 5 × (3 + 4) = 35 ways.

A tree diagram or box diagram (one box per position, writing the number of choices in each) makes the multiplication principle concrete and helps with restrictions.

WORKED EXAMPLE 1 Codes (basic)

A code consists of 2 letters followed by 3 digits. How many codes are possible if (a) repetition is allowed; (b) no repetition is allowed?

Solution

(a) 26 × 26 × 10 × 10 × 10 = 676 000A1

(b) 26 × 25 × 10 × 9 × 8 = 468 000A1

WORKED EXAMPLE 2 Even numbers (standard)

How many four-digit even numbers can be made from the digits 1, 2, 3, 4, 5, 6 without repetition?

Solution

Last digit even: 3 choicesM1

Remaining three positions: 5 × 4 × 3M1

3 × 60 = 180A1

Fill the restricted position first.

WORKED EXAMPLE 3 Addition and multiplication (exam level)

How many numbers between 100 and 999 inclusive have all digits different and are divisible by 5?

Solution

Ending in 0: hundreds 9 choices, tens 8: 72M1

Ending in 5: hundreds 8 choices (not 0 or 5), tens 8: 64M1

Total = 72 + 64 = 136A1

Practice exercise 1

1. How many outfits from 4 shirts, 3 trousers and 2 pairs of shoes?

2. How many 3-digit numbers have no repeated digits?

3. How many 4-letter codes use only vowels, with repetition allowed?

4. How many odd numbers between 1000 and 9999 have all digits different?

2 Factorials and arrangements

Lining up n objects.

The number of ways of arranging n different objects in a line is n × (n − 1) × ... × 2 × 1 = n!: there are n choices for the first position, n − 1 for the second, and so on. Five books can be arranged on a shelf in 5! = 120 ways.

For circular arrangements, rotations of the same arrangement are identical, so fix one object and arrange the rest: n different objects round a circle can be arranged in (n − 1)! ways.

WORKED EXAMPLE 4 Circular arrangement (standard)

In how many ways can 6 people sit at a round table?

Solution

Fix one person; arrange the other 5M1

5! = 120A1

Practice exercise 2

1. In how many ways can 7 runners finish a race (no ties)?

2. Simplify 10!/8!.

3. In how many ways can 8 people sit at a round table if two particular people must sit together?

3 Permutations

Ordered selections.

A permutation is an arrangement in which order matters. The number of permutations of r objects chosen from n different objects is:

WORKED EXAMPLE 5 Officers (basic)

In how many ways can a president, secretary and treasurer be chosen from 12 people?

Solution

Order matters: 12P3M1

= 12 × 11 × 10 = 1320A1

WORKED EXAMPLE 6 Solving with nPr (exam level)

Solve nP2 = 56.

Solution

n(n − 1) = 56M1

n2 − n − 56 = 0, (n − 8)(n + 7) = 0A1

n = 8A1

Practice exercise 3

1. Evaluate 7P2 and 6P6.

2. How many ways can gold, silver and bronze medals be awarded among 10 athletes?

3. Show that nP3 = 3! × nC3.

4 Arrangements with identical objects

Divide by the arrangements of identical items.

If some objects are identical, swapping them does not create a new arrangement. The number of arrangements of n objects, of which p are identical of one kind, q identical of another kind, and so on, is:

WORKED EXAMPLE 7 Letters (standard)

How many arrangements are there of the letters of BANANA? How many begin with B?

Solution

6 letters: A × 3, N × 2: 6!/(3!2!) = 60M1 A1

Begin with B: arrange ANANA: 5!/(3!2!) = 10A1

Practice exercise 4

1. How many arrangements of MISSISSIPPI?

2. How many arrangements of LEVEL begin and end with L?

3. How many different 6-digit numbers can be made from 1, 1, 2, 2, 2, 3?

5 Combinations

Order does not matter.

A combination is a selection in which order does not matter. Each selection of r objects can be arranged in r! orders, so the number of combinations is the number of permutations divided by r!:

WORKED EXAMPLE 8 Committee (basic)

A committee of 4 is chosen from 10 people. How many committees are possible?

Solution

Order irrelevant: 10C4M1

= 210A1

WORKED EXAMPLE 9 Two groups (standard)

A committee of 5 is chosen from 7 men and 6 women. How many committees contain exactly 3 women?

Solution

Women: 6C3 = 20; men: 7C2 = 21M1

20 × 21 = 420A1

Key point

Ask: does swapping two chosen items give a different outcome? If yes, use permutations; if no, use combinations.

Practice exercise 5

1. How many ways can 3 books be chosen from 8?

2. How many handshakes occur if 12 people each shake hands once with everyone else?

3. How many diagonals does a decagon have?

4. A team of 6 is chosen from 9 girls and 5 boys. How many teams have 4 girls and 2 boys?

6 Restrictions: together, apart and fixed positions

Handle the restriction first.

Objects together: treat the group as a single unit; arrange the units; then multiply by the arrangements within the group.

Objects apart: either subtract 'together' from the total, or arrange the other objects first and place the restricted objects in the gaps between them.

Fixed positions: place the restricted objects first, then arrange the rest.

WORKED EXAMPLE 10 Together and apart (standard)

Seven people, including A and B, stand in a line. In how many arrangements are (a) A and B together; (b) A and B apart?

Solution

(a) Treat AB as one unit: 6! × 2! = 1440M1 A1

(b) 7! − 1440 = 5040 − 1440 = 3600A1

WORKED EXAMPLE 11 Gaps method (exam level)

Four boys and three girls stand in a line. In how many ways can this be done if no two girls stand next to each other?

Solution

Arrange the boys: 4! = 24, creating 5 gapsM1

Choose and order 3 gaps for the girls: 5P3 = 60M1

24 × 60 = 1440A1

Common mistake

Forgetting to multiply by the internal arrangements of a group (2! for AB and BA).

Practice exercise 6

1. In how many ways can the letters of MATHS be arranged if M and A must be together?

2. Six books, including 2 maths books, are arranged on a shelf. How many arrangements have the maths books at the two ends?

3. Five men and four women sit in a row. How many arrangements alternate men and women?

7 Selections with conditions

'At least', 'at most' and complements.

At least one: count the total and subtract the selections with none. At most k: add the cases 0, 1, ..., k. Specific people included or excluded: include them first, then choose the rest from those remaining.

WORKED EXAMPLE 12 At least one (standard)

A committee of 5 is chosen from 7 men and 6 women. How many committees contain at least one man?

Solution

Total 13C5 = 1287; all women: 6C5 = 6M1

1287 − 6 = 1281A1

WORKED EXAMPLE 13 More girls than boys (exam level)

A team of 6 is chosen from 8 girls and 5 boys. Find the number of teams with more girls than boys.

Solution

Cases 6G0B, 5G1B, 4G2BM1

8C6 + 8C5 × 5 + 8C4 × 5C2 = 28 + 280 + 700A1

= 1008A1

Practice exercise 7

1. From 6 maths and 4 physics books, 3 are chosen. How many selections include at least one physics book?

2. A committee of 4 is chosen from 10 people including Ali and Bea. How many committees include Ali but not Bea?

3. How many teams of 5 from 6 boys and 5 girls contain at most 2 girls?

8 The extended binomial theorem

Fractional and negative powers give infinite series.

The binomial theorem (1.6) applies to positive integer n, giving n + 1 terms. For any rational n (negative or fractional), the expansion of (1 + x)n becomes an infinite series, because the coefficients never become zero:

The coefficients are the same as nCr written in product form, which makes sense even when n is not a positive integer. For (a + bx)n, first factor out a: (a + bx)n = an(1 + bx/a)n.

WORKED EXAMPLE 14 Negative power (standard)

Find the first four terms of (1 + x)−2.

Solution

1 + (−2)x + ((−2)(−3)/2)x2 + ((−2)(−3)(−4)/6)x3M1

= 1 − 2x + 3x2 − 4x3 + ...A1

WORKED EXAMPLE 15 Fractional power (standard)

Find the first three terms of (1 − 2x)−1/2 and state the values of x for which the expansion is valid.

Solution

1 + (−½)(−2x) + [(−½)(−3/2)/2](−2x)2M1

= 1 + x + (3/2)x2 + ...A1

Valid for |2x| < 1, i.e. |x| < ½A1

WORKED EXAMPLE 16 Factoring out (exam level)

Expand (4 + x)1/2 up to the x2 term and state its validity.

Solution

= 2(1 + x/4)1/2M1

= 2[1 + x/8 − x2/128 + ...]M1

= 2 + x/4 − x2/64, valid for |x| < 4A1

Common mistake

Writing (4 + x)1/2 = 41/2(1 + x)1/2. The x must also be divided by 4: 2(1 + x/4)1/2.

Practice exercise 8

1. Find the first three terms of (1 + x)1/3.

2. Find the first three terms of (1 − 3x)−1 and state the validity.

3. Expand (2 − x)−2 up to the x2 term.

4. Find the coefficient of x3 in (1 + 2x)−1/2.

9 Validity and approximations

Small x makes the series converge quickly.

The expansion of (1 + x)n is valid only for |x| < 1 (when n is not a non-negative integer); outside this interval the series diverges. For (1 + bx)n, the condition is |bx| < 1. The closer x is to 0, the faster the terms shrink and the better a few terms approximate the value.

To approximate a root, choose x small so that the expression matches the root, then substitute into the first few terms.

WORKED EXAMPLE 17 Approximating a root (exam level)

Use the expansion of (4 + x)1/2 to estimate √4.2 to 5 decimal places.

Solution

x = 0.2: 2 + 0.05 − 0.000 625M1

= 2.049 375 (actual 2.049 390...)A1

WORKED EXAMPLE 18 Using a fraction (exam level)

By substituting x = 1/10 into the expansion of (1 − x)−1/2, estimate √10.

Solution

(1 − 1/10)−1/2 = (10/9)1/2 = √10/3M1

(1 − x)−1/2 ≈ 1 + x/2 + 3x2/8 = 1 + 0.05 + 0.00375 = 1.05375A1

√10 ≈ 3 × 1.05375 = 3.161 (actual 3.162)A1

Practice exercise 9

1. Use (1 + x)1/2 to estimate √1.04 to 4 d.p.

2. Use (1 − 2x)−1 with x = 0.01 to estimate 1/0.98.

3. Explain why (1 + 2x)−1 cannot be used to estimate 1/3 by substituting x = 1.

10 The product and addition principles

When to multiply and when to add.

Product principle: if one task can be done in m ways and a second, independent task in n ways, both can be done in mn ways. Addition principle: if a task can be done in m ways or in n ways (mutually exclusive), there are m + n ways. Many errors come from adding when you should multiply, or vice versa.

WORKED EXAMPLE 19 Codes (basic)

A code has 2 letters followed by 3 digits. How many codes are possible? How many if no repeats are allowed?

Solution

262 × 103 = 676 000A1

26 × 25 × 10 × 9 × 8 = 468 000A1

WORKED EXAMPLE 20 Either-or (standard)

A menu has 5 starters, 8 mains and 4 desserts. A customer chooses either a starter and a main, or a main and a dessert. How many choices?

Solution

40 + 32M1

= 72A1

Practice exercise 10

1. How many 4-digit numbers (no leading zero) are there?

2. How many 4-digit numbers have all digits different?

3. How many even 3-digit numbers can be formed from 1, 2, 3, 4, 5 without repetition?

11 Permutations with restrictions

Deal with restrictions first.

When some positions are restricted, fill those positions first, then arrange the rest. When objects must be together, treat them as a single block and multiply by the arrangements within the block. When objects must be apart, arrange the others and use the gaps, or subtract 'together' from the total.

WORKED EXAMPLE 21 Together (standard)

In how many ways can 6 people sit in a row if A and B sit together?

Solution

Block AB plus 4 others: 5! × 2!M1

= 240A1

WORKED EXAMPLE 22 Apart (exam level)

In how many ways can 6 people sit in a row if A and B are not adjacent?

Solution

6! − 240M1

= 480A1

Practice exercise 11

1. How many arrangements of the letters of PLANET start and end with a vowel?

2. In how many ways can 4 boys and 3 girls stand in a row if the girls are together?

3. In how many ways can 5 books be arranged if two particular books are not next to each other?

12 Combinations with restrictions

Choosing groups.

For selections with conditions, split into cases (for example, 'exactly 2 women' or 'at least 1 man') and use nCr for each part, multiplying within a case and adding between cases. 'At least' problems are often easiest by subtracting the unwanted cases from the total.

WORKED EXAMPLE 23 Committees (standard)

A committee of 5 is chosen from 6 men and 4 women. How many have exactly 2 women?

Solution

4C2 × 6C3M1

= 6 × 20 = 120A1

WORKED EXAMPLE 24 At least one (exam level)

How many of these committees have at least one woman?

Solution

Total 10C5 = 252; no women 6C5 = 6M1

252 − 6 = 246A1

Practice exercise 12

1. A team of 4 is chosen from 7 girls and 5 boys. How many teams have more girls than boys?

2. How many ways can 3 cards be chosen from a standard pack so that they are all the same suit?

13 Arrangements with identical objects

Dividing out repeats.

If n objects include p identical of one kind and q of another, the number of distinct arrangements is n!/(p! q!). This also counts paths on a grid and binary strings with a fixed number of 1s.

WORKED EXAMPLE 25 Letters (standard)

How many distinct arrangements are there of the letters of MISSISSIPPI?

Solution

11!/(4! 4! 2!)M1

= 34 650A1

Practice exercise 13

1. How many arrangements of BANANA?

2. How many 8-digit binary strings contain exactly three 1s?

14 Circular arrangements

Fixing one position.

Around a circle, rotations of the same arrangement are identical, so n objects can be arranged in (n − 1)! ways. If clockwise and anticlockwise are also the same (a necklace that can be turned over), divide by 2.

WORKED EXAMPLE 26 Round table (standard)

In how many ways can 7 people sit at a round table if two particular people must sit together?

Solution

Block of 2 + 5 others = 6 units: (6 − 1)! × 2M1

= 240A1

Practice exercise 14

1. How many ways can 8 people sit at a round table?

2. How many different necklaces can be made with 6 different beads?

15 Counting in probability

Equally likely outcomes.

When outcomes are equally likely, P(event) = (number of favourable outcomes)/(total number of outcomes), and both numbers can be found by counting with permutations or combinations.

WORKED EXAMPLE 27 Cards (exam level)

Five cards are dealt from a standard pack. Find P(exactly two aces).

Solution

4C2 × 48C3/52C5M1

= 6 × 17 296/2 598 960 = 0.0399A1

WORKED EXAMPLE 28 Seating probability (standard)

Six people sit randomly in a row. Find P(A and B sit together).

Solution

240/720M1

= 1/3A1

Practice exercise 15

1. A committee of 3 is chosen at random from 5 men and 4 women. Find P(all women).

2. Find P(a 4-digit PIN has all different digits).

16 The binomial theorem and counting

Why nCr appears.

In expanding (a + b)n, the term an−rbr arises once for each way of choosing which r of the n brackets supply b, so its coefficient is nCr. This counting argument proves the binomial theorem for positive integer n.

WORKED EXAMPLE 29 Coefficient by counting (standard)

Find the coefficient of a2b3c in (a + b + c)6.

Solution

Choose positions: 6!/(2! 3! 1!)M1

= 60A1

Practice exercise 16

1. Find the coefficient of x2y2z2 in (x + y + z)6.

2. Explain why (1 + x)n has coefficient of xr equal to nCr.

17 Further extended binomial expansions

Two-term brackets and validity.

For (a + bx)n with n negative or fractional, take out an: an(1 + bx/a)n, valid for |bx/a| < 1. Products and quotients of such expansions are found by multiplying series and collecting terms.

WORKED EXAMPLE 30 Quotient (exam level)

Expand (1 + x)/(1 − 2x) up to x3 and state the validity.

Solution

(1 − 2x)−1 = 1 + 2x + 4x2 + 8x3 + ...A1

(1 + x)(1 + 2x + 4x2 + 8x3) = 1 + 3x + 6x2 + 12x3M1 A1

Valid for |x| < 1/2A1

Practice exercise 17

1. Expand (2 + x)−2 up to x2.

2. Expand √(1 + 4x) up to x3 and state when it is valid.

18 Mixed review: worked problems

Bringing the ideas together.

WORKED EXAMPLE 31 Mixed problem (exam level)

The letters of SEQUENCE are arranged randomly. Find the probability that the three Es are together.

Solution

Total 8!/3! = 6720A1

Block EEE + 5 letters: 6! = 720M1

P = 720/6720 = 3/28A1

WORKED EXAMPLE 32 Selection with conditions (exam level)

From 8 students, 3 are chosen for a team, one of whom is captain. How many ways?

Solution

8C3 × 3M1

= 168A1

Practice exercise 18

1. How many arrangements are there of the letters of ALGEBRA?

2. How many ways can 10 people be split into two groups of 5?

19 Additional exam-style practice

Paper 1 and Paper 2 questions.

WORKED EXAMPLE 33 Paper 1 question (exam level)

(a) Find the number of ways 4 boys and 4 girls can sit in a row if boys and girls alternate. (b) Find the number of ways if they sit round a table and alternate.

Solution

(a) 2 × 4! × 4! = 1152M1 A1

(b) Fix one boy: 3! × 4! = 144M1 A1

Practice exercise 19

1. Find the number of ways to choose a president, secretary and treasurer from 12 people.

2. Find P(a random arrangement of 1, 2, 3, 4, 5 has 1 before 2).

20 Exam-style questions with markscheme

Attempt each question under timed conditions before reading the markscheme.

Question 1 (Paper 1 style) (about 15 minutes)

(a) How many different arrangements of the letters of PARALLEL are there? [2]

(b) How many of these begin and end with L? [2]

Markscheme

Part	Answer	Marks
(a)	8!/(3! 2!)	M1
	3360	A1
(b)	L _ _ _ _ _ _ L: arrange P, A, R, A, L, E: 6!/2!	M1
	360	A1
(c)	6G0B + 5G1B + 4G2B	M1
	28 + 280 + 700	A1
	1008	A1

Examiner's comments. In (a), both repeated letters (L three times, A twice) must be accounted for.

Question 2 (Paper 1 style) (about 12 minutes)

(a) Expand (1 + 3x)−1/3 up to the term in x2. [3]

(b) State the interval of validity. [1]

Markscheme

Part	Answer	Marks
(a)	1 + (−1/3)(3x) + ((−1/3)(−4/3)/2)(3x)2	M1
	1 − x + 2x2	A2
(b)	\|x\| < 1/3	A1
(c)	2 × 2x2 + (−x)(−x)	M1
	4 + 1	A1
	5	A1

Examiner's comments. In (c), both contributions to x2 must be found.

21 Common misconceptions and links

Students often think…	Actually…
using nCr when order matters	use nPr for arrangements
extended expansions are valid for all x	only for \|x\| < 1 after factoring
(a + bx)n = a(1 + bx)n	factor out an
n people round a table: n! ways	(n − 1)!

How 1.10 connects to the rest of the course

Topic	Connection
1.6 Binomial theorem	positive integer n
4.5 Probability	counting outcomes
4.7 Binomial distribution	nCr
5.19 Maclaurin series	series expansions

22 Check your understanding

Section A: multiple choice

1. The number of arrangements of 5 different books is

A. 120 B. 25 C. 5 D. 60

2. 10C3 =

A. 720 B. 30 C. 120 D. 1000

3. 6 people round a table can sit in

A. 720 ways B. 120 ways C. 36 ways D. 6 ways

4. (1 + x)−1 = 1 − x + x2 − ... is valid for

A. all x B. x > 0 C. |x| < 2 D. |x| < 1

5. Arrangements of AABB:

A. 24 B. 6 C. 4 D. 12

6. 8P3 =

A. 336 B. 56 C. 512 D. 24

Section B: structured

7. How many ways can 4 boys and 3 girls sit in a row if the girls sit together? [3]

8. Find the first three terms of (2 − x)−2. [3]

9. Explain the difference between permutations and combinations. [2]

Answers

1. A 2. C 3. B 4. D 5. B 6. A

7. 5! × 3! = 720.

8. 1/4 + x/4 + 3x2/16, |x| < 2.

9. Permutations: order matters; combinations: order irrelevant.

23 Summary and topic map

Idea	Remember
Multiplication principle	AND: multiply
Addition principle	OR: add (exclusive cases)
Arrangements	n!; circular (n − 1)!; identical n!/(p!q!)
Permutations	nPr = n!/(n − r)!
Combinations	nCr = n!/(r!(n − r)!)
Restrictions	together, gaps, complement
Extended binomial	any rational n; \|x\| < 1

Before the exam, make sure you…

•decide whether order matters
•handle restrictions first
•use complements for 'at least'
•factor out an and state validity

Counting and Extended Binomial on one page

Cover this page with a sheet of paper and try to rebuild it from memory. Whatever you can't recall is what to revise next.

Figure 1. Topic map for Counting and Extended Binomial.

24 Answers to practice exercises

Check your working against these answers. Full methods are expected in the exam.

Practice exercise 1

1. 24

2. 648

3. 625

4. 2240

Practice exercise 2

1. 5040

2. 90

3. 6! × 2 = 1440

Practice exercise 3

1. 42; 720

2. 720

3. nP3 = n!/(n − 3)! = 3! × n!/(3!(n − 3)!)

Practice exercise 4

1. 34 650

2. 3!/2! = 3

3. 60

Practice exercise 5

1. 56

2. 66

3. 10C2 − 10 = 35

4. 126 × 10 = 1260

Practice exercise 6

1. 4! × 2 = 48

2. 2 × 4! = 48

3. 5! × 4! = 2880

Practice exercise 7

1. 120 − 20 = 100

2. 8C3 = 56

3. 6 + 75 + 200 = 281

Practice exercise 8

1. 1 + x/3 − x2/9

2. 1 + 3x + 9x2; |x| < 1/3

3. 1/4 + x/4 + 3x2/16; |x| < 2

4. (−½)(−3/2)(−5/2)/6 × 8 = −5/2

Practice exercise 9

1. 1 + 0.02 − 0.0002 = 1.0198

2. 1 + 0.02 + 0.0004 = 1.0204

3. |2x| = 2 > 1, so the series diverges

Practice exercise 10

1. 9000

2. 9 × 9 × 8 × 7 = 4536

3. 2 × 4 × 3 = 24

Practice exercise 11

1. 2 × 4! = 48

2. 5! × 3! = 720

3. 120 − 48 = 72

Practice exercise 12

1. 4G: 35; 3G1B: 175; total 210

2. 4 × 13C3 = 1144

Practice exercise 13

1. 60

2. 56

Practice exercise 14

1. 5040

2. 5!/2 = 60

Practice exercise 15

1. 4/84 = 1/21

2. 5040/10 000 = 0.504

Practice exercise 16

1. 90

2. choose which r brackets contribute x

Practice exercise 17

1. ¼ − x/4 + 3x2/16

2. 1 + 2x − 2x2 + 4x3; |x| < 1/4

Practice exercise 18

1. 7!/2! = 2520

2. 10C5/2 = 126

Practice exercise 19

1. 12 × 11 × 10 = 1320

2. 1/2

DP MATHEMATICS AA · TOPIC 1: NUMBER AND ALGEBRA

1.15

Proof by Induction, Contradiction and Counterexample

Full notes for HL · Syllabus AHL 1.15

Contents

1	Methods of proof
2	The principle of mathematical induction
3	Induction with sums and series
4	Induction with divisibility
5	Induction with derivatives and sequences
6	Induction with inequalities
7	Induction with complex numbers: De Moivre's theorem
8	Proof by contradiction
9	Disproof by counterexample
10	The structure of an induction proof
11	Induction for divisibility
12	Induction with inequalities
13	Induction with recurrences and derivatives
14	Proof by contradiction: more examples
15	Disproof by counterexample
16	Proofs about integers and divisibility
17	Choosing a method of proof
18	Mixed review: worked problems
19	Additional exam-style practice
20	Exam-style questions with markscheme
21	Common misconceptions and links
22	Check your understanding
23	Summary and topic map
24	Answers to practice exercises

These are full teaching notes. Read each section in order, try the Think about it question before you read on, and work through every worked example before attempting the Quick check.

Before you start

Rate yourself on each statement now, and again after you've worked through the notes. Shade R (not yet), A (getting there) or G (confident).

I can…	R	A	G
describe and apply the four stages of a proof by induction
prove results about sums, divisibility, derivatives, recurrence relations and inequalities by induction
prove De Moivre's theorem for positive integers
prove statements by contradiction, including the irrationality of √2 and the infinitude of primes
disprove a general statement with a counterexample
write proofs with clear, complete communication

This booklet covers Additional Higher Level (AHL) content (AHL 1.15). It is studied by HL students only.

Guiding questions

How can we prove that a statement is true for infinitely many cases? When is assuming the opposite a useful strategy? What makes a proof complete?

How this topic is examined

Proof by induction is a regular long question on Papers 1 and 2 (6 to 8 marks). Marks are awarded for each stage, and a final reasoning mark (R1) is given only for a complete concluding statement that refers to both the basis and the inductive step.

Write every stage: basis, assumption, inductive step (clearly showing where the assumption is used), and conclusion. Contradiction and counterexample questions are shorter but require precise logic.

Command term	What the examiner wants
Write down	an answer with little or no working; it should be obtainable by inspection
Find / Calculate / Determine	obtain the answer showing relevant working
Solve	find the values of the unknowns, using algebra or technology as allowed
Show that	obtain the given result; every step must be shown and the result must not be assumed
Hence / Hence or otherwise	use the previous result (or another valid method)
Sketch	a diagram showing the general shape and key features, labelled
Prove	a formal, rigorous argument from accepted facts
Justify / Explain	give valid reasons or evidence

How to use these notes

Each section teaches one part of the syllabus. You'll see these boxes throughout; each has one job:

Box	What it's for
Think about it	a question to get you thinking before a section
Why it works	a derivation or proof of a key result, so you understand where formulas come from
Key point	a result or idea you must not forget
Common mistake	an error examiners see every year, and how to avoid it
GDC tip	how to use your graphic display calculator efficiently on Paper 2
In the real world	where the mathematics is used outside the classroom
Worked example	a full solution with IB-style marks (M1 method, A1 answer, R1 reasoning, AG answer given); examples are graded basic, standard and exam level
Practice exercise	graded questions for each section; full answers are at the end of the booklet
Quick check	short questions to check the key ideas

1 Methods of proof

Direct, induction, contradiction, counterexample.

Think about it

Dominoes are lined up so that each one knocks over the next. If you push the first, what happens? What two facts guarantee that all of them fall?

You met direct (deductive) proof in 1.6: reasoning from known facts straight to the conclusion. This booklet adds three more methods.

Proof by induction proves a statement P(n) for every positive integer n (or every integer from some starting value). Proof by contradiction assumes the statement is false and shows this leads to an impossibility. A counterexample disproves a general statement with one specific case.

Method	Use it when...	Typical examples
Direct	you can reason straight from definitions	sums of odd numbers
Induction	the statement depends on a positive integer n	sum formulas, divisibility, nth derivatives
Contradiction	the negation gives something concrete to work with	√2 irrational; infinitely many primes
Counterexample	you want to show a general claim is false	n2 + n + 41 is always prime

2 The principle of mathematical induction

The domino principle.

Let P(n) be a statement about the positive integer n. If (1) P(1) is true, and (2) whenever P(k) is true, P(k + 1) is also true, then P(n) is true for all n ∈ ℤ+. This is like the dominoes: the first falls (basis), and each falling domino knocks over the next (inductive step), so all fall.

The four stages:

1. Basis: show P(1) is true (or P(n0) for the starting value n0). Show both sides explicitly.

2. Assumption: assume P(k) is true for some k ∈ ℤ+. Write out exactly what this means.

3. Inductive step: using the assumption, show that P(k + 1) is true. Write down the target P(k + 1) first so you know where you are heading, and make clear where the assumption is used.

4. Conclusion: 'Since P(1) is true, and P(k) true implies P(k + 1) true, by the principle of mathematical induction P(n) is true for all n ∈ ℤ+.'

Key point

The conclusion must mention both the basis and the inductive step. Without it, the final reasoning mark is lost even if the algebra is perfect.

Common mistake

Writing 'assume P(n) is true for all n'. That assumes what you are trying to prove. Assume it for one particular value k.

3 Induction with sums and series

Add the next term.

For a sum formula, the left side of P(k + 1) is the left side of P(k) plus the (k + 1)th term. Replace the sum to k with the formula from the assumption, then simplify to the formula with n = k + 1. Factorizing early (rather than expanding everything) keeps the algebra manageable.

WORKED EXAMPLE 1 Sum of squares (standard)

Prove by induction that the sum from r = 1 to n of r2 = n(n + 1)(2n + 1)/6.

Solution

n = 1: LHS = 1; RHS = 1 × 2 × 3/6 = 1. TrueA1

Assume true for n = k: sum to k = k(k + 1)(2k + 1)/6M1

Sum to k + 1 = k(k + 1)(2k + 1)/6 + (k + 1)2M1

= (k + 1)[k(2k + 1) + 6(k + 1)]/6 = (k + 1)(2k2 + 7k + 6)/6A1

= (k + 1)(k + 2)(2k + 3)/6, which is the formula with n = k + 1A1

P(1) true and P(k) ⇒ P(k + 1), so true for all n ∈ ℤ+R1

WORKED EXAMPLE 2 A geometric-type sum (exam level)

Prove that the sum from r = 1 to n of r × 2r = (n − 1)2n+1 + 2.

Solution

n = 1: LHS = 2; RHS = 0 + 2 = 2. TrueA1

Assume sum to k = (k − 1)2k+1 + 2M1

Sum to k + 1 = (k − 1)2k+1 + 2 + (k + 1)2k+1M1

= 2k × 2k+1 + 2 = k × 2k+2 + 2 = ((k + 1) − 1)2(k+1)+1 + 2A1 A1

Conclusion by inductionR1

Practice exercise 1

1. Prove by induction that the sum from r = 1 to n of (2r − 1) = n2.

2. Prove that the sum from r = 1 to n of r3 = n2(n + 1)2/4.

3. Prove that the sum from r = 1 to n of 1/(r(r + 1)) = n/(n + 1).

4. Prove that the sum from r = 1 to n of r(r + 1) = n(n + 1)(n + 2)/3.

4 Induction with divisibility

Write the (k + 1) case in terms of the k case.

To prove that f(n) is divisible by m, assume f(k) = mA for some integer A. Then rewrite f(k + 1) so that f(k) appears, substitute mA, and show the result is a multiple of m. A useful alternative is to show that f(k + 1) − f(k) (or f(k + 1) − c f(k)) is a multiple of m.

WORKED EXAMPLE 3 Divisibility (standard)

Prove by induction that 5n − 1 is divisible by 4 for all n ∈ ℤ+.

Solution

n = 1: 5 − 1 = 4, divisible by 4A1

Assume 5k − 1 = 4m, m ∈ ℤM1

5k+1 − 1 = 5 × 5k − 1 = 5(4m + 1) − 1 = 20m + 4M1 A1

= 4(5m + 1), divisible by 4A1

Conclusion by inductionR1

WORKED EXAMPLE 4 Two exponentials (exam level)

Prove that 7n − 3n is divisible by 4 for all n ∈ ℤ+.

Solution

n = 1: 4, divisible by 4A1

Assume 7k − 3k = 4mM1

7k+1 − 3k+1 = 7 × 7k − 3 × 3k = 7(4m + 3k) − 3 × 3kM1

= 28m + 4 × 3k = 4(7m + 3k)A1

Conclusion by inductionR1

Practice exercise 2

1. Prove that n3 − n is divisible by 6 for all n ∈ ℤ+.

2. Prove that 32n − 1 is divisible by 8.

3. Prove that 11n − 6 is divisible by 5.

5 Induction with derivatives and sequences

Differentiate the assumed result.

WORKED EXAMPLE 5 nth derivative (standard)

Prove that if f(x) = xex, then the nth derivative is f(n)(x) = (x + n)ex.

Solution

n = 1: f'(x) = ex + xex = (x + 1)ex. TrueA1

Assume f(k)(x) = (x + k)exM1

Differentiate: f(k+1)(x) = ex + (x + k)ex = (x + k + 1)exM1 A1

Conclusion by inductionR1

WORKED EXAMPLE 6 A recurrence relation (exam level)

A sequence has u1 = 1 and un+1 = 2un + 1. Prove that un = 2n − 1.

Solution

n = 1: 2 − 1 = 1 = u1. TrueA1

Assume uk = 2k − 1M1

uk+1 = 2(2k − 1) + 1 = 2k+1 − 1A1

Conclusion by inductionR1

Practice exercise 3

1. Prove that the nth derivative of e2x is 2ne2x.

2. Prove that the nth derivative of ln x is (−1)n−1(n − 1)!/xn.

3. u1 = 3, un+1 = 3un − 2. Prove that un = 2 × 3n−1 + 1.

6 Induction with inequalities

Use the assumption, then an extra comparison.

For inequalities, the inductive step usually needs an additional fact to bridge from what the assumption gives to what you need. Write the target first, then compare.

WORKED EXAMPLE 7 An exponential beats a square (exam level)

Prove that 2n > n2 for all integers n ≥ 5.

Solution

n = 5: 32 > 25. TrueA1

Assume 2k > k2 for some k ≥ 5M1

2k+1 = 2 × 2k > 2k2M1

2k2 − (k + 1)2 = k2 − 2k − 1 = (k − 1)2 − 2 > 0 for k ≥ 5, so 2k+1 > (k + 1)2A1

Conclusion by induction for n ≥ 5R1

Practice exercise 4

1. Prove that n! > 2n for n ≥ 4.

2. Prove that 3n > 2n + 1 for n ≥ 2.

7 Induction with complex numbers: De Moivre's theorem

A key HL proof.

WORKED EXAMPLE 8 De Moivre's theorem (exam level)

Prove (cos θ + i sin θ)n = cos nθ + i sin nθ for n ∈ ℤ+.

Solution

n = 1: trivially trueA1

Assume (cos θ + i sin θ)k = cos kθ + i sin kθM1

(cos kθ + i sin kθ)(cos θ + i sin θ) = cos kθ cos θ − sin kθ sin θ + i(sin kθ cos θ + cos kθ sin θ)M1

= cos(k + 1)θ + i sin(k + 1)θ (compound angle formulas)A1

Conclusion by inductionR1

8 Proof by contradiction

Assume the opposite and reach an impossibility.

To prove a statement by contradiction: assume the statement is false; reason logically from this assumption; reach a contradiction (something impossible, or something that contradicts the assumption); conclude that the assumption was wrong, so the statement is true.

A useful fact: if n2 is even then n is even (because if n were odd, n2 would be odd).

WORKED EXAMPLE 9 √2 is irrational (standard)

Prove that √2 is irrational.

Solution

Assume √2 = p/q, with p, q ∈ ℤ, q ≠ 0, in lowest terms (no common factor)M1

2 = p2/q2, so p2 = 2q2: p2 is even, so p is even; let p = 2mA1

4m2 = 2q2, so q2 = 2m2: q is evenA1

p and q both even contradicts lowest terms, so √2 is irrationalR1

WORKED EXAMPLE 10 Infinitely many primes (standard)

Prove there are infinitely many prime numbers.

Solution

Assume finitely many primes p1, p2, ..., pnM1

Let N = p1p2...pn + 1; dividing N by any pi leaves remainder 1A1

So N is prime or has a prime factor not in the list: a contradictionR1

WORKED EXAMPLE 11 An irrational logarithm (exam level)

Prove that log2 3 is irrational.

Solution

Assume log2 3 = p/q with p, q ∈ ℤ+M1

Then 2p/q = 3, so 2p = 3qA1

2p is even and 3q is odd: a contradictionR1

Practice exercise 5

1. Prove that √3 is irrational.

2. Prove there is no largest even number.

3. Prove that if n2 is odd then n is odd.

4. Prove that there are no integers a, b with 6a + 9b = 1.

9 Disproof by counterexample

One example is enough to show falseness.

To show that a general statement is false, give one specific counterexample, and show clearly that it fails. 'For all n, n2 − n + 41 is prime' is false: n = 41 gives 412, which is not prime. A counterexample must satisfy all the conditions of the statement and fail its conclusion.

Practice exercise 6

1. Disprove: 'if a2 = b2 then a = b'.

2. Disprove: 'the sum of two irrational numbers is irrational'.

3. Disprove: '2n + 1 is prime for all n ∈ ℤ+'.

10 The structure of an induction proof

Four essential parts.

Every induction proof needs: (1) a base case (usually n = 1); (2) an assumption that the statement holds for n = k; (3) an inductive step proving it for n = k + 1 using the assumption; (4) a conclusion stating that, since it is true for n = 1 and true for k + 1 whenever true for k, it is true for all positive integers n. Examiners award marks for each part, including the conclusion.

WORKED EXAMPLE 12 Sum of squares (standard)

Prove by induction that Σ from r = 1 to n of r2 = n(n + 1)(2n + 1)/6.

Solution

n = 1: LHS = 1, RHS = 1A1

Assume true for n = k; add (k + 1)2M1

k(k + 1)(2k + 1)/6 + (k + 1)2 = (k + 1)(2k2 + 7k + 6)/6 = (k + 1)(k + 2)(2k + 3)/6A1 A1

This is the formula for n = k + 1; conclusion by inductionR1

Practice exercise 7

1. Prove by induction that 1 + 3 + 5 + ... + (2n − 1) = n2.

2. Prove by induction that Σ r(r + 1) = n(n + 1)(n + 2)/3.

11 Induction for divisibility

Write the k + 1 case using the k case.

For divisibility proofs, write the assumption as f(k) = mA for some integer A, then express f(k + 1) in terms of f(k) plus a multiple of m.

WORKED EXAMPLE 13 Divisibility (exam level)

Prove that 7n − 1 is divisible by 6 for all positive integers n.

Solution

n = 1: 6 ✓A1

Assume 7k − 1 = 6AM1

7k+1 − 1 = 7(7k) − 1 = 7(6A + 1) − 1 = 42A + 6 = 6(7A + 1)A1 A1

Divisible by 6; conclusion by inductionR1

Practice exercise 8

1. Prove that 5n + 3 is divisible by 4.

2. Prove that n3 + 2n is divisible by 3.

12 Induction with inequalities

Inequalities need extra steps.

In the inductive step, use the assumption and then show the remaining inequality separately. The base case may start at a value other than 1.

WORKED EXAMPLE 14 Inequality (exam level)

Prove that 2n > n2 for n ≥ 5.

Solution

n = 5: 32 > 25A1

Assume 2k > k2 (k ≥ 5): 2k+1 > 2k2M1

2k2 − (k + 1)2 = k2 − 2k − 1 > 0 for k ≥ 5A1

So 2k+1 > (k + 1)2; conclusionR1

Practice exercise 9

1. Prove that 3n > 2n + 1 for n ≥ 2.

2. Prove that n! > 2n for n ≥ 4.

13 Induction with recurrences and derivatives

Sequences and repeated differentiation.

Induction proves formulas for recursively defined sequences and nth derivatives: assume the formula for k, then apply the recurrence (or differentiate once more) to obtain the k + 1 case.

WORKED EXAMPLE 15 nth derivative (exam level)

Prove that the nth derivative of xex is (x + n)ex.

Solution

n = 1: ex + xex = (x + 1)exA1

Assume f(k) = (x + k)ex; differentiate: ex + (x + k)exM1 A1

= (x + k + 1)ex; conclusionR1

Practice exercise 10

1. u1 = 2, un+1 = 3un − 2. Prove that un = 3n−1 + 1.

2. Prove that dn/dxn(e2x) = 2ne2x.

14 Proof by contradiction: more examples

Assume the opposite.

Assume the statement is false and derive a contradiction (something impossible, or contradicting an assumption). Classic examples: √2 is irrational; there are infinitely many primes; there is no largest even number.

WORKED EXAMPLE 16 Infinitely many primes (exam level)

Prove that there are infinitely many primes.

Solution

Assume finitely many: p1, ..., pnM1

N = p1p2...pn + 1 leaves remainder 1 on division by each piA1

So N has a prime factor not in the list: contradictionR1

WORKED EXAMPLE 17 Irrational sum (standard)

Prove that if a is rational and b irrational, then a + b is irrational.

Solution

Suppose a + b = c is rationalM1

Then b = c − a is rational: contradictionR1

Practice exercise 11

1. Prove that √3 is irrational.

2. Prove that there are no integers m, n with 6m + 3n = 1.

15 Disproof by counterexample

One case is enough.

To disprove a statement 'for all n', find one specific value for which it fails. Choose candidates thoughtfully: small values, zero, negatives, fractions, or values that make a factor vanish.

WORKED EXAMPLE 18 Counterexample (standard)

Disprove: for all real x, x2 > x.

Solution

x = 0.5: 0.25 < 0.5A1

Statement is falseR1

Practice exercise 12

1. Disprove: if a2 = b2 then a = b.

2. Disprove: 2n + 1 is prime for all n.

16 Proofs about integers and divisibility

Using algebra.

Many statements can be proved directly by writing integers in a convenient form: n = 3k, 3k + 1 or 3k + 2 (cases by remainder), or by factorizing an expression into consecutive integers.

WORKED EXAMPLE 19 Cases by remainder (exam level)

Prove that n2 leaves remainder 0 or 1 when divided by 3.

Solution

n = 3k: n2 = 9k2; n = 3k ± 1: n2 = 9k2 ± 6k + 1M1 A1

Remainders 0 and 1 onlyR1

Practice exercise 13

1. Prove that n5 − n is divisible by 5 for every integer n (consider n mod 5).

17 Choosing a method of proof

Which approach?

Statement type	Usual method
formula for all positive integers n	induction
'there is no...' or 'is irrational'	contradiction
'for all ...' that seems false	counterexample
algebraic identity	direct proof (LHS to RHS)

WORKED EXAMPLE 20 Choosing (standard)

Which method would you use to prove that 11n − 6 is divisible by 5 for all n ∈ ℤ+?

Solution

Induction (or direct: 11 ≡ 1 mod 5, so 11n − 6 ≡ 1 − 6 ≡ 0)R1

18 Mixed review: worked problems

Bringing the ideas together.

WORKED EXAMPLE 21 Induction with a trigonometric sum (exam level)

Prove that cos x + cos 3x + ... + cos(2n − 1)x = sin(2nx)/(2 sin x) for sin x ≠ 0.

Solution

n = 1: sin 2x/(2 sin x) = cos x ✓A1

Add cos(2k + 1)x: (sin 2kx + 2 sin x cos(2k + 1)x)/(2 sin x)M1

2 sin x cos(2k + 1)x = sin(2k + 2)x − sin 2kxA1

Sum = sin(2(k + 1)x)/(2 sin x); conclusionR1

Practice exercise 14

1. Prove by induction that 4n + 6n − 1 is divisible by 9.

19 Additional exam-style practice

Paper 1 proof questions.

WORKED EXAMPLE 22 Paper 1 question (exam level)

Prove by contradiction that log2 5 is irrational.

Solution

Assume log2 5 = p/q with integers p, q > 0M1

Then 2p = 5qA1

The LHS is even and the RHS odd: contradictionR1

Practice exercise 15

1. Prove that the product of any three consecutive integers is divisible by 6.

2. Prove by induction that 1/(1×2) + 1/(2×3) + ... + 1/(n(n + 1)) = n/(n + 1).

20 Exam-style questions with markscheme

Attempt each question under timed conditions before reading the markscheme.

Question 1 (Paper 1 style) (about 12 minutes)

Prove by induction that the sum from r = 1 to n of r(r + 1) = n(n + 1)(n + 2)/3, for n ∈ ℤ+. [7]

Markscheme

Part	Answer	Marks
	n = 1: LHS = 2, RHS = 2	A1
	assume true for n = k	M1
	add (k + 1)(k + 2) to both sides	M1
	k(k + 1)(k + 2)/3 + (k + 1)(k + 2)	A1
	= (k + 1)(k + 2)(k + 3)/3	A1
	this is P(k + 1)	A1
	conclusion referring to basis and inductive step	R1

Examiner's comments. Many candidates lost the final mark by omitting a full conclusion.

Question 2 (Paper 2 style) (about 12 minutes)

(a) Prove by induction that 7n − 3n is divisible by 4 for all n ∈ ℤ+. [6]

(b) Prove by contradiction that √3 is irrational. [4]

Markscheme

Part	Answer	Marks
(a)	basis: 4	A1
	assume 7k − 3k = 4m	M1
	7k+1 − 3k+1 = 7(4m + 3k) − 3 × 3k	M1
	= 4(7m + 3k)	A1 A1
	conclusion	R1
(b)	assume √3 = p/q in lowest terms	M1
	p2 = 3q2, so 3 divides p; p = 3m	A1
	q2 = 3m2, so 3 divides q	A1
	contradiction with lowest terms	R1

Examiner's comments. In (b), the step 'if 3 divides p2 then 3 divides p' should be stated.

21 Common misconceptions and links

Students often think…	Actually…
checking n = 1, 2, 3 proves P(n)	induction requires the inductive step
assume P(n) is true for all n	assume for a particular k only
omitting the conclusion	it earns a mark
a contradiction proof starts from the statement	it starts from the negation

How 1.15 connects to the rest of the course

Topic	Connection
1.6 Proof	direct proof
1.1 Series	sum formulas
1.12 Complex numbers	De Moivre's theorem
5.6 Differentiation	nth derivatives

22 Check your understanding

Section A: multiple choice

1. The first step of induction is

A. showing the basis case B. assuming P(k) C. the conclusion D. a counterexample

2. In the inductive step we prove

A. P(k + 1) ⇒ P(k) B. P(1) C. P(k) ⇒ P(k + 1) D. P(n) for all n

3. A statement can be disproved by

A. induction B. a single counterexample C. many examples D. contradiction only

4. Proof by contradiction begins by

A. assuming it is true B. checking n = 1 C. drawing a graph D. assuming the statement is false

Section B: structured

5. Prove by induction that 32n − 1 is divisible by 8. [6]

6. Prove that log3 5 is irrational. [4]

7. Show that 'all quadratics have two real roots' is false. [1]

Answers

1. A 2. C 3. B 4. D

5. Basis 8; 9k+1 − 1 = 9(8m + 1) − 1 = 8(9m + 1); conclusion.

6. 3p = 5q: a power of 3 cannot equal a power of 5 (unique factorization).

7. x2 + 1 = 0 has no real roots.

23 Summary and topic map

Idea	Remember
Induction	basis, assumption, inductive step, conclusion
Sums	add the (k + 1)th term
Divisibility	rewrite in terms of P(k)
Derivatives and recurrences	differentiate or apply the recurrence
Inequalities	extra comparison needed
Contradiction	assume false; reach impossibility
Counterexample	one case disproves

Before the exam, make sure you…

•write all four stages of induction
•show where the assumption is used
•state lowest terms in irrationality proofs
•give a specific counterexample

Further Proof on one page

Cover this page with a sheet of paper and try to rebuild it from memory. Whatever you can't recall is what to revise next.

Figure 1. Topic map for Further Proof.

24 Answers to practice exercises

Check your working against these answers. Full methods are expected in the exam.

Practice exercise 1

1. k2 + (2k + 1) = (k + 1)2

2. k2(k + 1)2/4 + (k + 1)3 = (k + 1)2(k2 + 4k + 4)/4

3. k/(k + 1) + 1/((k + 1)(k + 2)) = (k2 + 2k + 1)/((k + 1)(k + 2)) = (k + 1)/(k + 2)

4. k(k + 1)(k + 2)/3 + (k + 1)(k + 2) = (k + 1)(k + 2)(k + 3)/3

Practice exercise 2

1. (k + 1)3 − (k + 1) = (k3 − k) + 3k(k + 1); k(k + 1) is even, so 3k(k + 1) is a multiple of 6

2. 9k+1 − 1 = 9(8m + 1) − 1 = 72m + 8

3. 11k+1 − 6 = 11(5m + 6) − 6 = 55m + 60

Practice exercise 3

1. differentiate 2ke2x to get 2k+1e2x

2. differentiate (−1)k−1(k − 1)!x−k to get (−1)kk!x−k−1

3. 3(2 × 3k−1 + 1) − 2 = 2 × 3k + 1

Practice exercise 4

1. (k + 1)! = (k + 1)k! > (k + 1)2k > 2 × 2k

2. 3k+1 > 3(2k + 1) = 6k + 3 > 2k + 3

Practice exercise 5

1. as for √2: p2 = 3q2, so 3 | p, then 3 | q

2. if N is the largest, N + 2 is even and larger

3. contrapositive: if n is even, n2 = 4m2 is even

4. LHS is a multiple of 3, but 1 is not

Practice exercise 6

1. a = 1, b = −1

2. √2 + (−√2) = 0

3. n = 3: 9

Practice exercise 7

1. base 1 = 1; add 2k + 1 to k2

2. base 2 = 2; add (k + 1)(k + 2)

Practice exercise 8

1. 5k+1 + 3 = 5(5k + 3) − 12

2. (k + 1)3 + 2(k + 1) = (k3 + 2k) + 3(k2 + k + 1)

Practice exercise 9

1. 3k+1 > 6k + 3 > 2k + 3

2. (k + 1)! = (k + 1)k! > (k + 1)2k > 2k+1

Practice exercise 10

1. 3(3k−1 + 1) − 2 = 3k + 1

2. differentiate 2ke2x to get 2k+1e2x

Practice exercise 11

1. assume √3 = p/q in lowest terms; 3 divides p and q

2. 3 divides the LHS but not 1

Practice exercise 12

1. a = 2, b = −2

2. n = 3: 9

Practice exercise 13

1. n5 − n = (n − 1)n(n + 1)(n2 + 1); check each remainder

Practice exercise 14

1. 4k+1 + 6k + 5 = 4(4k + 6k − 1) − 18k + 9 = 9(4A − 2k + 1)

Practice exercise 15

1. one is even and one is a multiple of 3

2. base 1/2; add 1/((k + 1)(k + 2))

revisionprep.comIB-style notes · question bank · mock papers