38th IMO 1997 shortlist Problem 26 Find the minimum value of x 0 + x 1 + ... + x n for non-negative real numbers x i such that x 0 = 1 and x i ≤ x i+1 + x i+2 .
(F n+2 - 1)/F n Solution Define the Fibonacci numbers as usual by F 0 = 0, F 1 = 1, F n+2 = F n+1 + F n . We show first that F 1 + F 2 + ... + F n = F n+2 - 1. This is true for n = 1, since F 3 = 2. Suppose it is true for n, then F 1 + ... + F n+1 = F n+1 + F n+2 - 1 = F n+3 - 1, so it is true for n+1. Now put y i = x i - F n-i /F n . That gives y 0 = 0, y n = x n ≥ 0 (and we do not care about y n+1 , y n+2 etc). Also y i+1 + y i+2 = x i+1 + x i+2 - (F n-i-1 + F n-i-2 )/F n ≥ x i - F n-i /F n = y i . We claim that y 0 = 0, y n ≥ 0, y i+1 + y i+2 ≥ y i implies y 0 + y 1 + ... + y n ≥ 0. We use induction on n. It is obvious for n=1. Suppose it is true for <n. If y n-1 and y n-2 are both negative, then y n-3 ≤ y n-2 + y n-1 must also be negative, so continuing, y 0 is negative. Contradiction. So at least one of y n-1 , y n-2 must be non-negative. If y n-1 ≥ 0, then by induction y 0 + ... + y n-1 ≥ 0. But y n ≥ 0, so y 0 + ... + y n ≥ 0. So suppose y n-1 < 0. Then y n-2 ≥ 0. Hence by induction y 0 + y 2 + ... + y n-2 ≥ 0. But also y n-1 + y n ≥ y n-2 ≥ 0, so adding y 0 + ... + y n ≥ 0. So the result is true for all n. But x 0 + x 2 + ... + x n = y 0 + ... + y n + (F 0 + ... + F n )/F n ≥ (F 0 + ... + F n )/F n = (F n+2 - 1)/F n . Thanks to Kamil Duszenko 38th IMO shortlist 1997 © John Scholes jscholes@kalva.demon.co.uk 2 Dec 2003 Last corrected/updated 2 Dec 2003