0
$\begingroup$

I am trying to simplify the following summation:

$$\sum_{i=1}^{n/2}\sum_{j=i}^{n-i}j$$

I am not really sure how to solve the inner summation at the moment. I tried this:

$$\sum_{j=2i}^{n}j-i$$ and from there simplifying further. Right now, I keep coming up with very complex outcomes that are difficult to solve. I think I am missing something key point that makes this summation more straightforward. Once, I am able to solve this inner summation, I don't really know how I should handle the (n/2) upper bound on the outer summation. I guess it can be treated as any normal upper bound, and, depending on what terms are being summed, plugged in accordingly. However, I am not quite sure. Any help is greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ Do you have access to "Concrete Mathematics: Foundation for Computer Science" by R. Graham (ISBN-10: 0201558025)? Double sums are one of the many topics in this book. $\endgroup$ – Moritz Mar 9 '15 at 20:19
5
$\begingroup$

By following Gauss and its proof from elementary school, $$ \sum_{j=1}^{m}j = \binom{m+1}{2}, $$ hence: $$ \sum_{j=a}^{b} j = \binom{b+1}{2}-\binom{a}{2} $$ and: $$\sum_{i=1}^{n/2}\sum_{j=i}^{n-i}j = -\sum_{i=1}^{n/2}\binom{i}{2}+\sum_{i=1}^{n/2}\binom{n-i+1}{2}= -\sum_{i=1}^{n/2}\binom{i}{2}+\sum_{i=n/2+1}^{n}\binom{i}{2} .\tag{1}$$ Now finish the proof by proving $$ \sum_{k=2}^{M}\binom{k}{2}=\binom{M+1}{3} \tag{2}$$ through induction, then applying such an identity to $(1)$.

$\endgroup$
1
$\begingroup$

$$\sum_{i=1}^{n/2}\sum_{j=i}^{n-i}j=\frac{1}{2}\sum_{i=1}^{n/2}n\left(n+1-2i\right)=\frac{n^{3}}{8}.$$

$\endgroup$
  • 1
    $\begingroup$ The inner summation goes from $j=i$, not $j=1$. $\endgroup$ – Casteels Mar 9 '15 at 20:24
  • $\begingroup$ I don't understand how you simplified the inner summation $\endgroup$ – SherMM Mar 10 '15 at 13:27
  • $\begingroup$ Evaluate $$\sum_{j=i}^{n-i}j$$ using the standard AP summation formula $$\frac N2\left(A+L\right)$$ where $A=i$, $L=n-i$, and $N=n-2i+1$. $\endgroup$ – hypergeometric Mar 13 '15 at 16:19
1
$\begingroup$

$$\begin{align} S&=\sum_{i=1}^{\frac n2}\sum_{j=i}^{n-i}j\\ &=\sum_{i=1}^{\frac n2}\left(\sum_{j=i}^{\frac n2-1}n+\frac n2\right) \qquad \text{noting that } \small\sum_{j=i}^{n-i}j =\color{blue}{\sum_{j=i}^{\frac n2-1}j}+\color{purple}{\frac n2}+\color{green}{\sum_{j=\frac n2+1}^{n-i}j} =\sum_{j=i}^{\frac n2-1}[\color{blue}j+\color{green}{(n-j)}]+\color{purple}{\frac n2}\\ &=n\sum_{i=1}^{\frac n2}\left(\sum_{j=i}^{\frac n2-1}1+\frac 12\right)\\ &=n\left(T_{\frac n2-1}+\frac n4\right)\qquad\qquad \text{where } T_m=\frac {m(m+1)}2=\sum_{i=1}^{m}\sum_{j=i}^{m}1\\\\ &=\frac n2\left(2 \;T_{\frac n2-1}+\frac n2\right)\\\\ &=\frac n2\left(\frac n2\right)^2 \qquad\qquad\qquad\quad \text{using } 2T_{m-1}+m=m^2\\\\ &=\frac{n^3}8\qquad\blacksquare \end{align}$$


For visualisation:

$$\begin{align} S=1+2+3+\cdots+&\frac n2 +\cdots+(n-3)+(n-2)+(n-1)\\ +2+3+\cdots+&\frac n2 +\cdots+(n-3)+(n-2)\\ +3+\cdots+&\frac n2 +\cdots +(n-3)\\ &\;\vdots\\ +&\frac n2\\ \end{align}$$

Folding the right side of the triangular array over the left side, we find that this is equivalent to $$\begin{align} S=\overbrace{n+n+n+\cdots+n}^{\frac n2 -1}+\frac n2&\\ +n+n+\cdots+n+\frac n2&\\ +n+\cdots+n+\frac n2&\\ \vdots&\\ +\frac n2&\\ \end{align}$$ or $$\begin{align} S=\overbrace{\frac n2+n+n+\cdots+n+n}^{\frac n2}&\\ +\frac n2+n+\cdots+n+n&\\ +\frac n2+\cdots+n+n&\\ \vdots&\\ \vdots&\\ +\frac n2&\\ \end{align}$$ which is also equal to

$$\begin{align} S=&\;\;\frac n2\\ &\;\;\;\vdots\\ &\;\;\;\vdots\\ &+n+\cdots+n+\frac n2\\ &+n+n+\cdots+n+\frac n2\\ &+\underbrace{n+n+\cdots+n+n+\frac n2}_{\frac n2}\\ \end{align}$$ From this we can see clearly that $$S=\frac 12 \left(\frac n2\right)\left(\frac n2\right)n=\frac{n^3}8$$

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