47th Putnam 1986

Problem A6

Let p(x) be the real polynomial 1 + α1xm1 + α2xm2 + ... + αnxmn, where 0 < m1 < m2 < ... < mn. For some real polynomial q(x) we have p(x) = (1 - x)nq(x). Find q(1) in terms of m1, ... , mn.



Answer: m1m2...mn/n!

Moderately hard, unless you are used to manipulating determinants.

Notice that n occurs in two places: p(x) has n terms apart from 1, and it also has an n-fold root x = 1. The first key (but elementary) point is the fact that p(x) has a factor (1 - x)n iff p(1) = p'(1) = ... = p(n-1)(1) = 0. This gives us n linear equations for the n variables αi, so the αi are completely determined in terms of the mi. Moreover, differentiating p(x) one more time (n in all) gives p(n)(1) = (-1)n n! q(1). So having solved for the αi we just have to substitute them into p(n)(1) to get the answer. That is all straightforward, the only difficulty of the question is actually carrying out that programme. If you are not familiar with determinants, it can seem sufficiently intimidating to make you give up and try another approach.

It is convenient to have some notation for m1(m1 - 1) ... (m1 - r + 1). The traditional notation is Pochhammer's symbol (m1)r, but Graham et al are pushing m1r (read as m1 to the r falling) [see Ronald Graham, Donald Knuth, Oren Patashnik, Concrete Mathematics, 2nd Ed 1994, Addison-Wesley, ISBN 0201558025, especially section 2.6 Finite Calculus], which I also prefer. So, we have:

  α1 + α2 + ... + αn = -1;
  m11 α1 + m21 α2 + ... + mn1 αn = 0;
  m12 α1 + m22 α2 + ... + mn2 αn = 0;
  . . .
  m1n-1 α1 + m2n-1 α2 + ... + mnn-1 αn = 0;

The above n equations determine the αi, and we then substitute them into:

  m1n α1 + m2n α2 + ... + mnn αn = (-1)n n! q(1);   (*)

Let D be the n x n determinant with first row 1, 1, ... ,1; and ith row m1i-1, m2i-1, ... , mni-1; etc) for i > 1. Let Di be the determinant derived from D by replacing the ith column by the values on the other side of the n simultaneous equations (-1 in the top row and 0s below). [Sorry, that is hard to typeset in the type of HTML that browsers currently accept]. Then we know that αi = Di/D. (**)

It is also convenient to define E as the determinant derived from D by replacing the first row by m1n, m2n, ... , mnn and F as the determinant derived from D by deleting its first row and adding m1n, m2n, ... , mnn as a new bottom row. Note that E = (-1)n-1F since it is derived from it by n-1 row transpositions.

Having got the solution (**) we just substitute the values into (*). But notice that because the ith column of Di is all zeros except for -1 in the first row, its value is just -D1i, where D1i is the cofactor of the (1, i) element of D [D1i is (-1)1+i times the value of the (n-1) x (n-1) determinant obtained from D by deleting the 1st row and ith column]. So the left hand side of (*) is just: -(m1n D11 + m2n D12 + ... + mnn D1n) / D. But the expression in parentheses is just the expansion of the determinant E, so (remembering that E = (-1)n-1 F) we get that q(1) n! = F/D.

mk is a polynomial in m with highest term mk and no constant term m0 (unless i > m, in which case it is zero). So by adding multiples of rows 2, 3, ... , (k - 1) to row k successively for k = 2, 3, ... , n we can convert D into the Vandermonde determinant V which has mik replaced by mik. Since such row operations do not change the value of a determinant, we have D = V. Similarly, F = W, the determinant derived from F by replacing mik by mik. Now observe that every element in column i of W has a factor mi. We can take out these factors to get that W = m1m2 ... mn V. Hence result.



47th Putnam 1986

© John Scholes
3 Oct 1999