Problema 6 de la OMI 1985

Question

Para cada número real $x_1$ construir la secuencia de $x_1,x_2,x_3,\ldots$ mediante el establecimiento $x_{n+1}=x_n(x_n+\frac{1}{n})$ por cada $n \ge 1$. Demostrar que existe exactamente un valor de $x_1$ que $0 < x_n < x_{n+1} < 1$ por cada $n$.

Answer 1

Se supone que hay algunos $x_1$ tal que $0<x_n<x_{n+1}<1$ $\{x_n\}$ es monótona creciente y acotada. Por lo tanto converge por la monotonía teorema de convergencia.

Deje $\lim\limits_{n\rightarrow \infty}{x_n}=l$, a continuación, obtenga $l^2=l \Rightarrow l=0,1$, podemos fácilmente omitir $0$ y, por tanto,$x_n\rightarrow 1$.

---

La prueba de la unicidad de $x_1$.

Asumen para el primer periodo $x_1$$a_1$, la secuencia de $\{x_n\}$ $\{a_n\}$ converge. Sin pérdida de generalidad supongamos $x_1>a_1$(Recordemos que la definición de los estados de que todos los términos de la secuencia son positivos). El uso de la inducción, podemos demostrar que $x_n>a_n \quad\forall n\in \mathbb{N}$.

Como $x_n$ $a_n$ tanto converge a $1$, no sale de una $N$ tal que para todos los $n\ge N\implies \frac{3}{4}<a_n<x_n<1 $ (Tome $\varepsilon=\frac{1}{4}$)

Observar que $$x_{n+1}-a_{n+1}=\left(x_n-a_n\right)\left(x_n+a_n\right)+\frac{1}{n}\left(x_n-a_n\right)>\frac{3}{2}(x_n-a_n)$$

Por lo tanto $$\begin{array}{rcl}\frac{x_{n+1}-a_{n+1}}{x_n-a_n}&>&\frac{3}{2}\implies\\ x_{n+1}-a_{n+1}&>&\left(\frac{3}{2}\right)^{n+1-N}\cdot(x_N-a_N) \\ \end{array}$$

La divergencia de $x_n-a_n$ es clara. Una contradicción.

---

Para demostrar la existencia, denotan $f_{1}(x)=x$$f_{n+1}(x)=f_{n}(x)\left(f_{n}(x)+\frac{1}{n}\right)$. El uso de la inducción demostrar que $f_{n}(x)$ es estrictamente creciente de la función en $x$.

Vamos $b_n$, $c_n$ ser tal que $f_{n}(b_n)=1-\frac{1}{n}$$f_{n}(c_n)=1$, la existencia y unicidad de $b_n$, $c_n$ sigue a partir de la monotonía de $f_n$, las observaciones $f_{n}(0)=0$, $f_{n}(1)>1$ y la continuidad de la $f_{n}$. También se observa que el $b_n<c_n$ y el uso de la inducción que $b_n$ es estrictamente creciente y $c_n$ es estrictamente decreciente secuencias.

El conjunto $A=\{b_n\}$ está delimitado por encima. Por lo tanto, por lo menos límite superior de la propiedad de $\mathbb{R}$ existe un $\gamma =\sup \{b_n\}$. Demostraremos que los $\gamma$ es de hecho nuestro $x_1$!

$$\color{blue}{f_{n+1}{(\gamma)}}=f_{n}(\gamma)\left(f_n{(\gamma)}+\frac{1}{n}\right)\color{blue}{>}f_{n}(\gamma)\left(f_{n}(b_n)+\frac{1}{n}\right)=\color{blue}{f_{n}(\gamma)>0}\\ \color{blue}{1}=f_{n} c_{n})\color{blue}{>f_{n}(\gamma)} \quad \forall n \implica \\ 1>f_{n+1}{(\gamma)}>f_{n}(\gamma)>0 \qquad \square$$

---

Pruebas de interés

$f_n(x)$ no ha entero negativo de los coeficientes de ahí $f_n(x)$ es estrictamente creciente en a $[0,1]$.

Observe que $\color{blue}{f_{n+1}(b_n)}=f_{n}(b_n)\left(f_{n}(b_n)+\frac{1}{n}\right)=1-\frac{1}{n}\color{blue}{<}1-\frac{1}{n+1}=\color{blue}{f_{n+1}(b_{n+1})} \implies b_n< b_{n+1}$ o $b_n$ es estrictamente creciente de la secuencia.

