Suma del producto de dos polinomios idénticos.

Question

Recientemente me he atascado, ante un problema. Sin embargo, rara vez creo que hay alguna fórmula adecuada para este problema, pero aquí estoy en la búsqueda de algoritmos o teoremas que se relacionan con este problema o puede resolver este problema.

Tenemos tres enteros positivos $a, b, n$ y tenemos que calcular esta suma:
$$\sum\limits_{k = 1}^n{(k^a - {(k - 1)}^a)(k^b - {(k - 1)}^b)}$$ Parece sencillo, si intentamos resolverlo con un ordenador, pero el verdadero problema radica en sus limitaciones:
$$n < 10^{12}$$ $$a < 10^4$$ $$b < 10^4$$
Evidentemente, no podemos iterar desde $k = 1$ a $k = n$ por lo que necesitamos pensar en un algoritmo que lo resuelva en tiempo constante o en complejidad en términos de $a$ y $b$
Se puede encontrar fácilmente una relación como ésta $\sum\limits_{k = 1}^n{(k^a - {(k - 1)}^a)} = n^a$ pero el problema tiene producto de dos términos de este tipo. Así que, por favor, dame alguna sugerencia para resolver este problema.

Answer 1

Esta no es una respuesta completa porque los límites de $a$ y $b$ dadas por OP implican que hay situaciones en las que $a>>n$ y $b>>n.$ (Por ejemplo, $n=10, a=1000, b=2000.$ ) La siguiente fórmula asintótica funciona bien si $n>>a$ y $n>>b.$ Dado el cuadrado de los límites de los parámetros para $a$ y $b$ en relación con $n$ La fórmula cubre en realidad todo el dominio menos una parte de cada 10^16.

$$ S:=\sum_{k=1}^n \big(k^a -(k-1)^a)\big(k^b -(k-1)^b) \sim \frac{n^{a+b-1} a\,b}{a+b-1} \Big( 1 - \frac{(a-1)(b-1)}{12 n^2} \frac{a+b-1}{a+b-3)} \Big) $$ La prueba es bastante fácil de construir utilizando algunos términos de la fórmula de Faulhaber, $$ (*) \quad \sum_{k=1}^n k^m = \frac{n^{m+1}}{m+1} + \frac{n^m}{2} + m \, \frac{n^{m-1}}{12} + \binom{m+1}{3}\frac{B_3}{m+1}n^{m-2} + ... $$ y el teorema del binomio. Obsérvese que el número de Bernoulli $B_3$ es 0. Para ir más allá de los dos términos dados en la fórmula asintótica, necesitarás más términos en la expansión binomial y la fórmula de Faulhaber. Por un simple arreglo de series, $$ S= - n^{a+b} + \sum_{k=1}^n 2 k^a - k^a(k-1)^b - k^b(k-1)^a $$ Definir un símbolo $$(a,b)_k := \binom{a}{k} + \binom{b}{k}.$$ Luego a una expansión binomial de 4º orden, $$S=-n^{a+b} + (a+b)\sum_{k=1}^n k^{a+b-1} - (a,b)_2\sum_{k=1}^n k^{a+b-2} + (a,b)_3\sum_{k=1}^n k^{a+b-3} - (a,b)_4\sum_{k=1}^n k^{a+b-4} $$ Utilice (*): $$ S= - n^{a+b} + (a+b)\Big(\frac{n^{a+b}}{a+b} + \frac{n^{a+b-1}}{2} + \frac{a+b-1}{12}n^{a+b-2} + 0 \cdot n^{a+b-3} + ... \Big) $$ $$- (a,2)_n \Big( \frac{n^{a+b-1}}{a+b-1} + \frac{n^{a+b-2}}{2} + \frac{a+b-2}{12}n^{a+b-3} + ... \Big)$$ $$+(a,3)_n \Big( \frac{n^{a+b-2}}{a+b-2} + \frac{n^{a+b-3}}{2} + ...\Big) - (a,4)_n \Big( \frac{n^{a+b-3}}{a+b-3} + ...\Big)$$

Las elipses indican términos que no se muestran, porque las potencias de $n$ se vuelven demasiado pequeños para aparecer en la respuesta final. Los 2 primeros términos se anulan. Organiza el resto como una serie descendente en potencias de $n:$ $$ S = n^{a+b-1}\Big( \frac{a+b}{2} - \frac{(a,b)_2}{a+b-1} \Big) + n^{a+b-2}\Big( \frac{(a+b)(a+b-1)}{12} - \frac{(a,b)_2}{2} + \frac{(a,b)_3}{a+b-2} \Big)$$ $$+n^{a+b-3}\Big(-\frac{(a+b-2)}{12}(a,b)_2 + \frac{(a,b)_3}{2} - \frac{(a,b)_4}{a+b-3} \Big) + ...$$ La simplificación de los coeficientes da la respuesta de la forma final.

Se puede ver que una vez que $a$ o $b$ se convierten en comparables a $n,$ el segundo término será tan grande como el primero, por lo que la solución asintótica empieza a fallar. Además, debemos tener a+b>3.

Como ejemplo, para n=5000, a=20, b=60: El primer término de la expansión asintótica da una precisión de unos 5 dígitos, y ambos términos dan una precisión de unos 10 dígitos.

Answer 2

Creo que escribir como $$n + \sum_{k=1}^n{\frac{k-1}{k}^{ab}-\frac{k-1}{k}^{a}-\frac{k-1}{k}^{b}}$$ más pertinente para empezar porque tienes una estructura comunmente separada de $\frac{k-1}{k}^{x}$

Answer 3

Si expandimos los términos obtenemos cuatro términos de los cuales dos se pueden calcular utilizando la fórmula de Faulhaber( https://en.wikipedia.org/wiki/Faulhaber%27s_formula ) y me encuentro con el mismo problema en este momento. No soy capaz de obtener la suma de los otros dos términos.