Chapter 4 Combinatorics and Mathematical Induction

Practice questions

Using the result 1 + 3 + 5 + ... + (2n − 1) = n², what is 1 + 3 + 5 + ... + 39?

  1. 380
  2. 441
  3. 361
  4. 400
Answer and explanation

Answer: D

The last term 2n − 1 = 39 gives n = 20, so there are 20 odd numbers and the sum is 20² = 400. Taking n = 19 or 21 by mistake gives 361 or 441.

The expression n² − n + 41 gives a prime number for n = 1, 2, ..., 40. What does this show?

  1. That it gives a prime for every natural number n
  2. That induction proves it is always prime
  3. That checking many cases is not a proof: for n = 41 the value is 41², which is not prime
  4. That it is prime only for even n
Answer and explanation

Answer: C

For n = 41, 41² − 41 + 41 = 41², which has the factor 41. Many true cases make a conjecture, but only a proof, such as one by induction, covers every n.

To prove that 4ⁿ − 1 is divisible by 3, a student assumes 4ᵏ − 1 = 3m. Which expression does 4ᵏ⁺¹ − 1 then equal?

  1. 3(4m + 1)
  2. 4m
  3. 3m + 4
  4. 12m − 1
Answer and explanation

Answer: A

From the hypothesis 4ᵏ = 3m + 1. So 4ᵏ⁺¹ − 1 = 4(3m + 1) − 1 = 12m + 4 − 1 = 12m + 3 = 3(4m + 1), a multiple of 3.

A team of 11 is chosen from 15 players. The captain must be in the team and one injured player cannot be chosen. In how many ways can the team be chosen?

  1. ¹⁵C₁₁ = 1365
  2. ¹³C₁₀ = 286
  3. ¹⁴C₁₀ = 1001
  4. ¹³C₁₁ = 78
Answer and explanation

Answer: B

The captain takes one place, leaving 10 places. The captain and the injured player are removed from the pool, leaving 13 players. So the count is ¹³C₁₀ = ¹³C₃ = (13 × 12 × 11)/6 = 286.

If ⁿPᵣ = 210 and ⁿCᵣ = 35, what are n and r?

  1. n = 7, r = 3
  2. n = 6, r = 3
  3. n = 7, r = 4
  4. n = 10, r = 2
Answer and explanation

Answer: A

ⁿPᵣ/ⁿCᵣ = r! = 210/35 = 6 = 3!, so r = 3. Then n(n − 1)(n − 2) = 210 = 7 × 6 × 5, so n = 7. Check: ⁷C₃ = 35.

There are 9 points in a plane. Exactly 4 of them are collinear, and no other three are collinear. How many triangles have their vertices among these points?

  1. 84
  2. 80
  3. 76
  4. 120
Answer and explanation

Answer: B

Any 3 points give ⁹C₃ = 84 choices, but 3 points chosen from the 4 collinear ones make no triangle: ⁴C₃ = 4 such choices. Triangles = 84 − 4 = 80.

What is the sum of all the 3-digit numbers formed by using each of the digits 2, 4 and 6 exactly once?

  1. 2664
  2. 1332
  3. 888
  4. 3996
Answer and explanation

Answer: A

There are 3! = 6 numbers, and each digit appears 2! = 2 times in each place. Sum = 2 × (2 + 4 + 6) × 111 = 2 × 12 × 111 = 2664. Check: 246 + 264 + 426 + 462 + 624 + 642 = 2664.

In how many ways can 5 men and 3 women sit in a row if the 3 women must sit together?

  1. 720
  2. 40320
  3. 2880
  4. 4320
Answer and explanation

Answer: D

Bundle the 3 women as one unit: 5 men + 1 unit = 6 units, arranged in 6! = 720 ways. The women arrange themselves inside the unit in 3! = 6 ways. Total 720 × 6 = 4320.

How many different arrangements are there of the letters of ENGINEERING?

  1. 39916800
  2. 554400
  3. 277200
  4. 1663200
Answer and explanation

Answer: C

There are 11 letters: E three times, N three times, G twice, I twice and R once. The count is 11!/(3! × 3! × 2! × 2!) = 39916800/144 = 277200.

What is the units digit of 1! + 2! + 3! + ... + 100!?

  1. 0
  2. 3
  3. 9
  4. 1
