Find the minimum value of x0 + x1 + ... + xn for non-negative real numbers xi such that x0 = 1 and xi ≤ xi+1 + xi+2.
Answer
(Fn+2 - 1)/Fn
Solution
Define the Fibonacci numbers as usual by F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn. We show first that F1 + F2 + ... + Fn = Fn+2 - 1. This is true for n = 1, since F3 = 2. Suppose it is true for n, then F1 + ... + Fn+1 = Fn+1 + Fn+2 - 1 = Fn+3 - 1, so it is true for n+1.
Now put yi = xi - Fn-i/Fn. That gives y0 = 0, yn = xn ≥ 0 (and we do not care about yn+1, yn+2 etc). Also yi+1 + yi+2 = xi+1 + xi+2 - (Fn-i-1 + Fn-i-2)/Fn ≥ xi - Fn-i/Fn = yi. We claim that y0 = 0, yn &ge 0, yi+1 + yi+2 ≥ yi implies y0 + y1 + ... + yn ≥ 0. We use induction on n. It is obvious for n=1. Suppose it is true for <n. If yn-1 and yn-2 are both negative, then yn-3 ≤ yn-2 + yn-1 must also be negative, so continuing, y0 is negative. Contradiction. So at least one of yn-1, yn-2 must be non-negative. If yn-1 ≥ 0, then by induction y0 + ... + yn-1 ≥ 0. But yn ≥ 0, so y0 + ... + yn ≥ 0. So suppose yn-1 < 0. Then yn-2 ≥ 0. Hence by induction y0 + y2 + ... + yn-2 ≥ 0. But also yn-1 + yn ≥ yn-2 ≥ 0, so adding y0 + ... + yn ≥ 0. So the result is true for all n.
But x0 + x2 + ... + xn = y0 + ... + yn + (F0 + ... + Fn)/Fn ≥ (F0 + ... + Fn)/Fn = (Fn+2 - 1)/Fn.
Thanks to Kamil Duszenko
© John Scholes
jscholes@kalva.demon.co.uk
2 Dec 2003
Last corrected/updated 2 Dec 2003