0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Larssend May 8 '17 at 5:11
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

\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.

$\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.