Let $ \lfloor x \rfloor$ denote the greatest integer less than or equal to $ x.$ Pick any $ x_1$ in $ [0, 1)$ and define the sequence $ x_1, x_2, x_3, \ldots$ by $ x_{n+1} = 0$ if $ x_n = 0$ and $ x_{n+1} = \frac{1}{x_n} - \left \lfloor \frac{1}{x_n} \right \rfloor$ otherwise. Prove that \[ x_1 + x_2 + \ldots + x_n < \frac{F_1}{F_2} + \frac{F_2}{F_3} + \ldots + \frac{F_n}{F_{n+1}},\] where $ F_1 = F_2 = 1$ and $ F_{n+2} = F_{n+1} + F_n$ for $ n \geq 1.$
Problem
Source: IMO Shortlist 1992, Problem 18
Tags: floor function, algebra, Sequence, Fibonacci, Fibonacci sequence, Inequality, IMO Shortlist
19.08.2008 03:38
the sequence $ {x_i}$ satisfies 'off hand' criteria for "chaotic", in that it acts by stretching and folding. so $ {x_i}$ is just a collection of maybe not so random points in $ [0,1)$. on the RHS you may remember that $ \frac{F_{i+1}}{F_i} \approx \varphi = \frac{1+\sqrt{5}}{2}\approx 1.618$. with gross abuse of approximations we get $ x_1 + x_1 + \ldots + x_n \approx \frac{n}{2} < 0.618n \approx \frac{n}{\varphi} \approx \frac{F_1}{F_2} + \frac{F_2}{F_3} + \ldots + \frac{F_n}{F_{n+1}}$ certainly not a proof, but motivation(can be somewhat verified with programming). RHS looks usable, but LHS needs work.
26.11.2009 10:02
i will prove it by induction when $ n=1,2$, it is obvious. if $ x_1<=\frac{F_n} {F_{n+1}}$, then by induction, it is done. if $ x_1>\frac{F_n} {F_{n+1}}$, then since $ x_1=\frac{1} {a+x_2}<\frac{1} {1+x_2}$, hence $ x_2<\frac{F_{n-1}} {F_n}$. so $ x_1+x_2<\frac{1} {1+x_2}+x_2<\frac{F_n} {F_{n+1}}+\frac{F_{n-1}} {F_n}$. then we can use induction.
20.06.2019 00:09
Let $[a_0; a_1, a_2, \cdots, a_n, \cdots]$ be the continued fraction representation of $x_1$, in other words $$x_1 = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}},$$ where $a_0 = 0$ and $a_1, a_2, \cdots, a_n > 1.$ Then, in terms of continued fraction representations, we wish to prove that $[0; a_1, a_2, \cdots] + [0; a_2, a_3, \cdots] + [0; a_3, a_4, \cdots] + \cdots + [0, a_n, \cdots] < \frac{F_1}{F_2} + \frac{F_2}{F_3} + \cdots + \frac{F_n}{F_{n+1}}.$ Since we clearly have $[0; a_1, a_2, \cdots] < [0; a_1, a_2, \cdots, a_n], [0; a_2, a_3, \cdots] < [0; a_2, a_3, \cdots, a_n], \cdots$, we can just show that $$[0;a_1, a_2, \cdots a_n] + [0; a_2, a_3, \cdots, a_n] + \cdots + [0; a_n] \le \frac{F_1}{F_2} + \frac{F_2}{F_3} + \cdots + \frac{F_n}{F_{n+1}}.$$ Observe that the RHS is the same as the LHS when all $a_i$'s are one, and so let us just show that the LHS is maximized when all $a_i$'s are one. We will prove this via strong induction on $i$, with our hypothesis being that $a_1, a_2, \cdots, a_i$ must all be one in any "maximal" choice of $a_i$'s. For $i=1$, it is immediate, since $a_1$ has no influence on any of the terms but $[0; a_1, a_2, \cdots, a_n]$ and it's clear that $a_1 = 1$ maximizes $[0; a_1, \cdots, a_n].$ Let's now suppose that it holds for $i \le t.$ In this way, we have that $a_1 = a_2 = \cdots = a_t = 1.$ Let us show that $a_{t+1} = 1$ in any maximal configuration. Clearly, $a_{t+1}$ is independent of $[0; a_{t+2}, \cdots, a_n], [0, a_{t+3}, \cdots, a_n], \cdots$. Hence, we can let $q = [0; a_{t+2}, \cdots, a_n]$ and pick the optimal $a_{t+1}$ in these conditions. Viewing this as a function in terms of $x = a_{t+1}+q$, the relevant quantity (not including later stuff not influenced by $a_{t+1}$) is precisely: $$\frac{1}{x} + \sum_{j=1}^{t} \frac{F_jx + F_{j-1}}{F_{j+1}x + F_j}.$$ We now make the spectacular observation that: $$\frac{F_jx + F_{j-1}}{F_{j+1}x + F_j} = \frac{F_j}{F_{j+1}} + \frac{F_{j+1}F_{j-1} - F_j^2}{F_{j+1} (F_{j+1}x + F_j)},$$ and so hence if we plug this into the expression we actually just need to maximize: $$\frac1x + \sum_{j=1}^{t} \frac{(-1)^j}{F_{j+1} (F_{j+1}x + F_j)} = \frac{1}{x(x+1)} + \sum_{j=2}^{t} \frac{(-1)^j}{F_{j+1} (F_{j+1}x + F_j)}. \qquad (1)$$ Keeping in mind that $x$ is positive, it's obvious that any fraction of the form $\frac{\alpha}{\beta x^2 + \gamma x + \delta}$ is maximized when $x$ is minimized, and similarly for fractions of the form $\frac{\alpha}{\beta x + \gamma}$. Now, it just remains to partition the sum in $(1)$ into functions of these form. Indeed, $\frac{1}{x(x+1)}$ is of this form, and so is $\frac{1}{F_{j+1}(F_{j+1} x + F_j)} - \frac{1}{F_{j+2} (F_{j+2} x+ F_{j+1})}$ for any $j$ even. Finally, if $t$ is even, then we will need a final piece which is $\frac{1}{F_{t+1} (F_{t+1}x + F_t)},$ which is also maximized as $x$ is minimized. In conclusion, it's clear that $x$ should be minimized to maximize the sum in $(1)$, so since $x = a_{t+1} + q$, we have that $a_{t+1} = 1$ in any maximal choice of $a_i$'s. The induction is complete. $\square$