k lies in the open interval (1, 2). Show that the polynomial formed by expanding (x + y)n(x2 - k xy + y2) has positive coefficients for sufficiently large n. Find the smallest such n for k = 1.998.
The coefficient of xn-ryr+2 is ( nCr - k nCr+1 + nCr+2 ). We show that the worst case is r near n/2 and that even this is positive for sufficiently large n.
( nCr - k nCr+1 + nCr+2 ) = n!/(r+2! n-r!) ( (r+1)(r+2) - k(r+2)(n-r) + (n-r-1)(n-r) ). Let f(r) = ( (r+1)(r+2) - k(r+2)(n-r) + (n-r-1)(n-r) ). Then f '(r) = 2r+3 - kn +2kr + 2k - 2n + 2r + 1. So f '(r) = 0 iff (2k+4)r = (k+2)n - (2k+4) or r = n/2 - 1. Also it is clear that f '(r) is negative for smaller values and positive for larger values, so this represents a minimum. So if n = 2m the minimum occurs at r = m - 1 and is 2mCm-1 - k 2mCm + 2mCm+1. Now 2mCm-1 = 2mCm+1 = m/(m+1) 2mCm, so the minimum value is positive iff 2m/(m+1) > k which is certainly true for all sufficiently large m since k < 2.
Similarly if n = 2m+1, then the minimum occurs at r = m-1 or m. In either case, the minimum value is 2m+1Cm-1 - k 2m+1Cm + 2m+1Cm+1. But 2m+1Cm = 2m+1Cm+1 and 2m+1Cm-1 = m/(m+2) 2m+1Cm, so the minimum value is (m/(m+2) - (k-1) ) 2m+1Cm, which is certainly positive for all sufficiently large m since k-1 < 1.
We have 2m/(m+1) > 1.998 for m > 999, so the smallest even n with all coefficients positive is 2000. On the other hand, m/(m+2) > 0.998 for m > 998, so the smallest odd n with all coefficients positive is 1999. Thus the smallest n is 1999.
32nd Putnam 1971
© John Scholes
7 Feb 2001