Fórmula de la suma de las series

Question

Necesito calcular la suma de la serie lo más rápidamente posible en un programa dado n et k : $$f(n,k)= \frac{\sum_{i=0}^{n-1}f(i,k-1)}{n} $$ et $ f(i,0) =i $ para todos $i$ .

Hice algunos trámites y llevé la solución a $$f(n,k)=\frac{f(n-1,k-1)}{n} + \frac{(n-1)f(n-1,k)}{n} $$ Pero necesito una solución de forma cerrada. ¿Es posible dar resultados en O(1) or O( lg n) tiempo (el preprocesamiento está permitido pero no debe ser del orden de O(n^2 ) or O( k^2)) .

Answer 1

La solución de Marvis estaría muy bien si funcionara, pero la fórmula de $f(n,1)$ falla cuando $n=0$ y esto se propaga a los cálculos posteriores. Por cierto: aunque esto está implícito en la fórmula recursiva, ayudaría especificar $f(0,k)=0$ explícitamente en el planteamiento del problema.

Consideremos sólo $n\ge 1$ a partir de ahora. Entonces $f(n,1) = \frac12(n-1)$ se mantiene, y $$f(n,2) = \frac{1}{2n} \sum_{i=1}^{n-1}(i-1) =\frac{1}{2n} \left\{\frac{n(n-1)}{2}-n+1\right\} = \frac{n-3}{4} +\frac{1}{2n} \tag1$$ Utilizando la notación $H_n=1+\frac12+\dots+\frac1{n}$ para números armónicos encontramos $$\begin{align}f(n,3) & = \frac{1}{4n} \sum_{i=1}^{n-1}(i-3) + \frac{1}{2n}\sum_{i=1}^{n-1} \frac{1}{i} = \frac{1}{4n} \left\{ \frac{n(n-1)}{2} -3n+3\right\}+\frac{H_{n-1}}{2n} \\ &= \frac{n-7}{8} +\frac{3}{4n}+\frac{H_{n-1}}{2n} \end{align} \tag2$$

Esto nos lleva a una desagradable constatación: si pudiéramos computar $f(n,3)$ en $O(1)$ Entonces se podría hacer lo mismo con los números armónicos. He buscado algoritmos para calcular $H_n$ y encontró esta discusión . No leí cuidadosamente, pero tal vez se puede optimizar a $O(\lg n)$ .

Avanzando, nos encontramos con las sumas de $H_{n-1}/n$ . Un concepto superficialmente similar es números hiperarmónicos definido por $H_n^{(1)}=H_n$ y $H_n^{(r)}=\sum_{i=1}^n H_n^{(r-1)}$ cuando $r\ge 2$ . La fórmula de Conway y Guy (por ejemplo, aquí ) nos dice que $r$ añade muy poca complejidad: $$H_n^{(r)} = \binom{n+r-1}{r-1}(H_{n+r-1}-H_{r-1}) \tag3$$ Desgraciadamente, $n$ en el denominador de $H_{n-1}/n$ no permite que aparezcan los números hiperarmónicos, por lo que sé.
$$\begin{align}f(n,4) & = \frac{1}{8n} \sum_{i=1}^{n-1}(i-7) + \frac{3}{4n}H_{n-1} + \frac{1}{2n}\sum_{i=1}^{n-1}\frac{H_{i-1}}{i} \\ &= \frac{n-15}{16} +\frac{7}{8n} + \frac{3}{4n}H_{n-1} + \frac{1}{2n}\sum_{i=1}^{n-1}\frac{H_{i-1}}{i} \end{align} \tag4$$ En general, si definimos $$H_n^{[r]}=\sum_{i=1}^{n-1}\frac{H_{i}^{[r-1]}}{i},\quad H_n^{[0]}=1 \tag5$$ entonces $$f(n,k) = \frac{n-(2^k-1)}{2^k} +\sum_{r=0}^{k-2} \frac{2^{k-r-1}-1}{2^{k-r-1}n}H_n^{[r]} \tag6$$ donde los términos correctores $H_n^{[r]}$ se vuelven cada vez más costosos de calcular.

Answer 2

Esta solución es errónea.

$$f(n,1) = \dfrac{\sum_{i=0}^{n-1} f(i,0)}n = \dfrac{\sum_{i=0}^{n-1} i}n = \dfrac{n(n-1)}{2n} = \dfrac{n-1}2$$ $$f(n,2) = \dfrac{\sum_{i=0}^{n-1} f(i,1)}n = \dfrac{\sum_{i=0}^{n-1} (i-1)}{2n} = \dfrac{n(n-1)/2 - n}{2n} = \dfrac{(n-1)/2-1}2 = \dfrac{n-3}4$$ $$f(n,3) = \dfrac{\sum_{i=0}^{n-1} f(i,2)}n = \dfrac{\sum_{i=0}^{n-1} (i-3)}{4n} = \dfrac{n(n-1)/2 - 3n}{4n} = \dfrac{(n-1)/2-3}4 = \dfrac{n-7}8$$ Por lo tanto, en general, podemos adivinar $$f(n,k) = \dfrac{n-(2^k-1)}{2^k} = -1 + \dfrac{n+1}{2^k}$$ Una vez que tenemos esto probamos que nuestra conjetura es efectivamente cierta por inducción.