How can I solve this summation? I've been trying to solve this problem for quite some time now and I can't think of how to reduce the inner summation to a smaller problem. Usually when I have variables in the upper and lower bound of the summation, I just do 
$$(upper bound - lower bound + 1) * a$$ where $a$ is the value inside the summation. But this wont work here because I'll still have the $j$ variable inside the outer sigma. Is there an easier way to do this that I don't know?
$$\sum_{i=0}^{n}\,\,\sum_{j = i} ^ {n-1}(j -i +1 )$$
According to WolframAlpha, the solution should be:
$$\frac 16 n(n^2 + 3n + 2)$$
 A: This method doesn't use combinatorics explicitly, but reduces the sum to more well-known ones. 
The terms $-i$ and $1$ don't depend on the inner summation variable $j$, so you can take them out using the method you describe:
$$\begin{align}\sum_{i=0}^n \sum_{j=i}^{n-1} (j - i + 1) &= \sum_{i=0}^n \left( (n - i)(1-i) + \sum_{j=i}^{n-1}j\right)\end{align}$$
Also, we evaluate the inner summation as $T(n-1) - T(i-1)$ where $T(x)$ is the $x$th triangular number, and $T(-1)=T(0)=0$
$$\begin{align}\sum_{i=0}^n \sum_{j=i}^{n-1} (j - i + 1) &= \sum_{i=0}^n \left( (n - i)(1-i) + \sum_{j=i}^{n-1}j\right) \\
&= \sum_{i=0}^n \left( n - i(n+1) + i^2 + \sum_{j=i}^{n-1}j\right) \\
&= n \sum_{i=0}^n 1 - (n+1) \sum_{i=0}^n i + \sum_{i=0}^n i^2 + \sum_{i=0}^n \sum_{j=i}^{n-1}j \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + \sum_{i=0}^n \sum_{j=i}^{n-1}j \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + \sum_{i=0}^n (T(n-1) - T(i-1)) \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + (n+1)T(n-1) - \sum_{i=0}^n T(i-1) \\
&= n (n+1) - (n+1) T(n) + \sum_{i=0}^n i^2 + (n+1)T(n-1) - \sum_{i=1}^{n-1} T(i) \\
&= (n+1) \underbrace{\left( n - (T(n) - T(n-1)) \right)}_0 + \sum_{i=0}^n i^2 - \sum_{i=1}^{n-1} T(i) \\
&= \sum_{i=0}^n i^2 - \sum_{i=1}^{n-1} T(i) \\
\end{align}$$
Now the summation is expressed in terms of more standard summations whose values are well known.
$$\sum_{i=0}^n i^2 = \frac 1 6 n(n+1)(2n+1)$$
$$\sum_{i=1}^{n-1} T(i) = \frac 1 6 (n-1)n(n+1)$$
And we can evaluate:
$$\begin{align}\sum_{i=0}^n i^2 - \sum_{i=1}^{n-1} T(i) &= \frac 1 6 n (n+1) \left( (2n+1) - (n-1)\right)\\
&= \frac 1 6 n (n+1) (n+2)\\
&= \frac 1 6 n (n^2 + 3n + 2)\\
\end{align}$$
A: This should help you. 
HINT:
$$\sum^{n-1}_{j=i}{(j-i+1)}=\sum^{n-1}_{j=0}{(j-i+1)}-\sum^{i-1}_{j=0}{(j-i+1)}$$
$$\sum^{n-1}_{j=0}{(j-i+1)}=0+1+\ldots n-1-i \cdot n+n=\frac{n(n-1)}{2}+n-i \cdot n$$
$$\sum^{i-1}_{j=0}{(j-i+1)}=0+1+\ldots i-1-i\cdot i+1 \cdot i=\frac{(i-1)i}{2}+i-i \cdot i$$
$$\sum^{n}_{i=0}{\sum^{n-1}_{j=i}{(j-i+1)}}=\sum^{n}_{i=0}{\sum^{n-1}_{j=0}{(j-i+1)}}+\sum^{n}_{i=0}{\sum^{i-1}_{j=0}{(j-i+1)}}$$
A: $$S(n)=\sum_{i=0}^{n}\sum_{j=i}^{n-1}(j-i+1) = \sum_{i=0}^{n}\sum_{k=i+1}^{n}(k-i) = \sum_{0\leq i < k \leq n}(k-i) $$
How many couples $(i,k)$ with $i<k$ are such that $(k-i)=0$? Zero.
How many couples $(i,k)$ with $i<k$ are such that $(k-i)=1$? $n$.
How many couples $(i,k)$ with $i<k$ are such that $(k-i)=2$? $n-1$.
It follows that:
$$\begin{eqnarray*} S(n) &=& \sum_{c=1}^{n} c(n+1-c)\\ &=& [x^{n+1}]\left(\sum_{c\geq 0}c x^c\right)^2\\ &=& [x^{n+1}]\left(\frac{x}{(1-x)^2}\right)^2\\ &=& [x^{n-1}]\frac{1}{(1-x)^4} = \color{red}{\binom{n+2}{3}}=\frac{(n+2)(n+1)n}{6} \end{eqnarray*}$$
by stars and bars. It is a cubic polynomial in $n$, not a quadratic one.
A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{i\ =\ 0}^{n}\,\,\sum_{j\ =\ i}^{n - 1}\pars{j - i + 1}:\ ?}$.

