IMO 1985 SL 11

Problem

3a.(USS 3) Find a method by which one can compute the coefficients of P(x) = x6 + a1x5 + \cdot \cdot \cdot + a6 from the roots of P(x) = 0 by performing not more than 15 additions and 15 multiplications.

Solution

Let −x1, . . . , −x6 be the roots of the polynomial. Let sk,i (k \leqi \leq6) denote the sum of all products of k of the numbers x1, . . . , xi. By Vieta’s formula we have ak = sk,6 for k = 1, . . . , 6. Since sk,i = sk−1,i−1xi + sk,i−1, one can compute the ak by the following scheme (the horizontal and vertical arrows denote multiplications and additions respectively): x1 \tos2,2 \tos3,3 \tos4,4 \tos5,5 \toa6 ↓ ↓ ↓ ↓ ↓ s1,2 \tos2,3 \tos3,4 \tos4,5 \toa5 ↓ ↓ ↓ ↓ s1,3 \tos2,4 \tos3,5 \toa4 ↓ ↓ ↓ s1,4 \tos2,5 \toa3 ↓ ↓ s1,5 \toa2 ↓ a1