IMO 1976 SL 2

Origin: BUL

Problem

Let a0, a1, . . . , an, an+1 be a sequence of real numbers satisfying the following conditions: a0 = an+1 = 0, |ak−1 −2ak + ak+1| \leq1 (k = 1, 2, . . ., n). Prove that |ak| \leqk(n+1−k) (k = 0, 1, . . ., n + 1).

Solution

Let us put bi = i(n + 1 −i)/2, and let ci = ai −bi, i = 0, 1, . . ., n+ 1. It is easy to verify that b0 = bn+1 = 0 and bi−1 −2bi + bi+1 = −1. Subtracting this inequality from ai−1−2ai+ai+1 \geq−1, we obtain ci−1−2ci+ci+1 \geq0, i.e., 2ci \leqci−1 + ci+1. We also have c0 = cn+1 = 0. Suppose that there exists i \in{1, . . . , n} for which ci > 0, and let ck be the maximal such ci. Assuming w.l.o.g. that ck−1 < ck, we obtain ck−1 + ck+1 < 2ck, which is a contradiction. Hence ci \leq0 for all i; i.e., ai \leqbi. Similarly, considering the sequence c′ i = ai + bi one can show that c′ i \geq0, i.e., ai \geq−bi for all i. This completes the proof.