In a sequence, $x_1=\frac{1}{2}$ and $x_{n+1}=1-x_1x_2x_3...x_n$ for $n\ge 1$. Prove that $0.99<x_{100}<0.991$. Fresh translation. This problem may be similar to one of the 9th grade problems.
Problem
Source: St Petersburg 2008 10th grade #7
Tags: inequalities, inequalities proposed
mavropnevma
29.07.2011 11:27
It is precisely you that posted this http://www.artofproblemsolving.com/Forum/viewtopic.php?f=52&t=419804&p=2370424#p2370424. I had made the observation that the statement was incorrect. Now you just add to the estimation of the result. Was it not more accurate to revisit your old post, correct its statement, and ask the extra precision over there, in the context of the already received solutions? Not to mention this hardly is proper for the Inequality forum. People - let's enforce some well-needed hygiene ...
Pathological
27.05.2019 02:42
Let $a_{i+1} = 1-x_{i+1} = x_1x_2 \cdots x_i$ for $i \in \mathbb{N}.$ Then, we have that $a_1 = \frac12$, and for $n \ge 1$ we have that $a_{n+1} = x_1x_2 \cdots x_{n+1} = x_1x_2 \cdots x_n (1-x_1x_2 \cdots x_n) = a_n(1-a_n).$ We wish to show that $a_{100} \in (0.009, 0.01).$ It's easy to see by induction that $a_i < \frac1i$. Indeed, $a_n < \frac1n \Rightarrow a_{n+1} = a_n (1-a_n) \le \frac1n (1 - \frac1n) = \frac{n-1}{n^2} < \frac{1}{n+1}$ for $n \ge 2,$ and it's clear that $a_1 < \frac11$, $a_2 < \frac12$. This establishes that $a_{100} < \frac{1}{100} = 0.01.$
Now, we will tackle the $0.009$ part of the problem. Let $y_n = \frac1n - a_n.$ Then, we have that $y_1 = \frac12, y_2 = \frac14, y_3 = \frac{7}{48}, \cdots$ is defined by $y_{n+1} = \frac{1}{n+1} - (\frac1n - y_n) (1 + y_n - \frac1n) = \frac{1}{n^2(n+1)} + \frac{n-2}{n} y_n + y_n^2.$ The following lemma is the key.
Lemma. $y_t < \frac{1}{t \sqrt{t}} \forall t \in \mathbb{N}.$
Proof. We will prove it by induction on $t$. For $t \le 9$, it's easily verified by simply using the recursion and doing some calculations. Suppose that it holds for $t = n$, where $n \ge 9.$ When $t=n+1$, we have that
$$y_{n+1} \le \frac{1}{n^2(n+1)} + \frac{n-2}{n} \cdot \frac{1}{n\sqrt{n}} + \frac{1}{n^3}.$$Letting $a = \sqrt{n}$, we have that:
$$\frac{1}{(n+1)(a+\frac{1}{2a})} < \frac{1}{(n+1)\sqrt{n+1}},$$so it suffices to prove that
$$\frac{1}{n^2(n+1)} + \frac{n-2}{n} \cdot \frac{1}{n\sqrt{n}} + \frac{1}{n^3} \le \frac{1}{(n+1)(a + \frac{1}{2a})}.$$Rewriting this in terms of $a$, expanding, and then simplifying, we get that this is equivalent to:
$$a^5 - 4a^4 + 5a^3 - 5a^2 + 2a-1 \ge 0.$$This rewrites as
$$a^3(1 + (a-2)^2) - 4a^2 + 2a - 1 \ge 0,$$so since $a^3(1+(a-2)^2) - 4a^2 \ge 2a^3 - 4a^2 \ge 0$ (as $a \ge 3$) and $2a -1 \ge 0$ (as $a \ge 3$), we're done.
$\blacksquare$
By the lemma, we have that $a_{100} = 0.01 - y_{100} > 0.01 - \frac{1}{100 \sqrt{100}} = 0.009,$ and so we're done.
$\square$