Binomial Theorem and Mathematical Induction

The binomial theorem expands powers of two-term expressions without repeated multiplication, while mathematical induction proves statements that are meant to hold for every positive integer. Both topics use patterns carefully: one counts the ways terms can be chosen, and the other turns a verified first case into an unbroken chain of cases. Comfort with exponents, factorials, and algebraic expansion is helpful; review Algebra and Sequences and Series if those ideas are new.

Binomial Coefficients and Pascal’s Triangle

The binomial coefficient C(n, r), read “n choose r,” counts the number of ways to choose r objects from n objects when order does not matter. For integers 0 ≤ r ≤ n,

C(n, r) = n!/[r!(n − r)!], where n! = n(n − 1) · · · 2 · 1 and 0! = 1.

Pascal’s triangle places these coefficients in rows. The outside entries are 1; each interior entry is the sum of the two entries immediately above it.

n = 0:                 1
n = 1:              1     1
n = 2:           1     2     1
n = 3:        1     3     3     1
n = 4:     1     4     6     4     1

Thus row n gives the coefficients for a power of n. The symmetry C(n, r) = C(n, n − r) reflects that choosing r objects is equivalent to choosing which n − r objects to leave out.

Worked example: calculate a coefficient

Find C(7, 3), or “7 choose 3.”

C(7, 3) = 7!/[3!(7 − 3)!]
    = 7!/(3!4!)
    = (7 · 6 · 5)/(3 · 2 · 1)
    = 35

Cancel factorials before multiplying large numbers. The result says there are 35 unordered groups of three chosen from seven.

The Binomial Theorem

For a non-negative integer n, the theorem states

(a + b)ⁿ = Σ_{r = 0}ⁿ C(n, r)a^{n − r}b^r.

The sigma symbol means “add the displayed expression for every integer r from 0 through n.” In the term with index r, the exponent on a decreases from n to 0, the exponent on b increases from 0 to n, and the two exponents always total n.

Why the coefficients appear

In (a + b)ⁿ, multiplication chooses one term from each of n identical-looking factors. To make a^{n − r}b^r, choose b from exactly r of the factors. There are C(n, r) ways to make that choice, so that is the coefficient.

Worked example: expand a binomial

Expand (2x − 3)⁴. Treat the two terms as a = 2x and b = −3, so signs are included in the powers of b.

(2x − 3)⁴
= C(4, 0)(2x)⁴ + C(4, 1)(2x)³(−3)
  + C(4, 2)(2x)²(−3)² + C(4, 3)(2x)(−3)³ + C(4, 4)(−3)⁴
= 16x⁴ − 96x³ + 216x² − 216x + 81

A useful check: substituting x = 0 gives 81 in both the original expression and the expansion.

General Terms and Selected Coefficients

The general, or (r + 1)th, term of (a + b)ⁿ is

T_{r + 1} = C(n, r)a^{n − r}b^r, for r = 0, 1, ..., n.

The wording matters: the first term uses r = 0, so the kth term uses r = k − 1.

Worked example: find one coefficient

Find the coefficient of x³ in (1 + 2x)⁵.

To get x³, choose r = 3:
C(5, 3)(1)⁵⁻³(2x)³
= 10 · 1 · 8x³
= 80x³

Coefficient of x³: 80

Worked example: solve for the required term

Find the term containing x⁴ in (3x² + 2/x)⁵.

T(r + 1) = C(5, r)(3x²)⁵⁻ʳ(2/x)ʳ

Power of x = 2(5 − r) − r = 10 − 3r.
Set 10 − 3r = 4:
3r = 6, so r = 2.

T₃ = C(5, 2)(3x²)³(2/x)²
    = 10 · 27x⁶ · 4/x²
    = 1080x⁴

Solving for the exponent before calculating prevents expanding five large terms unnecessarily.

Applications of Binomial Expansion

Binomial coefficients are used in probability, counting, and approximation. For example, when a fair coin is tossed five times, exactly three heads can occur in C(5, 3) = 10 sequences. Since each sequence has probability (1/2)⁵, the probability is 10/32 = 5/16.

They also give quick information about a polynomial without a full expansion. The sum of the coefficients of a polynomial P(x) is P(1). Therefore the coefficients of (2x − 1)⁶ sum to (2 · 1 − 1)⁶ = 1. This check includes negative coefficients correctly.

Mathematical Induction: A Proof for Every Integer

A statement P(n) about an integer n cannot be proved for infinitely many values by checking examples. Mathematical induction proves it by establishing a starting point and a rule that advances from any one case to the next.

Base case: verify P(n₀) directly.
Inductive hypothesis: assume P(k) is true for an arbitrary integer k ≥ n₀.
Inductive step: using that assumption, prove P(k + 1).
Conclusion: state that P(n) is true for every integer n ≥ n₀.

