47th Putnam 1986

Let p(x) be the real polynomial 1 + α₁x^m₁ + α₂x^m₂ + ... + α_nx^m_n, where 0 < m₁ < m₂ < ... < m_n. For some real polynomial q(x) we have p(x) = (1 - x)ⁿq(x). Find q(1) in terms of m₁, ... , m_n.

Solution

Answer: m₁m₂...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)ⁿ 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⁽ⁿ⁾(1) = (-1)ⁿ n! q(1). So having solved for the α_i we just have to substitute them into p⁽ⁿ⁾(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₁(m₁ - 1) ... (m₁ - r + 1). The traditional notation is Pochhammer's symbol (m₁)_r, but Graham et al are pushing m₁^r (read as m₁ 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:

  α₁ + α₂ + ... + α_n = -1;
  m₁¹ α₁ + m₂¹ α₂ + ... + m_n¹ α_n = 0;
  m₁² α₁ + m₂² α₂ + ... + m_n² α_n = 0;
  . . .
  m₁^n-1 α₁ + m₂^n-1 α₂ + ... + m_n^n-1 α_n = 0;

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

  m₁ⁿ α₁ + m₂ⁿ α₂ + ... + m_nⁿ α_n = (-1)ⁿ n! q(1);   (*)

Let D be the n x n determinant with first row 1, 1, ... ,1; and ith row m₁^i-1, m₂^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₁ⁿ, m₂ⁿ, ... , m_nⁿ and F as the determinant derived from D by deleting its first row and adding m₁ⁿ, m₂ⁿ, ... , m_nⁿ 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 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)¹⁺ⁱ 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₁ⁿ D₁₁ + m₂ⁿ D₁₂ + ... + m_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⁰ (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₁m₂ ... m_n V. Hence result.

47th Putnam 1986

© John Scholes
jscholes@kalva.demon.co.uk
3 Oct 1999