IMO 1983 SL 19

Origin: ROM

Problem

Let (Fn)n\geq1 be the Fibonacci sequence F1 = F2 = 1, Fn+2 = Fn+1 + Fn (n \geq1), and P(x) the polynomial of degree 990 satisfying P(k) = Fk, for k = 992, . . ., 1982. Prove that P(1983) = F1983 −1.

Solution

For all n, there exists a unique polynomial Pn of degree n such that Pn(k) = Fk for n + 2 \leqk \leq2n + 2 and Pn(2n + 3) = F2n+3 −1. For n = 0, we have F1 = F2 = 1, F3 = 2, P0 = 1. Now suppose that Pn−1 has been constructed and let Pn be the polynomial of degree n satisfying Pn(X + 2) −Pn(X + 1) = Pn−1(X) and Pn(n + 2) = Fn+2. (The mapping Rn[X] \toRn−1[X]\timesR, P "\to(Q, P(n+2)), where Q(X) = P(X + 2) −P(X + 1), is bijective, since it is injective and those two spaces have the same dimension; clearly deg Q = deg P −1.) Thus for n+2 \leqk \leq2n+2 we have Pn(k+1) = Pn(k)+Fk−1 and Pn(n+2) = Fn+2; hence by induction on k, Pn(k) = Fk for n + 2 \leqk \leq2n + 2 and Pn(2n + 3) = F2n+2 + Pn−1(2n + 1) = F2n+3 −1. Finally, P990 is exactly the polynomial P of the terms of the problem, for P990 −P has degree less than or equal to 990 and vanishes at the 991 points k = 992, . . ., 1982.