Observe que $\color{blue}{f_{n+1}(c_n)}=f_{n}(c_n)\left(f_{n}(c_n)+\frac{1}{n}\right)=1+\frac{1}{n}\color{blue}{>}1=\color{blue}{f_{n+1}(c_{n+1})} \implies c_{n+1}<c_n$ o $c_n$ es estrictamente decreciente de la secuencia.

El hecho de que $b_n$ está delimitado, es claro como la $b_n<c_1 \quad \forall n$.

Answer 2

Esta no es una respuesta, sino más bien una (demasiado largo) comentario en respuesta a la respuesta apropiada por boywholived. Seguro, existe exactamente un valor de $x_1$, pero el comentario barak manos sigue en pie: cualquier posibilidad de que usted nos puede decir lo que el valor de $x_1$ es? Aquí es un pequeño programa informático que realiza el trabajo:

programa de IMO_1985;

procedimiento encontrar;
const
 GRANDE : integer = 50;
var
 n,i : integer;
 x,x_1,bits : doble;
 H,L : boolean;
comenzar
{ Inicializar }
 x_1 := 1/2;
 bits := 1/2;
 for i := 0 para hacer GRANDES
comenzar
 n := 1;
 H := true;
 L := true;
 { Writeln(n:2,' : ',x_1); }
 x := x_1;
 mientras que el verdadero ¿
comenzar
 x := x*(x+1/n);
 { Writeln((n+1):2,' : ',x); }
 { Disminuyendo hacia cero: }
 L := (x < 1-1/n);
 { Explosión hacia el infinito: }
 H := (x > 1);
 si H o L, a continuación, Break;
 n := n+1;
end;
 { Readln; }
 { Encontrar x_1 poco a poco: }
 bits := bit/2;
 si H, entonces x_1 := x_1 bits;
 si L, a continuación, x_1 := x_1 + bit;
end;
Writeln(x_1:0:16);
end;

comenzar
encontrar;
final.

El programa utiliza un par de fácil demostrar afirmaciones acerca de la secuencia:

• Si la secuencia de $x_n$ es decreciente para un cierto valor de $n$ ( $x_{n+1} < x_n$ ) entonces permanecerán así hasta que se llega a un límite, que es cero.
• La secuencia es decreciente si y sólo si $x_n < 1-1/n$ . Debido a la declaración anterior, se puede poner una Pausa en los cálculos entonces. Y a la conclusión de que nuestra estimación del valor inicial $x_1$ debe haber sido mayor (un bit).
• Si algún valor de $x_n$ es mayor que $1$, a continuación, la secuencia de será el aumento de siempre (es decir, de que explote). Se puede poner una Pausa en los cálculos. Y a la conclusión de que nuestra estimación de la inicial valor $x_1$ debe haber sido menor (un bit).

Resulta que la convergencia de la secuencia hacia la deseada límite de $\;x_n \to 1\;$ es extremadamente inestable numéricamente. Así que lo que en realidad tiene un interruptor entre el $\,0\,$ $\,\infty\,$ que genera el resultado para $x_1$ poco a poco, hasta que doble de precisión que se alcanza.
Ahora casi me olvidé de decirte lo que el resultado es: $$ x_1 \aprox 0.4465349172642295 $$ Inversa método. Si un método es (numéricamente) inestable, a continuación, intente la inversa. Porque no es raro que el último será estable, a continuación,. Así que vamos a solucionar $x_n \ge 0$$x_{n+1} = x_n(x_n+1/n)$: $$ x_n^2 + \frac{1}{n} x_n - x_{n+1} = 0 \quad \Longrightarrow \quad x_n = -\frac{1}{2n}+\sqrt{\left(\frac{1}{2n}\right)^2+x_{n+1}} = \frac{x_{n+1}}{\frac{1}{2n}+\sqrt{\left(\frac{1}{2n}\right)^2+x_{n+1}}} $$ El último truco es por razones de estabilidad numérica así. Ahora a empezar con algo de GRAN valor de $n$ y poner $x_{n+1}=1-1/(n+1)$. Luego de recorrer hacia atrás hasta que $x_1$ es alcanzado. La resultante (Pascal) programa ha sido de casi un one-liner (es decir, sin el Análisis de Errores):

