22 votos

¿El reemplazo recursivo de$\frac1n$ por$\frac1n(\frac12+\dots+\frac1{n+1})$ realmente converge a$\frac1e$?

Yo estaba pensando en un problema y tener una respuesta a través de la programación de la computadora, pero soy incapaz de demostrarlo matemáticamente. Empezar con la siguiente: $$\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg)\approx 0.41666$$ Reemplazar cada unidad de fracción concretarse en los paréntesis (en este caso, el interior de 1/2 y 1/3) $$\frac{1}{n}\bigg(\frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n+1}\bigg)$$ donde $n$ es el denominador de la unidad de fracción. Si aplicamos este proceso una vez, obtenemos $$\frac{1}{2}\bigg(\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg)+\frac{1}{3}\bigg(\frac{1}{2} + \frac{1}{3}+\frac{1}{4}\bigg)\bigg)\approx 0.3888$$ y si la aplicamos de nuevo, obtenemos $$\frac{1}{2}\bigg(\frac{1}{2}\bigg(\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg) + \frac{1}{3}\bigg(\frac{1}{2} + \frac{1}{3}+ \frac{1}{4}\bigg)\bigg)+\frac{1}{3}\bigg(\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg) + \frac{1}{3}\bigg(\frac{1}{2} + \frac{1}{3}+ \frac{1}{4}\bigg)+\frac{1}{4}\bigg(\frac{1}{2} + \frac{1}{3}+ \frac{1}{4}+ \frac{1}{5}\bigg)\bigg)\bigg)\approx 0.37754$$

Como repetimos este proceso, el resultado parece acercarse a $e^{-1}$.

Si alguien puede probar esto o me dirija a una prueba de ello, sería maravilloso!

15voto

Milo Brandt Puntos 23147

Considere el siguiente proceso aleatorio:

  • Comience con un número natural $n_0$.
  • Elegir un nuevo número de $n_1$ $\{2,3,\ldots,n_0+1\}$ uniformemente al azar.
  • Elegir un nuevo número de $n_2$ $\{2,3,\ldots,n_1+1\}$ uniformemente al azar.

y para repetir, sin embargo, muchos pasos. Su expresión es de ${\mathbb E}[1/n_k]$ - es decir, es el valor esperado de $1/{n_k}$. Este es un proceso de Markov y podemos aplicar nuestra típica de las herramientas de análisis de la misma*.

En particular, como $k$ aumenta, independientemente de nuestra posición de partida, la distribución de $n_k$ enfoques de un único estado estacionario de distribución, es decir, una distribución invariante bajo el paso.

Deje $p_m$ la probabilidad de que, para un gran $k$ (es decir, en el límite), tenemos $n_k=m$. Debe ser un estado estacionario en el sentido de que $$p_m=\sum_{\ell=m-1}^{\infty}\frac{1}{\ell}\cdot p_{\ell}$$ el que dice que, si empezamos en esta distribución, se quedaría en él.

Ahora, podemos construir una probabilidad de generación de función para el estado estacionario; vamos a trabajar la indexación ligeramente por conveniencia. Vamos a: $$f(x)=p_2x+p_3x^2+p_4x^3+\ldots.$$ Tenga en cuenta que podemos usar integración formal para obtener $$\int_0^x f(t)\,dt=\frac{p_2}2x^2+\frac{p_3}3x^3+\ldots$$ Luego, señalando $\frac{1}{1-x}=1+x+x^2+\ldots$ y el deslizamiento en un $x$ para la diversión, podemos definir una nueva función $g(x)$ como sigue: $$g(x)=\frac{x\int_0^x f(t)\,dt}{1-x}=\frac{p_2}2x^3+\left(\frac{p_2}2+\frac{p_3}3\right)x^4+\left(\frac{p_2}2+\frac{p_3}3+\frac{p_4}4\right)x^5+\ldots.$$ ¿Por qué hacer esto? Porque si dejamos $C=\frac{p_2}2+\frac{p_3}3+\ldots$ - que es, $C$ es exactamente la cantidad que estamos buscando - se nota que $$\frac{Cx}{1-x}-g(x)=\sum_{m=1}^{\infty}\sum_{\ell=m}^{\infty}\frac{1}{\ell}\cdot p_{\ell}\cdot x^m$$ Que reconocemos como $f(x)$. Por lo tanto, obtenemos una ecuación: $$(1-x)f(x)=Cx-x\int_0^x f(t)\,dt$$ Ahora, voy a dejar los detalles, porque yo no soy bueno en matemáticas, pero si usted diferenciar ambos lados de la ecuación dos veces, se obtiene un grado de dos ecuaciones diferenciales, y si usted lo enchufa en Mathematica, usted obtiene una solución: $$f(x)=c_1\cdot xe^x+c_2\cdot \frac{e+xe^x\operatorname{Ei}(x)}e$$ donde $c_1,c_2$ son todavía desconocidos constantes. Sin embargo, sabemos que $f(0)=0$ a partir de la definición de $f$ $f(1)=1$ desde $p_2+p_3+\ldots=1$ ya que estos son probabilidades. Esto corrige $c_2=0$$c_1=\frac{1}e$.

