Lo que han descubierto/inventado es conocido como el avance operador diferencia $D$ se define como:
$
\def\nn{\mathbb{N}}
\def\zz{\mathbb{Z}}
\def\lfrac#1#2{{\large\frac{#1}{#2}}}
\def\lbinom#1#2{{\large\binom{#1}{#2}}}
$
$D = ( \text{function $f$ on $\zz$} \mapsto ( \text{int $n$} \mapsto f(n+1) - f(n) ) )$
Es decir, para cualquier función de $f$ $\zz$ y $n \in \zz$, $D(f)(n) = f(n+1) - f(n)$.
Si usted piensa de las funciones como secuencias (infinita en ambas direcciones), luego tomar el avance diferencia significa el reemplazo de cada término con el valor del siguiente plazo, menos a sí mismo. Lo que hizo es esencialmente tomar a veces el avance diferencia de la secuencia de cubos:
...,-27,-8,-1, 0, 1, 8,27,...
..., 19, 7, 1, 1, 7,19,37,...
...,-12,-6, 0, 6,12,18,24,...
..., 6, 6, 6, 6, 6, 6, 6,...
..., 0, 0, 0, 0, 0, 0, 0,...
..., 0, 0, 0, 0, 0, 0, 0,...
Esta poderosa abstracción hace que sea fácil conseguir un montón de cosas. Por ejemplo, los números obtenidos aquí puede ser utilizado fácilmente para obtener la fórmula general para la suma de los cubos!
Método General para la suma indefinida
La clave está en que:
$D\left( \text{int $n$} \mapsto \lbinom{n}{k+1} \right) = \left( \text{int $n$} \mapsto \lbinom{n}{k} \right)$ cualquier $k \in \zz$.
Esto es de esperarse ya que se deriva directamente del triángulo de Pascal, especialmente si definimos $\lbinom{n}{k}$ utilizando el triángulo.
Esto significa que si tenemos alguna función de $f$ $\zz$ tal que $f(n) = \sum_{k=0}^\infty a_k \lbinom{n}{k}$ cualquier $n \in \zz$, entonces tenemos el Newton de la serie:
$D(f)(n) = \sum_{k=0}^\infty a_{k+1} \lbinom{n}{k}$ cualquier $n \in \zz$.
De un alto nivel de perspectiva, esta es la versión discreta de la serie de Taylor, y de hecho para tal función, podemos ver fácilmente que el $f(n) = \sum_{k=0}^\infty D^k(f)(0) \lbinom{n}{k}$ cualquier $n \in \zz$, debido a $\binom{0}{0} = 1$ mientras $\lbinom{0}{k} = 0$ cualquier $k \in \nn^+$.
Esto funciona para cualquier función polinómica $f$$\zz$, ya que el $D^k(f)$ es el cero de la función una vez $k$ es mayor que el grado de $f$, de modo que puede utilizar para encontrar inmediatamente las series de $(\text{int n} \mapsto n^3)$, y luego tomar la anti-diferencia por el cambio de los coeficientes de la serie de la otra manera. La indeterminación constante que aparece caerá una vez que se realiza una suma determinada como si queremos que la suma de los primeros a $m$ cubos.
Tenga en cuenta también que $D^k(f)$ es la función constante con valor de $k!$ si $f(n) = n^k$ por cada $n$. Lee Mosher ya ha explicado este hecho en particular directamente la prueba, pero otra manera de ver esto es que el término de mayor orden en sus Newton de la serie es $k! \lbinom{n}{k}$, debido a $\lbinom{n}{k}$ es el único término que puede contribuir a la $k$-ésima potencia de a $n$. Desde $D$ solo cambia los coeficientes, $D^k(f) = \left( \text{int $n$} \mapsto k! \lbinom{n}{0} \right)$ y hemos terminado.
Suma de $p$ poderes
Por ejemplo, si queremos $\sum_{k=1}^{n-1} k^3$ encontramos por primera vez el iterado adelante diferencias de la secuencia de cubos $( n^3 )_{n \in \zz}$:
..., 0, 1, 8,27,64,...
..., 1, 7,19,37,...
..., 6,12,18,...
..., 6, 6,...
..., 0,...
Así que inmediatamente se $n^3 = 0 \binom{n}{0} + 1 \binom{n}{1} + 6 \binom{n}{2} + 6 \binom{n}{3}$ y, por tanto,$\sum_{k=0}^{n-1} k^3 = 0 \binom{n}{1} + 1 \binom{n}{2} + 6 \binom{n}{3} + 6 \binom{n}{4} = \lfrac{n(n-1)}{2} \Big( 1 + \lfrac{6(n-2)}{3} \big( 1 + \lfrac{n-3}{4} \big) \Big) = \Big( \lfrac{n(n-1)}{2} \Big)^2$.
La eficiencia de cálculo
Esto es mucho más eficiente que el método habitual (es decir, tomando la sumatoria de ambos lados de $(n+1)^3-n^3 = 3n^2+3n+1$ y telescópico) debido a que la serie utilizando los coeficientes binomiales es fácil de manejar y fácil de calcular. Para la suma de $p$-poderes sólo necesitamos $O(p^2)$ operaciones aritméticas para encontrar las diferencias y, a continuación, $O(p^2)$ más para simplificar la forma de serie en un polinomio de la forma. En contraste, el otro método requiere de $O(p^3)$ de las operaciones aritméticas.
Indefinido resumen de no-polinomios
También, para una amplia clase de los no-funciones polinómicas, todavía podemos calcular la suma indefinida sin el uso de la serie, mediante el discreto analógica a la integración por partes, aquí se llama suma por partes.
Para obtenerlo, basta con comprobar que el $D(f \times g)(n) = f(n+1) g(n+1) - f(n) g(n) = f(n+1) D(g)(n) - D(f)(n) g(n)$ y por lo tanto obtenemos el producto de la regla:
$D(f \times g) = R(f) \times D(g) + D(f) \times g$
donde $R$ es el derecho de cambio de operador se define como:
$R = ( \text{function $f$ on $\zz$} \mapsto ( \text{int $n$} \mapsto f(n+1) ) )$
Es decir, para cualquier función de $f$ $\zz$ y $n \in Z$, $R(f)(n) = f(n+1)$.
Para su comodidad también definimos la suma del operador:
$S = ( \text{function $f$ on $\zz$} \mapsto ( \text{int $n$} \mapsto \sum_{k=0}^{n-1} f(k) ) )$
A continuación, tenemos la importante propiedad de que $DS(f) = f$ para cualquier función de $f$$\zz$, análoga a la del teorema fundamental del cálculo.
Ahora sustituyendo $f$ $S(f)$ en el producto de la regla y tomando la sumatoria de ambos lados obtenemos la suma por partes:
$S( f \times g ) = S(f) \times g - S( R(S(f)) \times D(g) ) + c$ para algunas constantes de la función de $c$$\zz$.
Ejemplo indefinido suma
Mediante este podemos fácilmente calcular cosas como $\sum_{k=1}^n k^3 3^k$ mediante la aplicación de tres veces, cada vez que reduce el grado del polinomio parte. Hay otras maneras de lograr esto mediante la diferenciación, pero este método es puramente discretos.