Answer and explanation

Answer: B

Every factorial from 5! onwards contains the factors 2 and 5, so it ends in 0. The units digit comes from 1 + 2 + 6 + 24 = 33, so it is 3.

If 1/4! − 1/5! = x/6!, what is x?

  1. 36
  2. 30
  3. 24
  4. 6
Answer and explanation

Answer: C

Multiply by 6!: 6!/4! − 6!/5! = x, that is 6 × 5 − 6 = 30 − 6 = 24.

If n!/(n − 2)! = 132, what is n?

  1. 11
  2. 12
  3. 66
  4. 13
Answer and explanation

Answer: B

n!/(n − 2)! = n(n − 1) = 132 = 12 × 11, so n = 12.

A test has 8 true-false questions, and each question may be marked True, marked False or left blank. In how many ways can the paper be handled?

  1. 2⁸ = 256
  2. 8 × 3 = 24
  3. 2⁸ − 1 = 255
  4. 3⁸ = 6561
Answer and explanation

Answer: D

Each of the 8 questions has 3 independent choices (True, False, blank), so by the product rule there are 3⁸ = 6561 ways. 2⁸ would forbid leaving a question blank.

In a class, 75% of the students play cricket and 55% play football. What is the least possible percentage who play both?

  1. 20%
  2. 30%
  3. 45%
  4. 55%
Answer and explanation

Answer: B

n(C ∩ F) = n(C) + n(F) − n(C ∪ F), and n(C ∪ F) is at most 100%. So n(C ∩ F) is at least 75 + 55 − 100 = 30%.

How many 3-digit odd numbers with all digits different can be formed from the digits 1, 2, 3, 4, 5, 6?

  1. 60
  2. 120
  3. 90
  4. 36
Answer and explanation

Answer: A

Fill the units place first: it must be 1, 3 or 5 (3 ways). The hundreds place then has 5 choices and the tens place 4. Total 3 × 5 × 4 = 60.

For the claim 'n² + n + 1 is even', the inductive step P(k) ⇒ P(k + 1) can be carried out. Why is the claim still not proved?

  1. Because P(1) = 3 is odd, so the initial step fails
  2. Because the inductive step needs k ≥ 2
  3. Because induction cannot prove statements about even numbers
  4. Because the claim is true only for even n
Answer and explanation

Answer: A

Induction needs both steps. Here P(1) gives 1 + 1 + 1 = 3, which is odd, so there is no first true statement to pass on. In fact n² + n + 1 = n(n + 1) + 1 is always odd.

By which number is 5ⁿ − 1 divisible for every natural number n?

  1. 3
  2. 6
  3. 5
  4. 4
Answer and explanation

Answer: D

For n = 1, 5 − 1 = 4. If 5ᵏ − 1 = 4m, then 5ᵏ⁺¹ − 1 = 5(4m + 1) − 1 = 20m + 4 = 4(5m + 1). So 4 divides it for all n. (For n = 1 the value 4 is not divisible by 3, 6 or 5.)

In proving 1 + 2 + ... + n = n(n + 1)/2, what is added to k(k + 1)/2 to obtain the sum for n = k + 1?

  1. k
  2. k + 1
  3. k + 2
  4. 2k + 1
Answer and explanation

Answer: B

The sum up to k + 1 is the sum up to k plus the next term, k + 1. Then k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, as required.

The statement 2ⁿ > n² is true for n = 1 but false for n = 2, 3 and 4. From which value should an induction proof start so that the statement is proved for every n from there on?

  1. n = 1
  2. n = 2
  3. n = 5
  4. n = 4
Answer and explanation

Answer: C

2⁵ = 32 > 25, and for k ≥ 5 the inductive step works because 2k² > (k + 1)². Starting at 1 fails because the chain breaks at n = 2 (4 is not greater than 4).

In the inductive step of a proof by mathematical induction, what must be shown?

  1. P(k) is true for every k
  2. P(1) is true
  3. If P(k) is true, then P(k + 1) is true
  4. P(k + 1) is true without using P(k)
Answer and explanation

Answer: C

The inductive step assumes P(k) (the induction hypothesis) and shows it forces P(k + 1). Checking P(1) is the initial step, and assuming P(k) for every k would assume what is to be proved.

Privacy · Terms · Refunds · Delivery