$$
\mbox{Note that}\quad
\sum_{i\ =\ 0}^{n}\,\,\sum_{j\ =\ i}^{n - 1}\pars{j - i + 1} =
\left.\partiald{}{x}\sum_{i\ =\ 0}^{n}\,\,
\sum_{j\ =\ i}^{n - 1}x^{j - i + 1}
\,\right\vert_{\ x\ =\ 1}
$$

\begin{align}
\sum_{i\ =\ 0}^{n}\,\,
\sum_{j\ =\ i}^{n - 1}x^{j - i + 1} & =
x\sum_{i\ =\ 0}^{n}\sum_{j\ =\ 0}^{n - 1 - i}x^{j} =
x\sum_{i\ =\ 0}^{n}{x^{n - i} - 1 \over x - 1} =
{x \over x - 1}\pars{x^{n}\sum_{i = 0}^{n}x^{-i} - n - 1}
\\[5mm] & =
\pars{1 + {1 \over x - 1}}
\pars{x^{n}\,{x^{-n - 1} - 1 \over x^{-1} - 1} - n - 1}
\\[5mm] & =
\pars{1 + {1 \over \epsilon}}\bracks{{\pars{1 + \epsilon}^{n + 1} - 1\over \epsilon} - n - 1}\,,\qquad \epsilon \equiv x - 1.
\end{align}

