Binomial Coefficients

01 / UNDERSTAND & APPLY

1. Why an expansion contains combinations

In the product (a + b)ⁿ, choose either a or b from each of n identical factors. A term a^(n−r)bʳ appears whenever b is selected from exactly r factor positions. There are C(n,r) ways to choose those positions. Grouping equal products gives the finite binomial theorem. This counting argument explains the coefficients without requiring a table to be memorized.

Here n is a nonnegative integer and r ranges from 0 to n. The coefficient C(n,r) = n!/[r!(n−r)!] is an integer even though its formula is a quotient. The conventions 0! = 1 and C(n,0) = C(n,n) = 1 include the two endpoint terms. For combinatorial identities, it is often convenient to define C(n,r) = 0 for integer r outside 0,…,n.

The expansion contains n + 1 formal terms before any special numerical cancellation. The term with index r is commonly called T_(r+1), because r begins at zero while ordinary term numbering begins at one. Distinguish the term, which includes powers of variables, from its numerical coefficient.

The finite theorem applies to polynomial or Laurent-polynomial substitutions such as a = 2x² and b = −1/x, provided the original expression is defined. If a denominator contains x, exclude x = 0 even when a particular extracted term is constant. Noninteger powers use an infinite binomial series with convergence restrictions and are not covered by the finite n + 1-term formula.

02 / UNDERSTAND & APPLY

2. Symmetry, Pascal’s identity and two counting stories

Choosing r objects to include is equivalent to choosing n − r objects to exclude, so C(n,r) = C(n,n−r). This is why each row of Pascal’s triangle is symmetric. If one particular object is singled out, an r-subset either contains it or does not. The two cases give C(n,r) = C(n−1,r−1) + C(n−1,r), Pascal’s identity.

Adding all entries in row n counts every subset of an n-element set, giving ΣC(n,r) = 2ⁿ. Substituting a = b = 1 into the theorem gives the same result algebraically. For n ≥ 1, substituting a = 1, b = −1 gives Σ(−1)ʳC(n,r) = 0, so the sums of even-indexed and odd-indexed coefficients are each 2^(n−1). The n = 0 case must be treated separately.

Vandermonde’s identity says Σᵣ C(m,r)C(n,k−r) = C(m+n,k), with terms outside their valid index ranges interpreted as zero. To see it, choose k people from two disjoint groups of sizes m and n, classifying by how many came from the first group. Algebraically, compare the coefficient of xᵏ in (1 + x)ᵐ(1 + x)ⁿ.

A useful special case is Σᵣ₌₀ⁿC(n,r)² = C(2n,n). It follows by choosing n objects from two groups of n and using C(n,n−r) = C(n,r). This is a sum of squares, not the square of a sum. The latter would contain cross terms and equal 4ⁿ instead.

03 / UNDERSTAND & APPLY

3. Solve the exponent equation before calculating the coefficient

For (αxᵖ + βxᵠ)ⁿ, the r-indexed term is C(n,r)α^(n−r)βʳx^[p(n−r)+qr]. To find the coefficient of xᵏ, solve p(n−r) + qr = k, then check that r is an integer between 0 and n. If no admissible r exists, the coefficient is zero. Computing factorials before checking the exponent wastes work and can hide an impossible term.

When p = q, all terms have the same power of x and must be combined; the one-index exponent equation no longer selects a unique term. The expression simplifies to (α + β)ⁿx^(pn). More generally, in a product of two expansions, several pairs of indices may contribute to the same requested power. Add every admissible contribution.

For a constant term, set the exponent equal to zero. A fractional value of r does not mean a fractional-numbered term exists. It means the requested power is absent from this finite expansion. Negative powers are allowed in a Laurent expansion, but the index r remains an integer selection count.

04 / UNDERSTAND & APPLY

4. Differentiate a generating polynomial to count weighted sums

Write (1 + x)ⁿ = ΣC(n,r)xʳ. Differentiating gives n(1 + x)^(n−1) = ΣrC(n,r)x^(r−1). Multiplying by x and setting x = 1 gives ΣrC(n,r) = n2^(n−1), for n ≥ 1. The factor r appears because differentiation records how many variable factors each term contains.

Differentiating twice gives Σr(r−1)C(n,r) = n(n−1)2^(n−2) for n ≥ 2. Since r² = r(r−1) + r, combine the two identities to obtain Σr²C(n,r) = n(n+1)2^(n−2), again with small n handled directly if the derivation used a second derivative.

The first identity also has a counting proof: choose a subset and distinguish one member. Either classify by its size r, giving rC(n,r), or first choose the distinguished person in n ways and then choose any subset of the remaining n − 1 people. This provides a conceptual check on the algebra and helps generalize to other weighted sums.

For alternating weighted sums, substitute x = −1 only after differentiating the finite polynomial. Terms with powers of zero need careful handling for small n. Do not copy a formula derived for n ≥ 3 into n = 1 and interpret 0 raised to a negative exponent.

05 / UNDERSTAND & APPLY

5. Compare neighbors instead of expanding everything

