Donald Knuth y las operaciones algebraicas sobre sumas

Question

Estoy leyendo el primer libro de Knuth de la serie TAOCP y estoy en el capítulo 1.2.3 (Sumas y productos).

Como este es mi primer encuentro con la recapitulación, me tomé el tiempo de revisar lo que pude encontrar en Khan Academy.

He repasado el capítulo y he trabajado con algunos ejemplos, pero concretamente me cuesta entender las cuatro leyes algebraicas de las sumas que Knuth enumera en el capítulo. Estas son las que entiendo:

• 1. la ley distributiva y
• 3. intercambiar el orden de la suma ;

pero no entiendo del todo

• 2. cambio de variable y
• 4. manipulación del dominio (este en particular me confunde)

Me ha costado mucho encontrar información con los mismos nombres en Internet, así que esperaba que alguien pudiera indicarme material para leer.

Un ejemplo de cambio de variable que no necesariamente entiendo:

$$\sum\limits_{R(i)}a_i = \sum\limits_{R(j)}a_j = \sum\limits_{R(p(j))}a_{p(j)}$$

Esta ecuación representa dos tipos de transformaciones. En el primer caso simplemente estamos cambiando el nombre de la variable índice de i a j . El segundo caso es más interesante: Aquí p(j) es una función de j que representa un permutación de los valores relevantes...

Entiendo lo que dice la cita (específicamente sobre las permutaciones) pero no entiendo cómo procede desde la suma de la extrema izquierda a la suma de la extrema derecha y por qué ocurre eso.

Un ejemplo de manipular el dominio que no entiendo:

$$\sum\limits_{1\le j\le m}a_j + \sum\limits_{m\le j\le n}a_j = \left(\sum\limits_{1\le j\le n}a_j\right) +a_m$$

Entiendo el lado izquierdo de la ecuación; pero no entiendo el lado derecho: ¿dónde está el m en $a_m$ ¿a partir de ahora que la suma se ha simplificado?

Answer 1

Cambio de variable . Esto dice que no importa cómo se ordenen los términos que se suman, siempre que se tengan todos. Como ejemplo, es obvio que $$ a_1+a_2+\cdots+a_{n-1}+a_n = a_n+a_{n-1}+\cdots+a_2+a_1 $$ por lo que tenemos $$ \sum_{k=1}^n a_k = \sum_{j=1}^n a_{n+1-j} $$ ya que la expresión de la izquierda es la misma que la suma de la izquierda anterior y la expresión de la derecha es la misma que la suma de la derecha anterior. En términos elegantes, acabamos de permutar los índices de la izquierda $\langle 1, 2, \dots n-1, n\rangle\mapsto\langle n, n-1, \dots 2, 1\rangle$ .

Otro ejemplo que podrías probar es ver cuál sería la permutación que lograra esto: $$ a_1+a_2+\cdots+a_{99}+a_{100} = (a_1+a_3+\cdots+a_{99})+(a_2+a_4+\cdots+a_{100}) $$ Esta reescritura podría ser útil si los términos del índice impar se definieran de forma diferente a los términos del índice par.

Manipulación del dominio . Lo que ocurre aquí es que estás juntando las sumas en una sola y ajustando el hecho de que los términos de las dos sumas se superponen. Por ejemplo $$ \begin{align} \sum_{j=1}^3 a_j + \sum_{j=3}^5 a_j &= (a_1+a_2+a_3)+(a_3+a_4+a_5)\\ &=(a_1+a_2+a_3+a_4+a_5)+a_3\\ &=\left(\sum_{j=1}^5 a_j\right)+a_3 \end{align} $$ ya que los dos conjuntos de sumandos se superponen en $j=3$ , dándonos una copia extra de $a_3$ . Por supuesto, podríamos hacer una reescritura similar si las sumas se solaparan en más de un término.