0

I'm trying to understand how to simplify summations. My text says that: $$\sum_{i=1}^{\frac{n}{2}} \sum_{j=i}^{n-i} \sum_{k=1}^{j} 1 = \frac{n^3}{8}$$

But does not explain how to get to the right-hand side.

I think the above nested summation evaluates to $\sum_{i=1}^{n/2} \left[\sum_{j=i}^{n-i} j = i + (i + 1) + (i + 2) + .. + (n-i-1) + (n-i)\right]$, but I don't know how to proceed from here.

k.Vijay
  • 2,128
Larssend
  • 105

3 Answers3

3

Hint: $$\sum_{j=i}^{n-i} j = \sum_{j=1}^{n-i} j - \sum_{j=1}^{i-1} j.$$ The right hand side now should look rather familiar (Gauss...).

There is also a rule for $$\sum_{i=1}^n i^2,$$ if you look this up and prove it or if you already know it, that should give the final result.

Dirk
  • 6,359
  • I think I need to brush up on how to manipulate and split summations and do more practice problems. Can you recommend me a book or something that explains this particular topic very well? – Larssend May 08 '17 at 05:11
1

Exploit the symmetry.

Put $n=2m$ (assuming $n$ is even):

$$\begin{align} S =\sum_{i=1}^{\frac n2}\sum_{j=i}^{n-i}\sum_{k=1}^j 1 =\sum_{i=1}^{\frac n2}\sum_{j=i}^{n-i}j &=\sum_{i=1}^m\sum_{j=i}^{2m-i}j&&(n=2m)\tag{1}\\ &=\sum_{i=1}^m\sum_{j=i}^{2m-i}(2m-j)&&(j\leftarrow 2m-j)\tag{2}\\ &=m\sum_{i=1}^m\sum_{j=i}^{2m-i}1 &&\dfrac{(1)+(2)}2\\ &=m\sum_{i=1}^m\left(\sum_{j=i}^m1+\sum_{j=m+1}^{2m-i}1\right)\\ &=m\sum_{i=1}^m\left(\sum_{j=i}^m1+\sum_{j=1}^{m-i}1\right)\\ &=m\sum_{i=1}^m\left(\sum_{j=i}^m1+\sum_{j=1}^{i-1}1\right) &&\big(i\leftarrow m-i+1\atop\scriptsize\text{for second summation}\big)\\ &=m\sum_{i=1}^m\sum_{j=1}^m 1\\ &=m^3\\ &=\color{red}{\frac {n^3}{8\;}} \end{align}$$

The solution is derived only by manipulating summation limits and indices without requiring expansion or evaluation of sum of squares or integers.

Hypergeometricx
  • 22,657
0

\begin{align} \sum_{k=1}^{j} 1 &= j \\ \sum_{j=i}^{n-i} j &= \frac{n(n-2i+1)}{2} \\ S &= \sum_{i=1}^{n/2} \frac{n(n-2i+1)}{2} \\ &= \frac{n(n+1)}{2} \sum_{i=1}^{n/2} 1- n \sum_{i=1}^{n/2} i \end{align}

  • If $n=2m$, \begin{align} S &= \frac{2m(2m+1)}{2} \times m-2m\times \frac{m(m+1)}{2} \\ &= m^3 \\ &= \frac{n^3}{8} \end{align}

  • If $n=2m-1$, \begin{align} S &= \frac{(2m-1)(2m)}{2} \times (m-1)-(2m-1)\times \frac{(m-1)m}{2} \\ &= \left( \frac{2m-1}{2} \right)^3-\frac{2m-1}{8} \\ &= \frac{n^3-n}{8} \end{align}

Your equality holds for even $n$ only.

Ng Chung Tak
  • 18,990