¿Dónde suma de las fórmulas?

Question

Es un problema clásico en la introducción de la prueba del curso para demostrar que $\sum_{ i \mathop =1}^ni = \frac{n(n+1)}{2}$ por inducción. El problema de la inducción es que no se puede probar lo que la suma es a menos que usted ya tiene una idea de lo que debería ser. Me gustaría saber cuál es el proceso para conseguir la idea.

Wikipedia tiene un montón de la suma de las fórmulas de la lista, y seguramente hay muchas más, pero creo que debería ser capaz de simplificar sumatorias sin hacer referencia a una tabla. No creo que hay una técnica universal para la obtención de todos ellos, pero sería bueno saber que al menos un par de cosas para probar.

Esta pregunta fue motivada por una respuesta que involucran suma, y aunque no tengo dudas de que es verdad, yo no sabría cómo obtener la respuesta a la suma sin ser dicho de antemano.

Answer 1

Este enfoque se calcula el $\sum_{i=1}^n i^k$ en términos de$\sum_{i=1}^n i^j$$j=0,1,\dots,k-1$. Esto nos permite en realidad calcular el $\sum_{i=1}^n i^k$ desde ciertamente,$\sum_{i=1}^n i^0 = n$. He publicado este un par de veces, y en este punto lo tienen guardado para su re-uso.

Comenzamos con esta ecuación:

$$n^k = \sum_{i=1}^n i^k-(i-1)^k.$$

Esto es para $k \geq 1$. De esta manera se sigue por telescópica; el $n^k$ plazo sobrevive, mientras que el $0^k$ plazo es cero y todos los otros términos cancelar. Usando el teorema del binomio:

\begin{align*} n^k & = \sum_{i=1}^n i^k-\sum_{j=0}^k {k \choose j} (-1)^j i^{k-j} \\ & = \sum_{i=1}^n \sum_{j=1}^{k} {k \choose j} (-1)^{j+1} i^{k-j} \\ & = \sum_{j=1}^{k} {k \choose j} (-1)^{j+1} \sum_{i=1}^n i^{k-j} \end{align*}

Así que ahora podemos resolver esta ecuación para $\sum_{i=1}^n i^{k-1}$:

$$\sum_{i=1}^n i^{k-1} = \frac{n^k + \sum_{j=2}^k {k \choose j} (-1)^j \sum_{i=1}^n i^{k-j}}{k}.$$

Más claramente, vamos a $S(n,k)=\sum_{i=1}^n i^k$, luego

$$S(n,k)=\frac{n^{k+1} + \sum_{j=2}^{k+1} {k+1 \choose j} (-1)^j S(n,k+1-j)}{k+1}$$

para $k \geq 1$. Ahora empieza la recursividad con $S(n,0)=n$.

Un fácil de inducción argumento de esta expresión muestra que el $S(n,k)$ es un polinomio en a $n$ grado $k+1$. Esto significa que si usted desea conseguir un $S(n,k)$ para algunos un gran $k$, se puede asumir con seguridad que un polinomio de la forma y, a continuación, calcular la interpolación polinomial, en lugar de la intensificación de la recursividad de la parte inferior.

Answer 2

Hay, de hecho, existen universal técnicas para la obtención de expresiones exactas para sumatorias. Donald Knuth le preguntó en un problema en uno de sus libros para desarrollar programas de ordenador para la simplificación de las sumas que implican los coeficientes binomiales. La respuesta a ese problema fue dada por Marko Petkovsek, Herbert Wilf y Doron Zeilberger en su libro "A = B", que pueden descargar de forma gratuita aquí.

Answer 3

Puede ser con un ejemplo podría ser más claro. Tomemos por ejemplo $$1+2+...+50$$

Como se puede observar, usted tiene que $$51=1+50=2+49=3+48=4+47=...$$ y así, en $$1+...+n,$$ si $n$ es incluso, se suma $$\underbrace{(n+1)+...+(n+1)}_{\frac{n}{2}\ times}=\frac{n(n+1)}{2}.$$

Si $n$ es impar, la suma $$\underbrace{(n+1)+...+(n+1)}_{\frac{(n-1)}{2}\ times}+\frac{n+1}{2}=\frac{(n+1)(n-1)+n+1}{2}=\frac{(n+1)(n-1+1)}{2}=\frac{n(n+1)}{2}$$

Answer 4

Como Gauss hizo:

Escribir los primeros n números en ordenadas dirección en la primera fila. Escribir números iguales en la dirección opuesta en la segunda fila. A continuación, agregue la columna de números. Consigue $n$ multiplicado por el número de $n+1$. Este producto $n \cdot (n + 1)$ es dos veces la suma de los primeros a $n$ números. Dividir por dos, y se obtiene la suma de los primeros a $n$ números.

$$\begin{array}{l} \begin{array}{*{20}{c}} 1&2&.&.&.&.&.&.&{n - 1}&n\\ n&{n - 1}&.&.&.&.&.&.&2&1\\ {n + 1}&{n + 1}&.&.&.&.&.&.&{n + 1}&{n + 1} \end{de la matriz}\\ \sum\limits_{k = 1}^n k = \frac{n}{2}(n + 1) \end{array}$$