47th Putnam 1986 Problem A6 Let p(x) be the real polynomial 1 + α 1 x m 1 + α 2 x m 2 + ... + α n x m n , where 0 < m 1 < m 2 < ... < m n . For some real polynomial q(x) we have p(x) = (1 - x) n q(x). Find q(1) in terms of m 1 , ... , m n . Solution
: m 1 m 2 ...m n /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 m i . 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 m 1 (m 1 - 1) ... (m 1 - r + 1). The traditional notation is Pochhammer's symbol (m 1 ) r , but Graham et al are pushing m 1 r (read as m 1 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; m 1 1 α 1 + m 2 1 α 2 + ... + m n 1 α n = 0; m 1 2 α 1 + m 2 2 α 2 + ... + m n 2 α n = 0; . . . m 1 n-1 α 1 + m 2 n-1 α 2 + ... + m n n-1 α n = 0; The above n equations determine the α i , and we then substitute them into: m 1 n α 1 + m 2 n α 2 + ... + m n n α n = (-1) n n! q(1); (*) Let D be the n x n determinant with first row 1, 1, ... ,1; and ith row m 1 i-1 , m 2 i-1 , ... , m n i-1 ; etc) for i > 1. Let D i 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 = D i /D. (**) It is also convenient to define E as the determinant derived from D by replacing the first row by m 1 n , m 2 n , ... , m n n and F as the determinant derived from D by deleting its first row and adding m 1 n , m 2 n , ... , m n n as a new bottom row. Note that E = (-1) n-1 F 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 D i is all zeros except for -1 in the first row, its value is just -D 1i , where D 1i is the cofactor of the (1, i) element of D [D 1i 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: -(m 1 n D 11 + m 2 n D 12 + ... + m n n D 1n ) / 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. m k is a polynomial in m with highest term m k and no constant term m 0 (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 m i k replaced by m i k . 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 m i k by m i k . Now observe that every element in column i of W has a factor m i . We can take out these factors to get that W = m 1 m 2 ... m n V. Hence result. 47th Putnam 1986 © John Scholes jscholes@kalva.demon.co.uk 3 Oct 1999