IMO 1997 SL 26

Origin: ITA

Problem

For every integer n \geq2 determine the minimum value that the sum a0 + a1 + \cdot \cdot \cdot + an can take for nonnegative numbers a0, a1, . . . , an satisfying the condition a0 = 1, ai \leqai+1 + ai+2 for i = 0, . . . , n −2.

Solution

Let us first examine the case that all the inequalities in the problem are actually equalities. Then an−2 = an−1 + an, an−3 = 2an−1 + an, . . . , a0 = Fnan−1 + Fn−1an = 1, where Fn is the nth Fibonacci number. Then it is easy to see (from F1 + F2 + \cdot \cdot \cdot + Fk = Fk+2) that a0 + \cdot \cdot \cdot + an = (Fn+2 −1)an−1 + Fn+1an = Fn+2−1 Fn +  Fn+1 −Fn−1(Fn+2−1) Fn

an. Since Fn−1(Fn+2−1) Fn \leqFn+1, it follows that a0 + a1 + \cdot \cdot \cdot + an \geqFn+2−1 Fn , with equality holding if and only if an = 0 and an−1 = Fn . We denote by Mn the required minimum in the general case. We shall prove by induction that Mn = Fn+2−1 Fn . For M1 = 1 and M2 = 2 it is easy to show that the formula holds; hence the inductive basis is true. Suppose that n > 2. The sequences 1, a2 a1 , . . . , an a1 and 1, a3 a2 , . . . , an a2 also satisfy the conditions of the problem. Hence we have a0 + \cdot \cdot \cdot + an = a0 + a1  1 + a2 a1

• \cdot \cdot \cdot + an a1  \geq1 + a1Mn−1 and a0 + \cdot \cdot \cdot + an = a0 + a1 + a2  1 + a3 a2
• \cdot \cdot \cdot + an a2  \geq1 + a1 + a2Mn−2. Multiplying the first inequality by Mn−2 −1 and the second one by Mn−1, adding the inequalities and using that a1 + a2 \geq1, we obtain (Mn−1 + Mn−2 + 1)(a0 + \cdot \cdot \cdot + an) \geqMn−1Mn−2 + Mn−1 + Mn−2 + 1, so Mn \geqMn−1Mn−2 + Mn−1 + Mn−2 + 1 Mn−1 + Mn−2 + 1 . Since Mn−1 = Fn+1−1 Fn−1 and Mn−2 = Fn−1 Fn−2 , the above inequality easily yields Mn \geqFn+2−1 Fn . However, we have shown above that equality can occur; hence Fn+2−1 Fn is indeed the required minimum.