Suma de suma de $k$th poder de la primera $n$ números naturales.

Question

Yo estaba trabajando en un problema que involucra el cálculo de $k$-ésima potencia de primer a $n$ números naturales.

Decir $f(n) = 1^k+2^k+3^k+\cdots+n^k$, se puede calcular el $f(n)$ mediante el uso de Faulhaber del Triángulo, también por el rápido cálculo de los números de Bernoulli.

Aquí tenemos que calcular $G(n)= f(1)+f(2)+f(3)+\cdots+f(n)$

Hice algunos trabajos sobre este para simplificar, pero incapaz de encontrar cualquier ecuación fácil.

Alguien me puede ayudar cómo calcular $G(n)$ eficiente , yo de manera eficiente puede calcular $f(n)$.

Aquí $n<123456789$ y $k<321$.

Gracias.

Answer 1

$$G_k(n)= \sum_{i=1}^n f_k(i)= \sum_{i=1}^n \sum_{j=1}^i j^k = \sum_{j=1}^n (n+1-j) j^k=(n+1)\sum_{j=1}^n j^k - \left(\sum_{j=1}^n j^{k+1} \right)\\ =(n+1)f_k(n)-f_{k+1}(n)$$

Ya que usted dijo que usted puede calcular eficientemente

$$f_{k}(n) =\sum_{j=1}^n j^k$$ también se puede calcular de manera eficiente $$(n+1)f_k(n)-f_{k+1}(n)=g_k(n)$$

Answer 2

Usted puede encontrar que es útil para visualizar la suma: $$ \begin{matrix} 1^k \\ 1^k & 2^k \\ 1^k & 2^k & 3^k \\ 1^k & 2^k & 3^k & 4^k \\ \vdots&\vdots&\vdots&\vdots&\ddots \\ 1^k & 2^k & 3^k & 4^k & \dots & n^k \\ \end{de la matriz} $$

$$ G_k(n) = n\cdot1^k + (n-1)\cdot2^k + (n-2)\cdot3^k + \dots + 2\cdot(n-1)^k + 1\cdot n^k = \sum_{s=1}^{n} (n-s+1)s^k $$

Esto le llevará $O(n\lg k)$ multiplicaciones para calcular directamente. Estoy tratando de encontrar un camino mejor.

EDIT: yo estaba en el camino correcto. Para el glorioso final, véase la respuesta publicado por N. S.