The polynomials pn(x) are defined by p1(x) = 1 + x, p2(x) = 1 + 2x, p2n+1(x) = p2n(x) + (n + 1) x p2n-1(x), p2n+2(x) = p2n+1(x) + (n + 1) x p2n(x). Let an be the largest real root of pn(x). Prove that an is monotonic increasing and tends to zero.
It is fairly obvious that an < 0 and that the sequence is strictly monotonic increasing. The problem is proving it tends to zero.
Trivial inductions show that pn(0) = 1 and pn(x) > 0 for x > 0, so an < 0. Also we note that a1 = -1, a2 = -1/2. If x > an, then pn(x) > 0 (otherwise there would be a root greater than an).
p2n+1(a2n) = (n + 1) a2n p2n-1(a2n). By induction p2n-1(a2n) > 0, so p2n+1(a2n) < 0 and hence a2n+1 > a2n. Similarly a2n+2 > a2n+1. So, as claimed, an is strictly monotonic increasing.
To show it tends to zero, it suffices to prove that: a2n-1 > -1/(n-1) and a2n > -1/n. This is true for n = 1. Suppose it is true for n. We have already established monotonicity, so a2n+1 > -1/n. Also p2n-1(-1/(n+1)) > 0. But p2n+2(-1/(n+1)) = p2n+1(-1/(n+1)) - p2n(-1/(n+1)) = - p2n-1(-1/(n+1)) < 0, so a2n+2 > -1/(n+1) and we have established the inductive hypothesis for n+1.
39th Putnam 1978
© John Scholes
30 Nov 1999