Note that
\begin{align}
&\sum_{i\ =\ 0}^{n}\,\,\sum_{j\ =\ i}^{n - 1}\pars{j - i + 1} =
\bracks{\epsilon^{1}}\braces{\pars{1 + {1 \over \epsilon}}
\bracks{{\pars{1 + \epsilon}^{n + 1} - 1 \over \epsilon} - n - 1}}
\\[5mm] = &\
\bracks{\epsilon^{1}}\braces{\pars{1 + {1 \over \epsilon}}
\bracks{{\pars{n + 1}\epsilon + \pars{n + 1}n\epsilon^{2}/2 + \pars{n + 1}n\pars{n - 1} \epsilon^{3}/6\over \epsilon} - n - 1}}
\\[5mm] = &\
\bracks{\epsilon^{1}}\braces{\pars{1 + {1 \over \epsilon}}
\bracks{{1 \over 2}\,\pars{n + 1}n\epsilon +
{1 \over 6}\pars{n + 1}n\pars{n - 1}\epsilon^{2}}}
\\[5mm] & =
{1 \over 2}\pars{n + 1}n + {1 \over 6}\pars{n + 1}n\pars{n - 1} =
\bbx{\ds{{1 \over 6}\,n^{3} + {1 \over 2}\,n^{2} + {1 \over 3}\,n}}
\end{align}
A: Note that the effective upper limit of $i$ is $n-1$. 
Also, it is useful to express $j-i+1$ as a summation.
A symmetrical approach:
$$\begin{align}
\color{red}{\sum_{i=0}^n}\color{green}{\sum_{j=i}^{n-1}}\color{orange}{j-i+1}
&=\color{red}{\sum_{i=0}^{n-1}}\color{green}{\sum_{j=i}^{n-1}}\color{orange}{\sum_{k=i}^j 1}\\
&=\color{red}{\sum_{i=1}^{n}}\color{green}{\sum_{j=i}^{n}}\color{orange}{\sum_{k=i}^j} 1\\
&=\color{red}{\sum_{j=1}^n}\color{orange}{\sum_{k=1}^j}\color{green}{\sum_{i=1}^k} 1
\qquad\qquad \qquad (1\le i\le k\le j\le n)\\
&=\color{red}{\sum_{j=1}^n}\color{orange}{\sum_{k=1}^j} \color{green}{\binom k1}\\
&=\color{red}{\sum_{j=1}^n} \color{orange}{\binom {j+1}2}\\
&=\color{red}{\binom {n+2}3 =\frac {n(n+1)(n+2)}{6}=\frac 16 n(n^2+3n+2)}\quad\blacksquare\end{align}$$
A: To my experience, I suggest that you get accustomed and use the "index range" notation
which allows a more clear way of how you can manipulate indices by substitution/replacement, aggregation, etc.
So, in your particular case, some of the various possible manouvres are:
$$
\begin{gathered}
  \sum\limits_{i = 0}^n {\sum\limits_{j = i}^{n - 1} {\left( {j - i + 1} \right)} }  = \sum\limits_{\begin{array}{*{20}c}
   {0\, \leqslant \,i\, \leqslant \,n}  \\
   {i\, \leqslant \,j\, \leqslant \,n - 1}  \\
 \end{array} } {\left( {j - i + 1} \right)}  = \sum\limits_{\begin{array}{*{20}c}
   {0\, \leqslant \,i\, \leqslant \,n}  \\
   {0\, \leqslant \,j - i\, \leqslant \,n - 1 - i}  \\
 \end{array} } {\left( {j - i + 1} \right)}  =  \hfill \\
   = \sum\limits_{\begin{array}{*{20}c}
   {0\, \leqslant \,i\, \leqslant \,n}  \\
   {1\, \leqslant \,j - i + 1\, \leqslant \,n - i}  \\
 \end{array} } {\left( {j - i + 1} \right)}  = \sum\limits_{\begin{array}{*{20}c}
   {0\, \leqslant \,i\, \leqslant \,n}  \\
   {1\, \leqslant \,k\, \leqslant \,n - i}  \\
 \end{array} } k  = \sum\limits_{0\, \leqslant \,i\, \leqslant \,n} {\left( \begin{gathered}
  n - i + 1 \\ 
  2 \\ 
\end{gathered}  \right)}  =  \hfill \\
   = \sum\limits_{0\, \leqslant \,n - i\, \leqslant \,n} {\left( \begin{gathered}
  n - i + 1 \\ 
  2 \\ 
\end{gathered}  \right)}  = \sum\limits_{0\, \leqslant \,m\, \leqslant \,n} {\left( \begin{gathered}
  m + 1 \\ 
  2 \\ 
\end{gathered}  \right)}  = \sum\limits_{1\, \leqslant \,m + 1\, \leqslant \,n + 1} {\left( \begin{gathered}
  m + 1 \\ 
  2 \\ 
\end{gathered}  \right)}  =  \cdots  \hfill \\ 
\end{gathered} 
$$
wherefrom you are left with performing the summation over he upper index of a binomial, which is classical formula that supposedly you know.
