The rise and fall of binomial coefficients

When you expand (x + y)n, the coefficients increase then decrease. The largest coefficient is in the middle if n is even; it’s the two in the middle if n is odd. For example, the coefficients for (1 + x)4 are 1, 4, 6, 4, 1 and the coefficients for (1 + x)5 are 1, 5, 10, 10, 5, 1.

More generally, if a > 0 and b > 0, the coefficients of (ax + by)n can only have one maximum. They may increase, or decrease, or change direction once, but they cannot wiggle more than that. They can’t, for example, increase, decrease, then increase again.

Here’s a proof. The coefficients are

{n \choose k} a^k b^{n-k}

To show that the coefficients are unimodal as a function of k, we’ll show that their logarithms are unimodal. And we’ll do that by showing that they are samples from a concave function.

The log of the kth coefficient is

log Γ(n+1) – log Γ(k+1) – log Γ(n-k+1) + k log a + (n-k) log b.

As a function of k, the terms

log Γ(n+1) + k log a + (n-k) log b

form an affine function. The function log Γ is convex, so -log Γ is concave. The composition of a concave function with an affine function is concave, so – log Γ(k+1) and – log Γ(n-k+1) are concave functions of k. The sum of concave functions is concave. And the sum of a concave function with an affine function is concave. So binomial coefficients are log-concave and they can only have one maximum.

(The fact log Γ(z) is a convex is the easy direction of the Bohr-Mollerup theorem. The harder direction is that Γ(z) is the only way to extend factorials to all reals that is log-convex.)

6 thoughts on “The rise and fall of binomial coefficients

  1. Nice, but a bit of an elephant gun for a mosquito? Or perhaps that was the point, but rather easier is that the ratio of consecutive terms is ((n-k)/(k+1))(b/a). Since the first factor is decreasing in k and the second constant, they increase so long as the first factor is > 1 and decrease thereafter (and of course this also tells you where the maximum is).

  2. Luke: There is. The difference between two consecutive elements on row n equals {by the “Pascal” relation} the difference between two 2-apart elements on row n-1, which {by induction and symmetry} has the right sign.

    You need to set up the induction hypothesis with a little care: it needs to say that (n choose k) is constant (at zero) unless 0 <= k <= n; otherwise it's strictly increasing "to the middle" and then strictly decreasing.

    You need symmetry to get things to come out right in the middle — e.g., to see that (5 choose 3) – (5 choose 1) equals (5 choose 2) – (5 choose 1) and is therefore positive.

  3. Abhishek Mishra

    It is not clear that why should a log-concave function have a unique maximum.

  4. It could have a flat spot, but it could not have two isolated maxima. Otherwise plot the log of the function and draw a line between the two maxima. The joining line lies above the graph, so the graph is not concave.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>