APMO 93/3 solution

5th APMO 1993

Problem 3

p(x) = (x + a) q(x) is a real polynomial of degree n. The largest absolute value of the coefficients of p(x) is h and the largest absolute value of the coefficients of q(x) is k. Prove that k ≤ hn.

Solution

Let p(x) = p₀ + p₁x + ... + p_nxⁿ, q(x) = q₀ + q₁x + ... + q_n-1x^n-1, so h = max |p_i|, k = max |q_i|.

If a = 0, then the result is trivial. So assume a is non-zero. We have p_n = q_n-1, p_n-1 = q_n-2 + aq_n-1, p_n-2 = q_n-3 + aq_n-2, ... , p₁ = q₀ + aq₁, p₀ = aq₀.

We consider two cases. Suppose first that |a| ≥ 1. Then we show by induction that |q_i| ≤ (i+1) h. We have q₀ = p₀/a, so |q₀| ≤ h, which establishes the result for i = 0. Suppose it is true for i. We have q_i+1 = (p_i+1 - q_i)/a, so |q_i+1| ≤ |p_i+1| + |q_i| ≤ h + (i+1)h = (i+2)h, so it is true for i+1. Hence it is true for all i < n. So k ≤ max(h, 2h, ... , nh) = nh.

The remaining possibility is 0 < |a| < 1. In this case we show by induction that |q_n-i| ≤ ih. We have q_n-1 = p_n, so |q_n-1| ≤ |p_n| ≤ h, which establishes the result for i = 1. Suppose it is true for i. We have q_n-i-1 = p_n-i - aq_n-i, so |q_n-i-1n-i| + |q_n-i| ≤ h + ih = (i+1)h, so it is true for i+1. Hence it is true for all 1 ≤ i ≤ n. Hence k ≤ max(h, 2h, ... , nh) = nh.

5th APMO 1993