How can I solve this summation?

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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.