2
$\begingroup$

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

Formulas in my book give me equations to memorize and solve simple questions like $$ \sum_{i=0}^{n} i $$ ... However, For the question on top, how would I go about solving it by hand without a calculator? WolfRamAlpha seems to give the equation of 1/6[(n-2)(n-1)n].

Any suggestions would be appreciated. It's not a homework question, but I am studying for a test. I wrote the mathematical version of two nested for-loops for code that checks to see if a number in an array is unique or not.

Thank you.

  • 0
    Is the $i$ in the inner summation an $i$, or meant to be a $j$? (that is, does it depend on $j$ at all?) If it is an $i$, then the inner sum is just $(n-i-1)i$.2011-02-24
  • 0
    My guess is it is neither $i$ nor $j$. It is $1$.2011-02-24
  • 0
    @ Arturo: I had the same question at first, but then posted my answer below. The reason why is even if it is a $j$, reversing the order of summation gives a sum identical to the one above, except possibly the start and end points of the sum maybe be changed by a constant.2011-02-24

1 Answers 1

2

Since the sum $$\sum_{j=i+1}^{n-1} i $$ does not depend on $j$ we see $$\sum_{j=i+1}^{n-1} i = i\cdot\sum_{j=i+1}^{n-1} 1= i(n-1-i) $$

Then you have to find $$\sum_{i=0}^{n-2} \left( i(n-1-i)\right)=\sum_{i=0}^{n-2} \left( (n-1)i-i^2)\right)=(n-1) \sum_{i=0}^{n-2} i- \sum_{i=0}^{n-2} i^2$$

Can you solve it from here?

Hope that helps,

Edit: Perhaps you wanted a $j$. In other words, lets evaluate $$ \sum_{i=0}^{n-2}\left(\sum_{j=i+1}^{n-1} j\right) $$ Reversing the order of summation yields: $$ \sum_{j=1}^{n-1}\left(\sum_{i=j-1}^{n-2} j\right) $$ which can be solved by the exact same method presented above.