Donald Knuth ' notación de sumatoria s me confunde.

Question

Yo no entiendo mucho de los casos de Knuth de la notación de sumatoria en Concreto de las Matemáticas. En general, me parece no puede aprehender la propiedad conmutativa de la ley aplicada a la manipulación de las sumas. La propiedad conmutativa de la ley se dice:

$$\sum_{k \in K}a_{k}=\sum_{p(k) \in K}a_{p(k)}$$

$K$ es un conjunto de números enteros y $p(k)$ es cualquier permutación de los enteros en ese conjunto.

Mi mayor problema surge con casos como este:

$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0 \leq n-k \leq n}(a+b(n-k))=\sum_{0 \leq k \leq n}(a+bn-bk)$$

Cómo se puede justificar que las dos últimas expresiones son equivalentes? Yo también estoy luchando con el siguiente ejemplo:

$$\sum_{1 \leq j < k \leq n}\frac{1}{k-j}=\sum_{1 \leq j < k+j \leq n}\frac{1}{k}=\sum_{1 \leq k \leq n}\sum_{1 \leq j \leq n-k}\frac{1}{k}$$

Para ser claro, yo entiendo la sustitución. Yo no, sin embargo, entender la forma en que se expandió la suma y eligió a los límites inferiores y superiores de los límites. Alguien podría posiblemente explique esta notación en la forma más simple posible, pero no más simple?

Answer 1

Ginger Rogers hizo todo lo Fred Astaire hizo, sólo que al revés y en tacones altos.

Voy a promocionar mi comentario con respecto a la primera parte de una respuesta completa. Como ya he dicho, considere la posibilidad de

$$\sum_{0\leq k\leq n}(a+bk)=(a+0\cdot b)+(a+1\cdot b)+\cdots+(a+(n-1)\cdot b)+(a+n\cdot b)$$

y el contraste con

$$\sum_{0\leq k\leq n}(a+(n-k)b)=(a+(n-0)\cdot b)+(a+(n-1)\cdot b)+\cdots+(a+(n-(n-1))\cdot b)+(a+(n-n)\cdot b)$$

La escritura de las sumas de esta manera muestra que uno es simplemente una reversión de los otros, y de hecho, esto es una solicitud de adición de la conmutatividad. (Las sustituciones hechas por Marvis y Brian decir lo mismo, sólo que en lenguaje algebraico.)

---

Ya que ha dicho que está trabajando en el Concreto de las Matemáticas, me siento más que justificada para mostrar la utilidad de Iverson soportes en la manipulación de doble sumas. (Efectivamente, esta es una reafirmación de Marvis y Brian respuestas en Iversonian formulario).

Como un recordatorio de la definición, $[p]$ evalúa a $1$ si la condición de $p$ es cierto, y $0$ si la condición de $p$ es falso. Iverson soportes tienen la propiedad útil que $[p\text{ and }q]=[p][q]$, para lo cual será importante aquí.

Podemos volver a escribir la suma doble en Iversonian forma como

$$\sum_j\sum_k\frac{[1\leq j<k\leq n]}{k-j}$$

(Es un poco de un abuso que sólo un simbolo fue escrito cuando dos índices se indican, pero vamos a perdonar). Tenga en cuenta que podemos tratar de manera efectiva la suma como una infinita suma, desde la Iverson soportes de cero términos que no cumplan la condición que encierra.

Como ya se ha explicado en las respuestas anteriores, podemos hacer la sustitución de $k\mapsto k+j$ así:

$$\begin{align*}\sum_j\sum_k\frac{[1\leq j<k+j\leq n]}{k+j-j}&=\sum_j\sum_k\frac{[1\leq j<k+j\leq n]}{k}\\&=\sum_j\sum_k\frac{[1\leq k<k+j\leq n]}{k}\end{align*}$$

Tenga en cuenta que aquí estaba muy bien de no tocar la suma de los índices, ya que si $-\infty < j < \infty$$-\infty < k < \infty$, también tenemos $-\infty < j+k < \infty$. También estamos justificados en sustitución de la $j$ en la segunda línea con un $k$, ya que el $k < k+j$ en el rango de ser considerado

Ahora podemos dividir la Iverson factor de uso de la propiedad que he mencionado anteriormente. En particular, hemos

$$\begin{align*}\sum_j\sum_k\frac{[1\leq k<k+j\leq n]}{k}&=\sum_k\sum_j\frac{[(1\leq k\leq n)\text{ and }(1\leq j+k\leq n)]}{k}\\&=\sum_k\sum_j\frac{[1\leq k\leq n][1\leq j+k\leq n]}{k}\end{align*}$$

(También he tomado la libertad de intercambio de sumación de orden en el ínterin.)

Podemos reorganizar el último bit a

$$\sum_k\sum_j\frac{[1\leq k\leq n][-k\leq j\leq n-k]}{k}=\sum_k\sum_j\frac{[1\leq k\leq n][1\leq j\leq n-k]}{k}$$

