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:
This is simply the number of linear permutations of k identical symbols of one kind and n-k identical symbols of another kind:
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:
The binomial coefficients can be computed mechanically by using Pascal's triangle:
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):
A useful formula can be derived by setting both terms to 1 in the binomial expression:
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
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:
we can identify the coefficients of xk from the left expression and the right expression:
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:
Example 2: Using the identity:
compute the coefficient of xn on both sides:
and use the symmetry property of the binomial coefficients to derive the identity:
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.