programa de IMO_1985;

procedimiento encontrar;
const
 GRANDE : integer = 50;
var
 n : integer;
 x,E : Extended;
comenzar
{ Inicializar }
 x := 1-1/(GRANDE+1);
 E := 1/(GRANDE+1);
 para n := GRANDE downto 1 do
comenzar
 x := x/(sqrt(1/sqr(2*n)+x)+1/(2*n));
 { Análisis De Errores: }
 E := E/(2*x+1/n);
end;
 Writeln('el Resultado x_1 = ',x:0:16);
 Writeln(' # decimales = ',-Trunc(ln(E)/ln(10)));
 Writeln('# buena bits = ',-Trunc(ln(E)/ln(2)));
end;

comenzar
encontrar;
final.

No hace falta decir que el resultado es el mismo que con el método anterior.

Análisis De Errores. Estimación con infinitesimals: $$ x_{n+1} = x_n(x_n+1/n) \quad \Longrightarrow \quad dx_{n+1} = (2x_n+1/n)dx_n $$ Inicializar con $\;dx_{n+1} = 1/(n+1)$ . De ello se sigue que: $$ dx_1 = \frac{dx_{n+1}}{(2x_1+1)(2x_2+1/2)(2x_3+1/3)\cdots(2x_n+1/n)} $$ El método Inverso programa ha sido modificado ligeramente para tomar esta en cuenta. La variable E se corresponde con los errores de $dx_n$ . Menos de 10 logaritmo del error $dx_1$ $x_1$ es el número de decimales, $16$ en nuestro caso, que de hecho parece estar bien. Menos el 2-logaritmo del error $dx_1$ $x_1$ es el número de bits significativos: $53$ . Este número, no en todos, por coincidencia (¿por qué?), está cerca del GRAN número de $=50$ en ambos programas.

La actualización. En realidad, nuestro valor $\,x_1\,$ así como el error de $\,dx_1\,$ son funciones de la $\,n$ , así que vamos a reemplazar $\,x_1\,$ $\,X(n)\,$ para todos finito de valores de$\,n\,$, y, asimismo,$\,dx_1\,$$\,\epsilon(n)$ : $$ \epsilon(n) = \frac{1/(n+1)}{(2x_1+1)(2x_2+1/2)(2x_3+1/3)\cdots(2x_n+1/n)} \quad \Longrightarrow \\ \epsilon(n) = \epsilon(n-1)\frac{n/(n+1)}{2x_n+1/n} $$ Con $\,1-1/n < x_n < 1\,$ tenemos $\,2-1/n < 2x_n+1/n < 2+1/n\,$ y el: $$ \epsilon(n) < \epsilon(n-1)\frac{1}{(1+1/n)(2-1/n)} = \frac{1}{2+1/n-1/n^2} < \frac{1}{2} \quad \Longrightarrow \quad \epsilon(n) < \epsilon(1)\left(\frac{1}{2}\right)^{n-1} $$ Para $\,n=1\,$ tenemos $\,1 < 2x_1+1 < 3\,$ por lo tanto $\,\epsilon(1) < 1/2$ . Esto demuestra una
Lema. (ver arriba: por eso!) : $$ \epsilon(n) < \left(\frac{1}{2}\right)^n $$ Nota. No estoy muy seguro de esto, porque $\,\epsilon(1)=dx_1=1/2\,$ no es un infinitesimal ( he.e lo suficientemente pequeño ) error; quizá $\,\epsilon(n)\,$ debe ser multiplicada por una constante adecuada?
Teorema. Como se esperaba: $$ \lim_{n\to\infty} X(n) = x_1 $$ Prueba. Para todos los verdaderos $\epsilon > 0$ existe un entero $N > 0$ de tal forma que si $n > N$$\left|X(n) - x_1\right| < \epsilon$ .
De hecho, definen $N$$\,N = \ln(1/\epsilon)/\ln(2)$, $\,\epsilon = (1/2)^N\,$ $n > N$ tenemos con el anterior Lema: $\,\left|X(n)-x_1\right| < (1/2)^n < \epsilon$ . Esto completa la prueba.
Descargo de responsabilidad: a pesar de que aparte de un par de tecnicismos quizás, véase la anterior Nota.