Por lo tanto $f(x)=\frac{1}exe^x$. Esto se ve prometedor ya! A continuación, se observa que la $\int_0^1 f(t)\,dt=C={\mathbb E}[1/n]$ con sólo mirar la serie se deriva de la anterior para la integral! Entonces, nos acaba de integrar la expresión y vemos a $C=1/e$. Hurra!! Funcionó! Como un bono, sabemos que en el estado estacionario las probabilidades son sólo $p_n=\frac{1}{e(n-2)!}$$2\leq n$.

(*Estoy ignorando la convergencia, que son relevantes ya que esta cadena de Markov tiene un número infinito de estados. La generación de la función de cosas puede ser justificado después de los hechos, a pesar de que implican graves problemas de convergencia - la unicidad de una solución no es tan difícil de establecer - el argumento habitual de la singularidad y de la existencia de un estado estacionario todavía nos da la unicidad de infinitos procesos de Markov y el hecho de que $f(x)=\frac{1}exe^x$ es una solución tampoco es demasiado difícil de demostrar. La convergencia de la cadena de su estado estacionario trae problemas más graves - creo que puede ser resuelto por la delimitación de la probabilidad de que $n_k$ es grande, que no debería ser demasiado difícil, ya que la probabilidad de que $n_{k+1}>n_k$ $n_k$ es sólo $\frac{1}{n_k}$)

3voto

Markus Scheuer Puntos 16133

Ofrecemos una relación de recurrencia para el número convergentes a $\frac{1}{e}$. Empezamos con algunos aspectos introductorios.

La representación a través de sumas

Denotamos los elementos de la secuencia que se forma iterativa generado por la OPs regla con $\alpha_n, n\geq 2$ y se derivan para las pequeñas $n$

\begin{align*} \alpha_2&=\frac{1}{2}\\ \alpha_3&=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\tag{i}\\ &=\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12}=0,41\dot{6}\\ \alpha_4&=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\sum_{j_2}^{j_1+1}\frac{1}{j_2}\tag{ii}\\ &=\frac{1}{2}\left(\frac{1}{2}\sum_{j_2=2}^3\frac{1}{j_2}+\frac{1}{3}\sum_{j_2=2}^4\frac{1}{j_2}\right)\\ &=\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)+\frac{1}{3}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)\right) =\frac{7}{18}=0,3\dot{8}\\ \alpha_5&=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\sum_{j_2}^{j_1+1}\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3}\tag{iii}\\ &=\frac{1}{2}\left(\frac{1}{2}\sum_{j_2=2}^3\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3}+\frac{1}{3}\sum_{j_2=2}^4\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3}\right)\\ &=\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}\sum_{j_3=2}^3\frac{1}{j_3}+\frac{1}{3}\sum_{j_3=2}^4\frac{1}{j_3}\right)\right.\\ &\qquad \left.+\frac{1}{2}\left(\frac{1}{2}\sum_{j_3=2}^3\frac{1}{j_3}+\frac{1}{3}\sum_{j_3=2}^4\frac{1}{j_3}+\frac{1}{4}\sum_{j_3=2}^5\frac{1}{j_3}\right)\right)\\ &=\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)+\frac{1}{3}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)\right)\right.\\ &\qquad\left.+\frac{1}{3}\left(\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)+\frac{1}{3}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right) +\frac{1}{4}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}\right)\right)\right)\\ &=\frac{1\,631}{4\,320}=0,377\,54\overline{629} \end{align*} de acuerdo con el OP de cálculo.

