¿Cuál es el límite inferior de la suma $S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n)$ ?

Question

Si tenemos

$$ S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n) $$

Cuál es el límite inferior de $S(n)$ cuando $n\to\infty$ ?

PD: Si no cometí ningún error al calcular $S(n)$ entonces debería ser $\Omega(n)$ . Pero no sé cómo conseguirlo.

Answer 1

Podemos hacer algo mejor que un límite inferior. Podemos encontrar el término principal, que es $\sqrt{\frac{\pi n}{2}}$ .

Observe que $$\prod_{j=1}^{k}\left(1-\frac{j}{n}\right)=\frac{1}{n^{k}}\prod_{j=1}^{k}\left(n-j\right)=\frac{1}{n^{k}}\frac{(n-1)!}{(n-k-1)!}=\frac{\left(n-1\right)_{k}}{n^{k}}.$$ Utilizando esto, y el hecho de que el $k=n$ término es $0$ podemos reescribir nuestra serie como

$$(n-1)!\sum_{k=1}^{n-1}\frac{1}{n^{k}(n-k-1)!}=\frac{(n-1)!}{n^{n-1}}\sum_{k=1}^{n-1}\frac{n^{n-k-1}}{(n-k-1)!}=\frac{(n-1)!}{n^{n-1}}\sum_{j=0}^{n-2}\frac{n^{j}}{j!}.$$

La última línea se deduce de la sustitución $j=n-k-1$ . Esta última suma es la truncada serie exponencial con $x=n$ . Concretamente tenemos que $$\sum_{k=0}^{n-2}\frac{n^{k}}{k!}\sim \frac{1}{2}e^{n}.$$ Así, nuestra serie es $$\sim\frac{e^{n}(n-1)!}{2n^{n-1}}.$$ Por Fórmula de Stirling el término principal es $$\frac{e^{n}(n-1)!}{n^{n-1}}=\sqrt{2\pi n}+O\left(\frac{1}{\sqrt{n}}\right),$$ por lo que podemos concluir que $$\sum_{k=1}^{n}\prod_{j=1}^{k}\left(1-\frac{j}{n}\right)\sim\sqrt{\frac{\pi n}{2}}.$$

Espero que le sirva de ayuda,

Edita: Antes faltaba un factor de dos. Gracias a Didier Piau por señalarlo.

Answer 2

Esto es $Q(n)-1$ donde $Q(n)$ es una suma que aparece repetidamente en la obra de Knuth y que menciono en mi respuesta a su otra pregunta. Una ligera adaptación del argumento muestra que el término dominante es (en la notación de la respuesta) $T_n(0)$ por lo que obtenemos $$Q(n) = S(n)+1 = \sqrt{\frac{\pi n}{2}} + O(1).$$ Si desea una asíntota más precisa, puede consultar la obra de Knuth Arte de la programación informática vol. 1 (3ª ed.), sección 1.2.11.3 (como ya he mencionado en mi otra respuesta). Da $$Q(n) = S(n)+1 = \sqrt{\frac{\pi n}{2}} - \frac{1}{3} + \frac{1}{12} \sqrt{\frac{\pi }{2n}} - \frac{4}{135n} + O(n^{-3/2}).$$