¿Cómo sucede esto? Debido a las condiciones $1\leq j\leq n$$1\leq k\leq n$, se puede poner a cero todos los términos de$j=-k$$j=0$. Un final de reordenamiento conduce a

$$\sum_k [1\leq k\leq n] \sum_j [1\leq j\leq n-k] \frac1{k}=\sum_{1\leq k\leq n} \sum_{1\leq j\leq n-k} \frac1{k}$$

y hemos terminado.

Answer 2

Después de mucha concentración y fracaso, aquí está mi respuesta :)

\begin{align} S_n&=\sum_{1 \leq j < k \leq n}\frac{1}{k-j}\\ \text{Let } k&=j+u\\ S_n&=\sum_{1 \leq j < j+u \leq n}\frac{1}{u}\\ j+u \leq n &\rightarrow j \leq n-u\\ 1 \leq j \text{ and } j \leq n-u &\rightarrow 1 \leq j \leq n-u\\ 1 \leq n-u &\rightarrow u \leq n-1\\ j < u+j &\rightarrow 0 < u\\ 0 < u &\rightarrow 1 \leq u\\ \therefore 1 \leq &u \leq n-1\\ \text{Thus } S_n&=\sum_{1 \leq j \leq n-u}\sum_{1 \leq u \leq n-1}\frac{1}{u}\\ &=\sum_{1 \leq u \leq n-1}\frac{n-u}{u}\\ \frac{n-u}{u}&=0 \text{ at } u=n\\ \therefore S_n&=\sum_{1 \leq u \leq n}\frac{n-u}{u}\\ &=n\sum_{1 \leq u \leq n}\frac{1}{u}-\sum_{1 \leq u \leq n}1\\ &=nH_n-n\\ &=n\left(H_n-1 \right) \end {Alinee el}

(La otra suma parece trivial en comparación.)

P.d.: he publicado esto solamente como una conclusión a la pregunta y que demuestra que entiendo la pregunta debido a la ayuda de Math.SE. También quería compartir mi tren de pensamiento con los usuarios aquí.

Answer 3

Vamos a echar un vistazo a $$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0 \leq n-k \leq n}\Big(a+b(n-k)\Big)\;.$$ It may help to look at this as a substitution. Let $j=n-k$; then $k=n-j$, por lo que

$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0\le n-j\le n}\Big(a+b(n-j)\Big)\;.$$ But $0\le n-j\le n$ iff $-n\le j-n\le 0$ iff $0\le j\le n$ (by multiplying by $-1$ and adding $n$), por lo

$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0\le j\le n}\Big(a+b(n-j)\Big)\;.$$ Now just rename $j$ to $k$, y usted tiene la deseada.

$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0\le k\le n}\Big(a+b(n-k)\Big)\;.$$ Cuando usted está aprendiendo a esto, a menudo ayuda a escribir la sustitución de forma explícita, como he hecho aquí.

Para $$\sum_{1 \leq j < k \leq n}\frac{1}{k-j}=\sum_{1 \leq j < k+j \leq n}\frac{1}{k}=\sum_{1 \leq k \leq n}\sum_{1 \leq j \leq n-k}\frac{1}{k}\;,\tag{1}$$ let $i=k-j$. Note that $1\le j<k\le n$ iff $1\le j<j+i\le$ n, por lo que

$$\sum_{1\le j<k\le n}\frac1{k-j}=\sum_{1\le j<j+i\le n}\frac1i\;.$$ If you now rename $i$ to $k$, you have $$\sum_{1\le j<k\le n}\frac1{k-j}=\sum_{1\le j<j+k\le n}\frac1k\;,\tag{2}$$ which is clearly the same as the middle summation in $(1)$. Now what are the possible values of $k$? It has to be at least $1$, since $j+k>j$, and it can be at most $n-1$, when $j=1$ and $j+k=n$. Thus, if we break down the second summation in $(2)$ by lumping together all terms with the same $k$, we'll have something of the form $$\sum_{1\le k\le n-1}\text{something}\;.\tag{3}$$ (Don't worry about the $n-1$ for now.) For each fixed value of $k$, $j$ runs from a minimum of $1$ up to whatever makes $j+k$ equal to $n$: that's the biggest allowable value of $j+k$. Clearly that's $j=n-k$, so for each $k$, $j$ runs from $1$ through $n-k$. We can now replace the $\text{something}$ in $(3)$:

$$\sum_{1\le j<j+k\le n}\frac1k=\sum_{1\le k\le n-1}\left(\sum_{1\le j\le n-k}\frac1k\right)=\sum_{1\le k\le n-1}\sum_{1\le j\le n-k}\frac1k\;.$$

No se trata exactamente de la misma como Knuth del $$\sum_{1\le k\le n}\sum_{1\le j\le n-k}\frac1k\;,$$ but if you look closely, you'll see that these expressions actually have the same value: when $k=n$ in Knuth's the inner sum ranges over $1\le j\le 0$, so it's an empty sum and equals $0$.