De (i),(ii),(iii) obtenemos general $n$: \begin{align*} \color{blue}{\alpha_n=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\sum_{j_2=2}^{j_1+1}\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3} \cdots\sum_{j_{n-2}=2}^{j_{n-3}+1}\frac{1}{j_{n-2}}\sum_{j_{n-1}=2}^{j_{n-2}+1}\frac{1}{j_{n-1}}\qquad\qquad n\geq 3}\tag{1} \end{align*}

Nota: El omnipresente catalán números ocurrir aquí también. Si escribimos $\alpha_n$ \begin{align*} \alpha_2&=\frac{1}{2},&C_1=1\\ \alpha_3&=\frac{1}{\color{blue}{2}\cdot 2}+\frac{1}{\color{blue}{2}\cdot 3},&C_2=2\tag{2}\\ \alpha_4&=\frac{1}{\color{blue}{2\cdot 2}\cdot 2}+\frac{1}{\color{blue}{2\cdot 2}\cdot 3}+\frac{1}{\color{blue}{2\cdot 3}\cdot 2}+\frac{1}{\color{blue}{2\cdot 3}\cdot 3}+\frac{1}{\color{blue}{2\cdot 3}\cdot 4},&C_3=5\\ &\ \,\vdots \end{align*} vemos que el número de sumandos de $\alpha_n$$C_{n-1}$. La marca en azul factores en $\alpha_n$ provienen de los factores de $\alpha_{n-1}$.

La recurrencia de la relación

Con el fin de encontrar una relación de recurrencia que nos gustaría invertir el orden de la suma en (1). Por desgracia esto es algo engorroso ya que el límite superior de su interior, una suma no muy bien se corresponden con el límite inferior de la siguiente externa de la suma. En su lugar, mostrar la relación con la ayuda del número de triángulos que también puede proporcionar información adicional $$ \begin{array}{r|cccc} n&w_{\alpha_2}&w_{\alpha_3}&w_{\alpha_4}&w_{\alpha_5}\\ \hline\\ 5&&&&\frac{1}{5}\\\\ 4&&&\frac{1}{4}&\frac{1}{4}\\\\ 3&&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\\\ 2&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\ \\ \hline\\ \\ \end{array} \qquad\qquad\qquad \begin{array}{r|rrrr} n&\alpha_2&\alpha_3&\alpha_4&\alpha_5\\ \hline\\ 5&&&&\frac{1}{120}\\\\ 4&&&\frac{1}{4}&\frac{12}{288}\\\\ 3&&\frac{1}{6}&\frac{5}{36}&\frac{7}{54}\\\\ 2&\frac{1}{2}&\frac{1}{4}&\frac{5}{24}&\frac{7}{36}\\ \\ \hline\\ \alpha_n&\frac{1}{2}&\frac{5}{12}&\frac{7}{18}&\frac{1\,631}{4\,320} \end{array} $$

La tabla de la izquierda muestra un triangular de la región de pesos $\frac{1}{2},\frac{1}{3},\ldots$ peso $\frac{1}{n}$ de la fila $n$. Estos pesos se utilizan para generar las entradas de la tabla de la derecha y $\alpha_n$ que es la suma de las entradas en el $n$-ésima columna. Se denota filas y columnas a partir de $2$, de modo que la parte inferior izquierda del elemento es$a_{22}=\frac{1}{2}$, mientras que la parte superior derecha del elemento es $a_{55}=\frac{1}{5!}=\frac{1}{120}$. Tenemos \begin{align*} \color{blue}{\alpha_2}&=a_{22}\color{blue}{=\frac{1}{2}}\\ \color{blue}{\alpha_3}&=a_{32}+a_{33}\\ &=\frac{1}{2}a_{22}+\frac{1}{3}a_{22}\\ &=\frac{1}{4}+\frac{1}{6}\color{blue}{=\frac{5}{12}}\\ \color{blue}{\alpha_4}&=a_{42}+a_{43}+a_{44}\\ &=\frac{1}{2}\left(a_{32}+a_{33}\right)+\frac{1}{3}\left(a_{32}+a_{33}\right)+\frac{1}{4}a_{33}\\ &=\frac{5}{24}+\frac{5}{36}+\frac{1}{24}\color{blue}{=\frac{7}{18}}\\ \color{blue}{\alpha_5}&=a_{52}+a_{53}+a_{54}+a_{55}\\ &=\frac{1}{2}\left(a_{42}+a_{43}+a_{44}\right)+\frac{1}{3}\left(a_{42}+a_{43}+a_{44}\right) +\frac{1}{4}\left(a_{43}+a_{44}\right)+\frac{1}{5}a_{55}\\ &=\frac{7}{36}+\frac{7}{54}+\frac{13}{288}+\frac{1}{120}\color{blue}{=\frac{1\,631}{4\,320}} \end{align*}

