# Solving a summation for n

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.

• 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. – Moritz Mar 9 '15 at 20:19

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

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

• The inner summation goes from $j=i$, not $j=1$. – Casteels Mar 9 '15 at 20:24
• I don't understand how you simplified the inner summation – SherMM Mar 10 '15 at 13:27
• 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$. – hypergeometric Mar 13 '15 at 16:19

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