2

I simplified the most inner sum to: $j$. So, now I have:

$$\sum^{n-1}_{i=1}\sum^{n}_{j=i+1}j$$

I'm not sure if the following is correct but here is what I am thinking. I can re-index the inner sum by letting $m = j - i$. So, now I have

$$\sum^{n-1}_{i=1}\sum^{n}_{m=1} (j - m + 1)$$

Then the inner sum becomes:

$$\frac{(j-m+1)(j - m + 2)}{2}$$

So now I'm left with:

$$\sum^{n-1}_{i=1} \frac{(j-m+1)(j - m + 2)}{2} $$

Since, $j - m = i$, I have:

$$\sum^{n-1}_{i=1} \frac{(i+1)(i + 2)}{2} $$

Assuming the above is correct (for whatever reason, it doesn't feel right) then the only issue I am having is the pesky $n-1$ at the top. Can I do a change of variable on that as well and if I do then what would I have to subtract (or add) later? If that's not a good method and what's a good way to go about figuring this out?

Thanks a lot!

Jeel Shah
  • 9,306
  • The mistake is introduced when you change the summation index to $m=j-i$. You don't use the correct upper limit. The sum over $m$ starts at $m = (i+1) - i = 1$ but ends at $m = (n) - i = n-i$ not $n$. – Winther Jun 23 '16 at 19:11

3 Answers3

4

I am afraid that you have made a mistake somewhere in your work as the final sum does not evaluate to the same value as the initial sum.

Note: $\sum_{i=1}^n i=\frac{n(n+1)}{2}.\quad\!\!$ Thus, $\quad\!\!\!\sum_{i=a}^ni=\frac{(n+a)(n-a+1)}{2}=\sum_{i=1}^ni -\sum_{i=1}^{a-1}=\frac{n(n+1)}{2}-\frac{a(a-1)}{2}$

An easier way to approach this might be to evaluate the inner sum:

$$\sum_{j=i+1}^nj=\dfrac{(n+i+1)(n-i)}{2}$$

Then, since $(n+i+1)(n-i)=n^2+n-i-i^2$, we have

$$\sum_{i=1}^{n-1} \dfrac{n^2+n-i-i^2}{2}=\dfrac{1}{2}\left(n^2(n-1)+n(n-1)-\sum_{i=1}^{n-1}i-\sum_{i=1}^{n-1}i^2\right)$$

$$=\dfrac{1}{2}\left(n^2(n-1)+n(n-1)-\dfrac{1}{2}n(n-1)-\dfrac{1}{6}n(n-1)(2n-1)\right)=\dfrac{1}{3}n(n^2-1)$$

Eliza
  • 212
  • How did you evaluate the inner sum to what you did? Sorry, I'm slightly confused. How did you introduce $n$? And you're absolutely right, it doesn't make sense for the final sum to be the same the initial. – Jeel Shah Jun 23 '16 at 18:57
  • Jeel, I have edited the answer to put some comments early on. Besides that, I believe some other components such as $\sum_{i=1}^n i^2$ and $\sum_{i=1}^n n$ are elementary, which does not imply easy! – Eliza Jun 23 '16 at 19:09
  • Thanks Elaine, I think the note you added clears it up for me. I was not aware of the $i=a$ sum. This might be stupid question but when you do $\sum_{i=1}^{n-1} n^2$ why is it $n^2(n-1)$? I'm sorry, I haven't studied sums very much - this question stems from an algorithm question I was working on. Where is a good place to learn more about sums? – Jeel Shah Jun 23 '16 at 19:22
  • Jeel, when we have $\sum_{i=1}^{n-1} n^2$ we are looking at each term with $i$ and summing it over the different values. For example, $\sum_{i=1}^n i=1+2+\cdot\cdot\cdot+n$. But, we have $\sum_{i=1}^{n-1} n^2 i^0$ and $n^2$ is a constant. So, we sum $n^2$ exactly $n-1$ times and hence, $\sum_{i=1}^{n-1}n^2=n^2(n-1)$. – Eliza Jun 23 '16 at 19:35
  • For a very brief introduction: http://tutorial.math.lamar.edu/Classes/CalcI/SummationNotation.aspx

    It is most helpful to go through the Wikipedia page and looking at various summations: https://en.wikipedia.org/wiki/Summation

     – Eliza Jun 23 '16 at 19:39
0

$$\begin{align} \sum^{n-1}_{i=1}\sum^{n}_{j=i+1}\sum^{j}_{k=1} 1&=\sum_{j=2}^n\sum_{i=1}^{j-1}\sum_{k=1}^j1\\ &=\sum_{j=2}^nj(j-1)\\ &=2\sum_{j=2}^n \binom j2\\ &=2\binom {n+1}3\\ &=\frac 13 n(n^2-1)\qquad\blacksquare\end{align}$$

Hypergeometricx
  • 22,657
0

Just going to work this out with the OP's logic, making the necessary two change of variable corrections at the stumbling point (c.f. comment).

$\sum^{n-1}_{i=1}\sum^{n-i}_{m=1} (m + i) = \sum^{n-1}_{i=1}\left(\frac{(n-i)(n-i+1)}{2} + i(n-i)\right) = \sum^{n-1}_{i=1}(\frac{n^2+n-i-i^2}{2} )$

The accepted answer wraps thing up from here.

Although this might look like the accepted answer, it is more aligned with the OP's original intent; also, here we don't have to introduce a letter $a$.

CopyPasteIt
  • 11,366