The hypothesis is not the result being proved: it is a temporary, permitted assumption used only to establish the next case. Like a row of dominoes, the base case starts the chain and the step ensures each true case passes truth to its successor.

Worked proof: sum of the first integers

Prove 1 + 2 + · · · + n = n(n + 1)/2 for every integer n ≥ 1.

Base case n = 1:
left side = 1; right side = 1(1 + 1)/2 = 1. True.

Inductive hypothesis:
Assume 1 + 2 + ··· + k = k(k + 1)/2 for some k ≥ 1.

Inductive step:
1 + 2 + ··· + k + (k + 1)
= k(k + 1)/2 + (k + 1)       [use the hypothesis]
= (k + 1)(k + 2)/2
= (k + 1)[(k + 1) + 1]/2.

This is the required formula with n = k + 1.
Therefore the formula holds for every integer n ≥ 1.

Worked proof: a divisibility statement

Prove that 8ⁿ − 1 is divisible by 7 for every integer n ≥ 1.

Base case n = 1:
8¹ − 1 = 7, which is divisible by 7.

Inductive hypothesis:
Assume 8ᵏ − 1 is divisible by 7. Thus 8ᵏ − 1 = 7m
for some integer m.

Inductive step:
8ᵏ⁺¹ − 1 = 8(8ᵏ) − 1
          = 8(8ᵏ − 1) + 7
          = 8(7m) + 7
          = 7(8m + 1).

Since 8m + 1 is an integer, 8ᵏ⁺¹ − 1 is divisible by 7.
Therefore 7 divides 8ⁿ − 1 for every integer n ≥ 1.

Worked proof: an inequality

Prove that 2ⁿ ≥ n + 1 for every integer n ≥ 0.

Base case n = 0:
2⁰ = 1 and 0 + 1 = 1, so 1 ≥ 1.

Inductive hypothesis:
Assume 2ᵏ ≥ k + 1 for some k ≥ 0.

Inductive step:
2ᵏ⁺¹ = 2 · 2ᵏ
       ≥ 2(k + 1)             [multiply by positive 2]
       = 2k + 2
       ≥ k + 2                [because k ≥ 0].

Thus 2ᵏ⁺¹ ≥ (k + 1) + 1.
Therefore 2ⁿ ≥ n + 1 for every integer n ≥ 0.

In an inequality proof, justify every inequality direction. Multiplying by a positive number preserves the direction; multiplying by a negative number would reverse it.

Common Mistakes to Avoid

Using the wrong row: coefficients of a power n come from row n, beginning with row 0 as 1.
Losing a negative sign: in (3x − 2)ⁿ, use b = −2, not 2. Odd powers remain negative.
Confusing term number and index: T₄ has r = 3, not 4.
Checking only a few cases: values such as n = 1, 2, 3 suggest a pattern but do not prove it for all integers.
Assuming what must be shown: in the inductive step, start from the expression for k + 1 and use the hypothesis about k; do not simply write the desired result.
Forgetting the stated range: induction proves only the range covered by its base case and step.

Practice Set

Compute C(9, 2) and C(9, 7).
Write the coefficients, in order, of (1 + x)⁶.
Expand (x − 2)⁴.
Find the coefficient of x² in (3 − x)⁵.
Find the fourth term of (2x + 1)⁷.
Find the term independent of x in (x² + 1/x)⁶.
A bag has 8 distinct beads. In how many ways can 3 beads be selected?
Prove by induction that 1 + 3 + 5 + · · · + (2n − 1) = n² for n ≥ 1.
Prove by induction that 5ⁿ − 1 is divisible by 4 for n ≥ 1.
Prove by induction that 3ⁿ > 2n for n ≥ 1.

Answer Checks

C(9, 2) = 9 · 8/2 = 36. By symmetry, C(9, 7) = C(9, 2) = 36.
1, 6, 15, 20, 15, 6, 1.
x⁴ − 8x³ + 24x² − 32x + 16.
The required term has r = 2: C(5, 2)3³(−x)² = 270x². The coefficient is 270.
T₄ uses r = 3: C(7, 3)(2x)⁴ = 35 · 16x⁴ = 560x⁴.
The exponent is 2(6 − r) − r = 12 − 3r. It is zero when r = 4. The constant term is C(6, 4) = 15.
C(8, 3) = 8 · 7 · 6/(3 · 2 · 1) = 56 selections.
Base: for n = 1, both sides are 1. Assume the sum through 2k − 1 is k². Adding the next odd number gives k² + (2k + 1) = (k + 1)², which is the required next case.
Base: 5 − 1 = 4 is divisible by 4. If 5^k − 1 = 4m, then 5^{k + 1} − 1 = 5(5^k − 1) + 4 = 4(5m + 1), so the next case is divisible by 4.
Base: 3 > 2. Assume 3^k > 2k for k ≥ 1. Then 3^{k + 1} = 3 · 3^k > 6k ≥ 2k + 2 = 2(k + 1). Thus the result holds for k + 1.