The numbers $x_1,...x_{100}$ are written on a board so that $ x_1=\frac{1}{2}$ and for every $n$ from $1$ to $99$, $x_{n+1}=1-x_1x_2x_3*...*x_{100}$. Prove that $x_{100}>0.99$.
Problem
Source:
Tags: induction, inequalities proposed, inequalities
23.07.2011 11:22
I assume it is meant $x_{n+1}=1-x_1x_2x_3*...*x_{n}$, otherwise all but first are equal, to $\approx \frac {1} {2}$.
23.07.2011 12:34
3333 wrote: The numbers $x_1,...x_{100}$ are written on a board so that $ x_1=\frac{1}{2}$ and for every $n$ from $1$ to $99$, $\color{red}{x_{n+1}=1-x_1x_2x_3\cdots x_{n}}$. Prove that $x_{100}>0.99$. For each and every $n,$ we have that $x_n>\frac{n-1}{n}.$ So, assume that there existed a certain $n\in\{1,\cdots,100\}$ such that $x_n\leq \frac{n-1}{n}.$ This would have forced \[1-x_1\cdots x_{n-1}\leq 1-\frac 1n\implies x_1x_2\cdots x_{n-1}\geq\frac 1n.\] This further forces \[x_1\cdots x_{n-2}\left(1-x_1\cdots x_{n-2}\right)\ge \frac 1n\implies nk^2-nk+1\leq 0;\] \[\implies \frac 1{n-1}\leq \frac12\left(1-\sqrt{\frac{n-4}{n}}\right)\le x_1\cdots x_{n-2}\le \frac 12\left(1+\sqrt{\frac{n-4}{n}}\right)\] Continuing this way, we can reach $n=4.$ Then we would have obtained $x_1x_2x_3x_4\geq \frac 15.$ But, $x_1=\frac 12, x_2=\frac 12, x_3=\frac 34, x_4=\frac{13}{16},\implies x_1x_2x_3x_4=\frac{39}{256}<\frac 15;$ a contradiction. So, we are done. $\Box$
24.07.2011 13:10
3333 wrote: The numbers $x_1,...x_{100}$ are written on a board so that $ x_1=\frac{1}{2}$ and for every $n$ from $1$ to $99$, $x_{n+1}=1-x_1x_2x_3*...*x_{n}$. Prove that $x_{100}>0.99$. Let me post my proof,I dedicate this proof to Potla First,I will show $ \sum_{n=1}^{99}{\frac{1}{x_{n}}}\geq 98 $ because by AM-GM.we have \[ \sum_{n=1}^{99}{\frac{1}{x_{n}}}\geq \frac{99^{2}}{99-(x_{1}+x_{1}x_{2}+\cdots+x_{1}x_{2}\cdots x_{98})}\geq 99 >98 \] Then,I show $ x_{100}>\frac{99}{100}=0.99 $, We notice that \[ x_{n+1}=1-x_{n}+x_{n}^{2} \] which can be rewrite into: \[ \frac{1}{x_{n}}=\frac{1}{x_{n}-1}-\frac{1}{x_{n+1}-1} \] sum it from $ 1$ to $99 $,we get \[ \sum_{n=1}^{99}{\frac{1}{x_{n}}}+2=\frac{1}{1-x_{100}} \] then\[ \frac{1}{1-x_{100}} >98+2=100 \] Which give that$ x_{100}>0.99 $ Done!
25.07.2011 11:47
3333 wrote: The numbers $x_1,...x_{100}$ are written on a board so that $ x_1=\frac{1}{2}$ and for every $n$ from $1$ to $99$, $x_{n+1}=1-x_1x_2x_3*...*x_{100}$. Prove that $x_{100}>0.99$. More Stronger The recursiong can be rewrite as $x_{n+1} = x_n^2 - x_n + 1$ that is not difficult to prove that for all $n$ having $x_n < 1$ so we let $b_i = 1 - x_i$ and $b_1 = \frac{1}{2}$ and the recusiong be \[b_{n+1} = b_n - b_{n+1}^2 \] and that was not difficult to prove that $b_{i+1} < b_i$ and $b_i > 0$ so $b_{n+1} = b_n - b_{n+1}^2 < b_n - b_{n+1}b_n$ $\iff \frac{1}{b_{n+1}} - \frac{1}{b_n} > 1$ $\iff b_{n} < \frac{1}{n+1}$ and that was easy know that $x_n = 1 - b_n > 1 - \frac{1}{n+1} = \frac{n}{n+1}$ so $x_{100} > \frac{100}{101} > \frac{99}{100}$ as we known
09.10.2011 08:22
Potla wrote: 3333 wrote: The numbers $x_1,...x_{100}$ are written on a board so that $ x_1=\frac{1}{2}$ and for every $n$ from $1$ to $99$, $\color{red}{x_{n+1}=1-x_1x_2x_3\cdots x_{n}}$. Prove that $x_{100}>0.99$. For each and every $n,$ we have that $x_n>\frac{n-1}{n}.$ So, assume that there existed a certain $n\in\{1,\cdots,100\}$ such that $x_n\leq \frac{n-1}{n}.$ This would have forced \[1-x_1\cdots x_{n-1}\leq 1-\frac 1n\implies x_1x_2\cdots x_{n-1}\geq\frac 1n.\] This further forces \[x_1\cdots x_{n-2}\left(1-x_1\cdots x_{n-2}\right)\ge \frac 1n\implies nk^2-nk+1\leq 0;\] \[\implies \frac 1{n-1}\leq \frac12\left(1-\sqrt{\frac{n-4}{n}}\right)\le x_1\cdots x_{n-2}\le \frac 12\left(1+\sqrt{\frac{n-4}{n}}\right)\] Continuing this way, we can reach $n=4.$ Then we would have obtained $x_1x_2x_3x_4\geq \frac 15.$ But, $x_1=\frac 12, x_2=\frac 12, x_3=\frac 34, x_4=\frac{13}{16},\implies x_1x_2x_3x_4=\frac{39}{256}<\frac 15;$ a contradiction. So, we are done. $\Box$ it's easy to prove by a stronger induction that$x_n\ge 1-\frac{1}{n}$.a casual use of contradictory methods is not very good,and can sometimes lead to chaos
12.06.2018 16:07
Extension: Prove that $x_{95}>0.99$