0

I'm trying to evaluate the following nested summation as a function of $n$:

$$\sum_{i=1}^{n-1} \sum_{j=i+1}^n \sum_{k=1}^j 1$$

So far I have: $$\sum_{i=1}^{n-1}\sum_{j=i+1}^n i+1$$ $$\sum_{i=1}^{n-1} \left(\sum_{j=i+1}^n i+\sum_{j=i+1}^n 1 \right)$$ This is where I've gotten stuck. I feel that I may be solving this incorrectly:

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

Any and all help is appreciated!

Michael Hardy
  • 1
  • 31
  • 294
  • 591
HNVDB
  • 3
  • 2
  • 1
    You can use [the summation formula for squares](http://math.stackexchange.com/questions/48080/proof-that-sum-limits-k-1nk2-fracnn12n16) and [the gaussian summation for the first $k$ integers](https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF) – flawr Jan 30 '16 at 21:54
  • 1
    Your second step should be $$\sum_{i=1}^{n-1}\sum_{j=i+1}^n j.$$ – Intelligenti pauca Jan 30 '16 at 21:54

2 Answers2

1

$$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\sum_{k=1}^j1=\sum_{i=1}^{n-1}\sum_{j=i+1}^nj=\sum_{i=1}^{n-1}(n+i+1)(n-i)/2=\frac{1}{2}\left(n^2\sum_{i=1}^{n-1}1-n\sum_{i=1}^{n-1}i+n\sum_{i=1}^{n-1}i-\sum_{i=1}^{n-1}i^2+n\sum_{i=1}^{n-1}1-\sum_{i=1}^{n-1}i\right)=\frac{1}{2}\left(n^2(n-1)-\frac{1}{6}(n-1)n(2n-1)+n(n-1)-\frac{1}{2}n(n-1)\right)= \frac{1}{2}(n-1)n\Big(n-\frac{1}{6}(2n-1)+1-\frac{1}{2}\Big)=\frac{1}{2}(n-1)n\Big(\frac{2}{3}n+\frac{2}{3}\Big)=\frac{1}{3}(n-1)n(n+1)$$

Marcin Malogrosz
  • 1,910
  • 11
  • 8
  • Thanks for your help. Can you explain the following step: $$ \sum_{i=1}^{n-1}\sum_{j=i+1}^nj=\sum_{i=1}^{n-1}\frac{(n+i+1)(n-i)}{2} $$ I'm having trouble visualizing it. I'm assuming it's some sort of play on $\frac{n(n+1)}{2}$ . – HNVDB Jan 30 '16 at 22:31
  • One uses the fact that if $(a_k)_{k=l}^{r}$ is an arithmetic sequence than $\sum_{k=l}^ra_k=\frac{1}{2}(a_l+a_r)(r-l+1)$ – Marcin Malogrosz Jan 31 '16 at 03:58
0

Let's look at the first one: $\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1$

$ \displaystyle \sum_{k=1}^{j}1$ means $1+1+\ldots + 1$ added to itself exactly $j$-many times. Therefore $ \displaystyle \sum_{k=1}^{j}1 = j$

Then the triple-sum becomes $\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j$

Let's look at the inner-sum again: $\displaystyle \sum_{j=i+1}^{n}j = (i+1)+(i+2)+\ldots + n$.

There is a formula for $\displaystyle 1+2+\ldots + n = \frac{n(n+1)}{2}$.

What we have above is the sum of the first $n$ natural numbers, minus the sum of the first $i$ natural numbers. Work that out and there's only one sum left to compute.

Daron
  • 9,785
  • 1
  • 18
  • 40