A partir de los cálculos anteriores se deriva la regla para construir las entradas $a_{k,l}$:

  • Tome $\frac{1}{k}$ veces la suma de todas las entradas de la columna de $k-1$ fila y mayor o igual $\max\{l-1,2\}$.

  • La relación de recurrencia es \begin{align*} a_{n,j}&=\frac{1}{j}\sum_{k=\max\{j-1,2\}}^{n-1}a_{n-1,k}\qquad\qquad\qquad\qquad\qquad n\geq 3,j=2,\ldots,n\\ \color{blue}{\alpha_2}&\color{blue}{=\frac{1}{2}}\\ \color{blue}{\alpha_n}&=\sum_{j=2}^na_{n,j}\color{blue}{=\sum_{j=2}^n\frac{1}{j}\sum_{k=\max\{j-1,2\}}^{n-1}a_{n-1,k}\qquad\qquad n\geq 3,j=2,\ldots,n}\tag{3} \end{align*}

Podemos mostrar la validez de (3) por la sucesiva aplicación de la relación de recurrencia para obtener \begin{align*} \color{blue}{\alpha_n}&=\sum_{j_1=2}^na_{n,j_1}\\ &=\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}a_{n-1,j_2}\\ &=\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}\frac{1}{j_2}\sum_{j_3=\max\{j_2-1,2\}}^{n-2}a_{n-2,j_3}\\ &\ \,\vdots\\ &=\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}\frac{1}{j_2} \cdots\sum_{j_{n-2}=max\{j_{n-3}-1,2\}}^{3}\frac{1}{j_{n-2}}\sum_{j_{n-1}=\max\{j_{n-2}-1,2\}}^{2}a_{2,j_{n-1}}\\ &\,\,\color{blue}{=\frac{1}{2}\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}\frac{1}{j_2} \cdots\sum_{j_{n-2}=max\{j_{n-3}-1,2\}}^{3}\frac{1}{j_{n-2}}}\tag{3} \end{align*} y (3) es el mismo que (1) con la suma en orden inverso.

Notas:

  • Es interesante, que sumando las columnas en la tabla de la derecha de arriba da una monótonamente creciente sucesión convergente a $\frac{1}{e}$. \begin{align*} \lim_{n\to\infty} \alpha_n=\frac{1}{e} \end{align*} Lo que me parece increíble es el uso de las pesas $\frac{1}{j}$ utilizado en la expresión de $\alpha_n$ (ver, por ejemplo, (2)), que hace de apariencia similar a \begin{align*} \sum_{j=0}^n(-1)^j\frac{1}{j!} \end{align*} pero sin la alternancia de signo.

  • Sería genial si alguien pudiera demostrar la convergencia de $(\alpha_n)$ al resolver la relación de recurrencia (3).

  • Podría ser interesante que la misma estructura de la relación de recurrencia (3), pero con diferentes pesos, es decir, $n-1$ en lugar de $\frac{1}{n}$ y diferentes valores de límite $a_{2,n}=1$ en lugar de $\frac{1}{2}$ $a_{n,n}=n-1$ en lugar de $\frac{1}{n}$ está archivada como A185423 en OEIS que indica el número de Ordenadas los bosques de $k$ el aumento de avión unario-árboles binarios con $n$ nodos. $$ \begin{array}{r|cccc} n&&&&\\ \hline\\ 5&&&&3\\\\ 4&&&3&3\\\\ 3&&2&2&2\\\\ 2&1&1&1&1\\ \end{array} \qquad\qquad\qquad \begin{array}{r|rrrr} A185423&&&&\\ \hline\\ 5&&&&24\\\\ 4&&&6&36\\\\ 3&&2&6&30\\\\ 2&1&1&3&9\\ \end{array} $$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X