# Basic Summation Rules

I'm not so good with manipulating summations, and recently going over some questions, I had some problems in understanding how some summation related answers were derived. Here are the two problems. It would be great if anyone could explain to me how these work in detail:

First Problem: fair value of a hat-drawing game

Here in this problem, in Yuval Filmus' solution, he turns the term $$\frac{\sum_{t=X}^{100} t}{100}$$ into $$\frac{(100-X+1)(100+X)}{200}$$

I am quite confused as to how he ended up getting this. I had gotten

$$\frac{\sum_{t=X}^{100} t}{100} = \frac{\sum_{t=0}^{100-X} (t + X)}{100} = \frac{(\sum_{t=0}^{100-X}t) + (\sum_{t=0}^{100-X}X)}{100} = \frac{(100 - X + 1)(100-X)(\frac{1}{2}) + (100-X)(X)}{100} = \frac{(100-X)(100-X+1+2X)}{200}=\frac{(100-X)(100+X+1)}{200}$$

Can anyone tell me where I went wrong?

Second Problem: Expected Value of the Difference between 2 Dice

In this problem I just straight up don't understand how the math works. Can anyone explain (or point me to some resources that I could read) how something like this comes about:

$$\sum_{i=1}^n \sum_{j=1}^n \dfrac{|i-j|}{n^2} = 2 \sum_{i=1}^n \sum_{j=1}^i \frac{i-j}{n^2} = \frac{n^2-1}{3n}$$

I neither understand how the summation formula works for absolute value nor how he got rid of the summations at the end.

Thanks!

-

In the first problem, $\sum_{t=0}^{100-X}X=(100-X+1)X$: there are $100-X+1$ terms because of the $t=0$ term. Fix this, and you’ll get Yuval’s answer.

In the second, notice first that $|i-j|=0$ when $i=j$, so we can remove those terms from the sum. Next, $|i-j|=|j-i|$, so we need only sum the terms in which $i>j$ and then double the total to account for those in which $i<j$. The sum of the terms in which $i>j$ is $$\frac1{n^2}\sum_{i=2}^n\sum_{j=1}^{i-1}(i-j)\;:\tag{1}$$

the $1/n^2$ is constant and can be pulled out, $i$ must be at least $2$ to leave room for a smaller $j$, and $j$ runs only up to $i-1$, so as to remain less than $i$. (Robert didn’t pull out the constant factor, and he left in the terms in which $i=j$; since they’re $0$, there’s no actual difference.)

Now rewrite the inner sum: as $j$ runs from $1$ to $i-1$, $i-j$ runs from $i-1$ down to $1$, so $$\sum_{j=1}^{i-1}(i-j)=\sum_{k=1}^{i-1}k=\frac12i(i-1)\;.$$ Substitute this into $(1)$ to get $$\frac1{n^2}\sum_{i=2}^n\frac12i(i-1)=\frac1{2n^2}\sum_{i=2}^ni(i-1)=\frac1{2n^2}\sum_{i=1}^{n-1}i(i+1)\;,$$ where the last step is just an index shift. Now break up the sum to get

\begin{align*} \frac1{2n^2}\sum_{i=1}^{n-1}i(i+1)&=\frac1{2n^2}\left(\sum_{i=1}^{n-1}i^2+\sum_{i=1}^{n-1}i\right)\\ &=\frac1{2n^2}\left(\frac16(n-1)n(2n-1)+\frac12n(n-1)\right)\\ &=\frac{n-1}{12n}(2n-1+3)\\ &=\frac{(n-1)(n+1)}{6n}\\ &=\frac{n^2-1}{6n}\;. \end{align*}

Recall that we have to double this to account for the terms with $i<j$, so the actual sum in question is $$\sum_{i=1}^n\sum_{j=1}^n\frac{|i-j|}{n^2}=\frac{n^2-1}{3n}\;.$$

-
Thank you so much for the explanation. Could you quickly expound on how that index shift worked? –  Matt May 22 '12 at 2:47
@Matt: Sure. Think of it as a substitution. Let $k=i-1$; then $i=k+1$, and $\sum_{i=2}^n i(i-1)=\sum_{k+1=2}^n(k+1)(k+1-1)=\sum_{k=1}^{n-1}(k+1)k$; now rename $k$ back to $i$. –  Brian M. Scott May 22 '12 at 2:51

For the first one:

We have a sum of the form $\sum_{t=X}^{100} t$. Now, lets write it as: $$\frac{\sum_{t=X}^{100} t + \sum_{t=X}^{100} t}{2}=\frac{\sum_{t=X}^{100} t + \sum_{t=X}^{100} (100+X-t)}{2}$$ This second sum comes from the fact that we change the order of it, we sum up from the last to the first: now the first term is 100 and the last one $X$, as you can verify. It is the same thing as if we took the first sequence, and copied it down: $$X,X+1,...,99,100$$ $$100,99,...,X+1,X$$ As you can see, the sum in each column is constant! Now we put both sums together and we have: $$\frac{\sum_{t=X}^{100} (100+X)}{2}=\frac{(100+X)(100-X+1)}{2}$$

-
$$\sum_{i=1}^{n} \sum_{j=1}^{n} \frac{\lvert i - j \rvert}{n^2}$$ Split the inner sum over $j$ from $1$ to $i$ and $i+1$ to $n$.
$$\sum_{i=1}^{n} \sum_{j=1}^{n} \frac{\lvert i - j \rvert}{n^2} = \sum_{i=1}^{n} \left( \sum_{j=1}^{i} \frac{\lvert i - j \rvert}{n^2} + \sum_{j=i+1}^{n} \frac{\lvert i - j \rvert}{n^2} \right)$$
In the first inner sum, where $j$ runs over $1$ to $i$, we have $\lvert i - j \rvert = i-j$ (Why?). In the second inner sum, where $j$ runs over $i+1$ to $n$, we have $\lvert i - j \rvert = j-i$ (Why?). Hence, $$\sum_{i=1}^{n} \sum_{j=1}^{n} \frac{\lvert i - j \rvert}{n^2} = \sum_{i=1}^{n} \left( \sum_{j=1}^{i} \frac{ i - j}{n^2} + \sum_{j=i+1}^{n} \frac{j-i}{n^2} \right) = \frac1{n^2} \left(\sum_{i=1}^{n} \left(i^2 - \frac{i(i+1)}{2} + \frac{(n-i)(n+i+1)}{2} -i(n-i)\right) \right)$$ Now sum this again to get the desired result.