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
  • 2
    $\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, 2015 at 20:19

3 Answers 3

6
$\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$
3
  • 1
    $\begingroup$ The inner summation goes from $j=i$, not $j=1$. $\endgroup$
    – Casteels
    Mar 9, 2015 at 20:24
  • $\begingroup$ I don't understand how you simplified the inner summation $\endgroup$
    – SherMM
    Mar 10, 2015 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$ Mar 13, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .