1
$\begingroup$

So as we know, if we have a summation from $1$ to $n$, the simple formula is

$$\sum_{i=1}^n i=\frac{n(n+1)}2.$$

But if we have two summations, one from $i=1$ to $n$ and another one $j>i$ to $n$, the formula we get is

$$\sum_{i=1}^n\sum_{j>i}^nj=\frac{n(n-1)}2.$$

I'm not understanding this, how does it go from $n+1$ to $n-1$, especially since it's a double summation?

$\endgroup$
  • $\begingroup$ I have edited your question. You can re-edit it if my edits are not correct. $\endgroup$ – Tianlalu Nov 19 '18 at 3:11
1
$\begingroup$

I think you might be confusing two different things.

Fact 1: Define $S_n := \sum_{k=1}^n k$. Then $S_n = n(n+1)/2$ for every nonnegative integer $n$.

(You can see this by induction. Certainly the formula is correct for $n = 0$. With $S_{n-1} = (n-1)n/2$, we have $S_{n} = n + S_{n-1} = (n+1)n/2$, as required.)

Then there is the following fact

Fact 2: Define $T_n = \sum_{1 \leq i < j \leq n} 1$. Then $T_n = n(n-1)/2$.

This is just the number of tuples $(k, l)$ with $1 \leq k \leq n$ and $1 \leq l \leq n$ there are with $k < l$. That's just $\binom{n}{2}$, or if you like it's also $(n^2 - n)/2 = n(n-1)/2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.