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
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.)
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).
Grr, proofreading failure “they increase so long as the product is > 1”.
My gut tells me there is a simple constructive / inductive proof that uses Pascal’s Triangle…
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.
It is not clear that why should a log-concave function have a unique maximum.
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.
Here’s a proof of the first statement, that the binomial coefficients are concave unimodal.
First, C(n, k) = C(n, n – k) (easy by the factorial definition, or by a simple combinatorial argument). This means that one only needs to show that C(n, k) is increasing for k = 1…n//2 (n fixed).
C(n, k + 1) = C(n, k)(n – k)/(k + 1). This also follows from the factorial definition, or combinatorially: for every way to choose k items from n, we can chose an additional item from the n – k remaining items, that is C(n, k)*(n – k). However, this over counts, because each choice of k + 1 items can be obtained in this way by appending 1 item to the other k in k ways (k ways to choose k items from the k + 1 to append to). Hence we divide by k + 1.
n > 2k, so k + 1 (n – k)/(n/2 + 1). If k + 1 < n/2, then k – n n/2 + 1. Hence, (n – k)/(k + 1) > 1, so the function is increasing.