1

$$\sum_{i=1}^n \sum_{j=i+1}^n (i+j)$$

I'm pretty sure it's somewhat simple to solve but I can't get it done.

I know that the given sum is equal to $\frac{n}{2} (n^2-1)$.

I've been on this for 3h+ now and I'm really hoping someone can give me a hint :)

Florian
  • 23

3 Answers3

4

Here is a more visual approach: Fill a square $n\times n$ grid with the values of $i+j$: $$ \begin{matrix} 1+1&1+2&1+3&\cdots&1+n\\ 2+1&2+2&2+3&\cdots&2+n\\ 3+1&3+2&3+3&\cdots&3+n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ n+1&n+2&n+3&\cdots&n+n \end{matrix} $$ We are after the sum of all the elements above the main diagonal (the diagonal that goes from $1+1$ to $n+n$). Note that this is equal to the sum of all the elements below the main diagonal. So if we can find the sum of the entire table, and the sum of the main diagonal, then a simple subtraction followed by a division by 2 will get us there.

The sum of the main diagonal is $n(n+1)$.

For the sum of the entire table, collect each $j$ column-by column, and all the $i$'s row-by-row. The $j$'s in the first column sum to $n$. The $j$'s in the second column sum to $2n$, and so on. And similarly for the $i$'s. Thus the sum of all the elements in the table is $$ \underbrace{n+2n+\cdots+n^2}_{\text{the }j\text{'s}}+\underbrace{n+2n+\cdots+n^2}_{\text{the }i\text{'s}}=2n(1+2+\cdots+n)\\ =n^2(n+1) $$ Our final answer is therefore $$ \frac{n^2(n+1)-n(n+1)}2=\frac12n(n^2-1) $$

Arthur
  • 199,419
  • 1
    Drawing, or writing a table, is something I often find helpful when dealing with double sums or integrals. It's is particularly useful when trying to interchange the order of the summations. But some times, like here, it also helps calculate the final result. – Arthur Sep 09 '20 at 15:15
  • 1
    From the diagram it is evident that the average of the numbers is question is $n+1$, and there are $\binom n2=\frac12n(n-1)$ of them.... – Angina Seng Sep 09 '20 at 15:22
  • I really liked that approach since it viasualizes what I am doing! Thanks for showing me. – Florian Sep 09 '20 at 15:25
  • The question refer to a summation starting from $i=0$, this result is for the summation starting from $i=1$. – user Sep 09 '20 at 16:36
  • 1
    @user The title starts at $i=1$. And the edit history says that the title was there first. So I will keep it at $i=1$. – Arthur Sep 09 '20 at 16:39
  • @Arthur Sorry I didn't noticed that! – user Sep 09 '20 at 16:41
  • @AnginaSeng Indeed, going along the parallels to the main diagonal, we can see this quite clearly. This is another way of either finding the sum of all the table, or of just the upper triangular part we are interested in. – Arthur Sep 09 '20 at 16:53
2

Here is to help you to start:

\begin{align} \sum_{i=1}^n \sum_{j=i+1}^n (i+j) &= \left( \sum_{i=1}^n \sum_{j=i+1}^n i\right)+\left( \sum_{i=1}^n \sum_{j=i+1}^n j\right) \\ &= \left( \sum_{i=1}^n i (n-(i+1)+1)\right)+\left( \sum_{i=1}^n \left(\sum_{j=1}^n j -\sum_{j=1}^i j \right)\right) \\ \end{align}

Try to simplify it. Formulas to evaluate $\sum i^2$ is useful as well.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • 1
    \begin{align} \sum_{i=1}^n \sum_{j=i+1}^n (i+j) &= \left( \sum_{i=1}^n \sum_{j=i+1}^n i\right)+\left( \sum_{i=1}^n \sum_{j=i+1}^n i\right) \ \end{align}

    that's what I started with but I'm summing up j in the second sum, right?

    \begin{align} \sum_{i=1}^n \sum_{j=i+1}^n (i+j) &= \left( \sum_{i=1}^n \sum_{j=i+1}^n i\right)+\left( \sum_{i=1}^n \sum_{j=i+1}^n j\right) \ \end{align}

     – Florian Sep 09 '20 at 14:24
  • yes, I made a typo, thanks. btw, you might like to include your working in your post. :) – Siong Thye Goh Sep 09 '20 at 14:25
  • I'm the one thanking ! I wasn't sure if that's the way to go so I thought, I'd be better of not sharing it ^^ – Florian Sep 09 '20 at 14:43
  • actually on this site.... most people are not judging how much you know, but rather how much you have tried. the more you show that you have tried, the more help youl get. welcome to MSE. – Siong Thye Goh Sep 09 '20 at 14:52
1

By double counting with $p=i+j$

enter image description here

we have

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

$$=\frac12\left(\sum_{p=1}^{n} (p^2-3p)+\sum_{p=1}^{n+1} (n-p+2)(n+p-1)\right)=$$

$$=\frac12\left(\sum_{p=1}^{n} (n^2+n-2)+2n\right)=\frac12n(n^2+n-2)+n=\frac12n^2(n+1)$$

The answer you are referring to is for the sum starting form $i=1$ indeed

$$\frac12n^2(n+1)-\frac12 n(n+1)=\frac12n(n^2-1)$$

user
  • 154,566