The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: AMC-10, AMC-12, AIME.

The binomial coefficients represent the number of ways in which we can place a symbol k times in a line of n slots:

equation

This is simply the number of linear permutations of k identical symbols of one kind and n-k identical symbols of another kind:

equation

Since, by choosing the positions of one symbol, the positions of the other symbol get to be automatically chosen as well, the binomial coefficients are symmetric:

equation

equation

The binomial coefficients can be computed mechanically by using Pascal's triangle:

figure

One notices that, except for the coefficients at the ends of the rows, each coefficient is the sum of the one directly above it and the one above and to the left.

This observation leads us to a general formula for 'downgrading' binomial coefficients (i.e. finding the higher order ones from lower order ones):

equation

A useful formula can be derived by setting both terms to 1 in the binomial expression:

equation

equation

i.e. the sum of combinations of n is equal to 2n.

This fact can be seen by adding up all the numbers in each row of Pascal's triangle: we get the powers of 2.

Using algebraic identities with binomes to derive identities among binomial coefficients

Various recurrence formulas for computing combinations can be obtained from algebraic identities with binomes.

Example 1: Using the identity:

equation

we can identify the coefficients of xk from the left expression and the right expression:

equation

This is easy to perform since 1k=1 for any k.

The recurrence formula obtained permits us to 'downgrade' combinations (binomial coefficients) from row n+1 in the Pascal triangle to row n. Visually, one can check that numbers in the Pascal triangle (except the ones on the edges) result by adding up the coefficient directly above with the coefficient above and to the left - this is exactly what the recurrence formula allowed us to prove.

Another proof for the same recurrence formula uses the factorial definition of the binomial coefficients:

equation

equation

equation

equation

equation

equation

equation

Example 2: Using the identity:

equation

compute the coefficient of xn on both sides:

equation

and use the symmetry property of the binomial coefficients to derive the identity:

equation

Other useful identities comprising binomial coefficients may be derived in similar ways.

Often, such identities either shorten the time for solving a problem or are directly part of the requirements.