Adjacent binomial coefficients satisfy C(n,r+1)/C(n,r) = (n−r)/(r+1). This ratio exceeds 1 before the middle, equals 1 when two central entries tie, and falls below 1 afterward. Thus an even n gives one largest central coefficient C(n,n/2), while an odd n gives two equal largest coefficients at r = (n−1)/2 and (n+1)/2.

The greatest numerical term in (a + b)ⁿ is a different question when a and b are positive and unequal. Its adjacent ratio is T_(r+2)/T_(r+1) = [(n−r)/(r+1)](b/a). The additional factor shifts the maximum. Locate where this ratio crosses 1 and check any equality case, which produces two tied neighboring terms.

If terms have alternating signs, distinguish greatest value from greatest absolute value. Comparing positive magnitudes uses |b/a| in the ratio, but the largest signed term must also have the appropriate sign. If a or b is zero, handle the expansion directly rather than dividing by zero in the ratio formula.

For the positive-term case, do not round a threshold blindly. A statement such as the ratio is greater than one for r < 8/3 means terms increase through the corresponding integer indices; then explicitly compare the neighboring candidates. This index check prevents an off-by-one answer between r and the ordinary term number r + 1.

06 / UNDERSTAND & APPLY

6. Congruence turns large powers into small remainders

For integers A and B and a positive integer m, write A ≡ B (mod m) when m divides A − B. This means A and B have the same remainder on division by m. Congruences may be added, subtracted and multiplied. Consequently, one can replace a base by a simpler congruent number before raising it to a nonnegative integer power.

Binomial expansion is particularly effective when the base is close to a multiple of the modulus. If a = qm + r, then aⁿ = (qm + r)ⁿ and every term except rⁿ contains a factor m. Therefore aⁿ ≡ rⁿ (mod m). For a remainder modulo m², retain the first two terms of (1 + m)ⁿ: 1 + nm; all terms with m² or higher powers vanish modulo m².

The remainder must be the unique integer between 0 and m − 1. A convenient residue such as −3 is not the conventional remainder modulo 7; its remainder is 4. Always reduce the final small expression into the required range. Divisibility is the special case where the residue is zero.

For negative residues, parity can simplify the power. For example, (m − 1)ⁿ ≡ (−1)ⁿ (mod m). But modulo m², the next binomial term may matter. Choosing the modulus first tells you how many terms survive; expanding the full enormous power is unnecessary.

07 / UNDERSTAND & APPLY

7. Retain the exact factors needed for a proof

To prove m² divides (1 + m)ⁿ − 1 − nm, expand and factor m² from every remaining term. This proves the statement for all positive integer m and nonnegative integer n without numerical testing. A few examples can suggest divisibility but cannot replace the factor argument for an arbitrary exponent.

For a prime p and 1 ≤ r ≤ p − 1, p divides C(p,r). In the factorial expression, p occurs in p! but not in r! or (p−r)!, so the denominator has no factor p to cancel it. Therefore (a + b)ᵖ ≡ aᵖ + bᵖ (mod p) for integers a,b. The primality assumption is essential; for composite n, the intermediate coefficients need not all be divisible by n.

The prime argument is an integer-factor argument, not ordinary division of congruences. In modular arithmetic, division by c is valid with the same modulus only if c has a multiplicative inverse modulo that modulus, equivalently gcd(c,m) = 1. From 2A ≡ 2B (mod 6), one may conclude A ≡ B (mod 3), but not necessarily modulo 6.

This matters when a binomial identity has a factorial denominator. You may know the binomial coefficient is an integer, but reducing numerator and denominator separately modulo a composite number and cancelling a noninvertible denominator can destroy information. Use exact integer factorization or a justified inverse instead.

08 / UNDERSTAND & APPLY

8. Original practice: terms, identities and maxima

Write the general term before attempting a coefficient question. State whether the requested object is a coefficient, an entire term, a sum, or a greatest positive value.

09 / UNDERSTAND & APPLY

9. Original practice: remainders with explicit moduli

For each answer, name the congruence or factor that permits discarding terms. The fact that a number is large is not a reason to approximate it in a remainder problem.

10 / UNDERSTAND & APPLY

10. The same expansion supports two different kinds of reasoning

Coefficient extraction keeps one exponent and discards terms with other exponents. Modular arithmetic keeps terms that are not multiples of the modulus and discards those that are. Both start from the same exact binomial expansion, but the selection rule is different. State which rule you are using before simplifying.

The main coefficient errors are off-by-one term numbering, forgetting numerical powers, dropping alternating signs, accepting a noninteger index, and treating the greatest coefficient as the greatest term. The main remainder errors are forgetting to reduce a negative residue, discarding terms too early for a squared modulus, and cancelling factors without a modular inverse.

A compact solution should show the general term or surviving modular terms, then the index or divisibility argument, then the exact arithmetic. Check a coefficient with a small expansion when feasible and a remainder with direct modular exponentiation. These are independent verification routes that do not require writing the full large power.

Finally, keep the theorem’s domain visible: finite expansion means a nonnegative integer exponent. Variables appearing in denominators cannot be zero. Greatest-term ratio arguments require positivity or an explicit switch to magnitudes. Prime divisibility facts require a prime. These conditions determine whether a familiar-looking shortcut is actually valid.