• Foundation
  • About 17 min
  • 5 practice questions

Sums of binomial coefficients and divisibility

Use special values of x in (1 + x)ⁿ to find sums of binomial coefficients, find the sum of the coefficients of any expansion, and use the binomial theorem to prove divisibility results and find remainders.

If something looks wrong, please tell us.

By the end of this lesson you can

  • Show that nC0 + nC1 + ... + nCn = 2ⁿ and nC0 − nC1 + nC2 − ... = 0.
  • Find the sum of the coefficients of an expansion by putting each variable equal to 1.
  • Evaluate sums such as Σ 2ʳ nCr.
  • Prove divisibility results such as 36 divides 7ⁿ − 6n − 1, and find remainders.

Putting special numbers into (1 + x)ⁿ = nC0 + nC1 x + ... + nCn xⁿ turns the binomial theorem into a machine for adding binomial coefficients. Writing a number as 1 plus a multiple of something does the same for divisibility questions. This lesson shows both techniques.

Sums of binomial coefficients

Put x = 1 in (1 + x)ⁿ: nC0 + nC1 + nC2 + ... + nCn = 2ⁿ. This is why row n of Pascal's triangle adds up to 2ⁿ. It also matches counting: a set of n elements has 2ⁿ subsets, and nCr of them have r elements.

Put x = −1 in (1 + x)ⁿ: nC0 − nC1 + nC2 − ... + (−1)ⁿ nCn = 0, for n ≥ 1. Adding and subtracting these two results shows that the coefficients in even positions and those in odd positions each add up to 2ⁿ⁻¹.

nC0 + nC1 + ... + nCn = 2ⁿ; nC0 − nC1 + nC2 − ... = 0; nC0 + nC2 + nC4 + ... = nC1 + nC3 + ... = 2ⁿ⁻¹.

— Sums of binomial coefficients

Worked example 1: sums

(i) 10C0 + 10C1 + ... + 10C10 = 2¹⁰ = 1024. (ii) 8C0 + 8C2 + 8C4 + 8C6 + 8C8 = 2⁷ = 128. Check: 1 + 28 + 70 + 28 + 1 = 128. (iii) Σ (r = 0 to n) 2ʳ nCr: put x = 2 in (1 + x)ⁿ to get 3ⁿ. For n = 3: 1 + 2(3) + 4(3) + 8(1) = 27 = 3³.

The sum of the coefficients of any expansion

Putting every variable equal to 1 makes every term equal to its coefficient, so the value of the expression at 1 is the sum of the coefficients. For example, the coefficients of (2x − 1)⁵ add up to (2 − 1)⁵ = 1, which agrees with lesson 1: 32 − 80 + 80 − 40 + 10 − 1 = 1.

Divisibility

To show that a number divides an expression, write the base as 1 plus a multiple of a suitable number and expand. All the terms after the first two contain a high power of that number.

Proving divisibility with the binomial theorem

  1. Write the base as 1 + m For 7ⁿ use 7 = 1 + 6.
  2. Expand (1 + m)ⁿ 1 + nm + nC2 m² + nC3 m³ + ...
  3. Move the first terms Subtract the terms named in the question.
  4. Factor out m² What is left is m² × (a whole number).

Worked example 2: 7ⁿ − 6n − 1 is divisible by 36

For a positive integer n: 7ⁿ = (1 + 6)ⁿ = 1 + n(6) + nC2(6²) + nC3(6³) + ... + 6ⁿ. So 7ⁿ − 6n − 1 = 6²[nC2 + nC3(6) + ... + 6ⁿ⁻²] = 36k, where k is a whole number (for n = 1 the bracket is empty and the expression is 0). Hence 36 divides 7ⁿ − 6n − 1. Check n = 2: 49 − 12 − 1 = 36.

Worked example 3: 4ⁿ − 3n − 1 is divisible by 9

4ⁿ = (1 + 3)ⁿ = 1 + 3n + 3²[nC2 + nC3(3) + ...]. So 4ⁿ − 3n − 1 = 9 × (a whole number). Check n = 3: 64 − 9 − 1 = 54 = 9 × 6.

Worked example 4: remainders

(i) Find the remainder when 2³⁰ is divided by 7. Working: 2³⁰ = (2³)¹⁰ = 8¹⁰ = (7 + 1)¹⁰. Every term of the expansion except the last contains a factor 7, and the last term is 1¹⁰ = 1. So the remainder is 1. (ii) Show that 11ⁿ − 1 is divisible by 10: 11ⁿ = (1 + 10)ⁿ = 1 + 10n + nC2(10²) + ..., so 11ⁿ − 1 = 10 × (n + nC2(10) + ...).

Worked example 5: a − b divides aⁿ − bⁿ

For distinct integers a and b, write a = (a − b) + b. Then aⁿ = [(a − b) + b]ⁿ = (a − b)ⁿ + nC1 (a − b)ⁿ⁻¹b + ... + nC(n − 1)(a − b)bⁿ⁻¹ + bⁿ. Every term except bⁿ has a factor (a − b), so aⁿ − bⁿ = (a − b) × (a whole number). For example, 5 − 2 = 3 divides 5⁴ − 2⁴ = 625 − 16 = 609 = 3 × 203.

Key takeaways: put x = 1 and x = −1 in (1 + x)ⁿ to get 2ⁿ and 0 as sums of binomial coefficients; put each variable equal to 1 to add the coefficients of any expansion. For divisibility and remainders, write the base as 1 plus a multiple (or a multiple plus 1), expand, and factor out what is common.

Check your understanding

  1. 1. What is the sum of the coefficients in the expansion of (3x − 2)⁵?

    1. 1
    2. 243
    3. −1
    4. 3125
    Show answer

    Answer: A. Put x = 1: (3 − 2)⁵ = 1⁵ = 1. Every term becomes its coefficient, so the coefficients add up to 1.

  2. 2. What is 7C0 + 7C1 + 7C2 + ... + 7C7?

    1. 49
    2. 64
    3. 128
    4. 256
    Show answer

    Answer: C. Put x = 1 in (1 + x)⁷: the sum of all the binomial coefficients is 2⁷ = 128.

  3. 3. What is 4C0 + 2(4C1) + 4(4C2) + 8(4C3) + 16(4C4)?

    1. 16
    2. 81
    3. 64
    4. 32
    Show answer

    Answer: B. This is Σ 2ʳ 4Cr, the expansion of (1 + 2)⁴ = 3⁴ = 81. Check: 1 + 8 + 24 + 32 + 16 = 81.

  4. 4. What is the remainder when 3⁴⁰ is divided by 8?

    1. 3
    2. 0
    3. 7
    4. 1
    Show answer

    Answer: D. 3⁴⁰ = 9²⁰ = (8 + 1)²⁰. Every term of the expansion except the last has a factor 8, and the last term is 1. So the remainder is 1.

  5. 5. Which number always divides 4ⁿ − 3n − 1 for every positive integer n?

    1. 4
    2. 27
    3. 6
    4. 9
    Show answer

    Answer: D. 4ⁿ = (1 + 3)ⁿ = 1 + 3n + 9[nC2 + 3(nC3) + ...], so 4ⁿ − 3n − 1 is a multiple of 9. For n = 2 the value is 16 − 6 − 1 = 9, which rules out 27, 4 and 6.

Privacy · Terms · Refunds · Delivery