¿Va al infinito $\sum_{i=0}^\infty{i\left((1-p^{i+1})^m-(1-p^{i})^m\right)}$ $\log m$?

Question

Resumen

Creo que la siguiente suma $$\sum_{i=1}^\infty{i\left((1-p^{i+1})^m-(1-p^{i})^m\right)}$$ es $O(\log m)$, donde $0<p<1$ e $m \geq 1$. Sin embargo, yo no era capaz de demostrarlo formalmente, a pesar de mis esfuerzos sin fin (binomial expansiones, derivación, majoration, etc. y la combinación de los mismos).

Contexto

Yo estaba estudiando una variación de la saltarse la lista de estructura de datos. Cada clave de un salto de la lista se asocia una "torre" de una cierta altura. La altura es la que ha elegido repetidamente tirando una moneda: con una probabilidad de $p$ la torre crece de un nivel, con una probabilidad de $1-p$ nos detenemos. Considere la posibilidad de $m$ claves y la variable aleatoria "nivel máximo de las torres de ese $m$ claves". La expresión anterior es el valor esperado de esta RV. Curiosamente estándar de la literatura acerca de saltarse las listas se lleva a una especie de trabajo en torno a demostrar que el número de niveles de $O(\log n)$ donde $n$ es el número de claves en la exclusión de la lista.

Experimentos con Mathematica

Es posible numéricamente apoyo mi conjetura. La siguiente es una Mathematica experimento.

maxi = 100; 
maxm = 10^9; 
G[m_] := Sum[i*((1 - p^(i + 1))^m - (1 - p^i)^m), {i, 0, maxi}]; 
p = 0.5; 
delta = G[m] - Log[1/p, m] /. m -> maxm; 
DiscretePlot[{G[m], Log[1/p, m]}, {m, 1, maxm, maxm/200}, 
 PlotLegends -> "Expressions"]
DiscretePlot[G[m] - Log[1/p, m] - delta, {m, 1, maxm, maxm/100}]

obtenemos el gráfico, tanto de la suma y la función de registro a $m=10^9$ y gráfico de su diferencia. El segundo gráfico es un poco raro, no sé si es un numérica fenómeno o una ondulación de la propia función.

Answer 1

Vamos a denotar su suma por $S(m,p)$. Primero de todo, tenemos $$S(m,p)=\sum_{k=1}^{\infty}\big(1-(1-p^k)^m\big)=\color{blue}{\sum_{j=1}^{m}(-1)^{j-1}\binom{m}{j}\frac{p^j}{1-p^j}}.$$ (La primera igualdad se obtiene, con $a_k=1-(1-p^k)^m$, de $$\sum_{k=1}^{n}k(a_k-a_{k+1})=\sum_{k=1}^{n}ka_k-\sum_{k=1}^{n+1}(k-1)a_k=\sum_{k=1}^{n}a_k-na_{n+1};$$ para obtener el segundo, expandir $(1-p^k)^m$ y suma más de $k$ en primer lugar).

Una "herramienta" para que este tipo de sumas es Nørlund–Arroz integral (fácilmente verificado por uno mismo): $$S(m,p)=-\frac{m!}{2\pi i}\oint_{C}F(m,p,z)\,dz,\qquad F(m,p,z)=\frac{(p^{z}-1)^{-1}}{\prod_{j=0}^{m}(z+j)}$$ donde $C$ es un contorno cerrado que rodea $z=-1,\ldots,-m$ y no otros polos de el integrando.

Ahora, si $C_n$ es el círculo de $|z|=-(2n+1)\pi/\ln p$ orientada hacia la izquierda, a continuación, $$0=\lim_{n\to\infty}\frac{m!}{2\pi i}\oint_{C_n}F(m,p,z)\,dz=-S(m,p)+m!\sum_{n\in\mathbb{Z}}\operatorname*{Res}_{z=2n\pi i/\ln p}F(m,p,z);$$ la evaluación de los residuos que se da (no sólo un asintótica - una exacta deuno!) $$S(m,p)=-\frac{1}{2}-\frac{H_m}{\ln p}+\frac{1}{\pi}\sum_{n=1}^{\infty}\frac{1}{n}\Im\prod_{j=1}^{m}\Big(1+\frac{2n\pi i}{j\ln p}\Big)^{-1},$$ donde $H_m=\sum\limits_{j=1}^{m}\dfrac{1}{j}$ es el $m$-ésimo número armónico.

Esto confirma $\color{blue}{\dfrac{S(m,p)}{\ln m}\underset{m\to\infty}{\longrightarrow}-\dfrac{1}{\ln p}}$, como $H_m=\ln m+O(1)$ cuando $m\to\infty$.