1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why is there an $i-1$ on the upper bound of the second summation in your hint? Can you please explain what rule you used or link me to it because I dont really understand what you did. $\endgroup$ – ninesalt Oct 18 '16 at 19:33
  • $\begingroup$ $\sum^{n}_{i=0}=0+1+2+\ldots + i-2+i-1+i+i+1+\ldots + n-2+n-1+n$ $\endgroup$ – Iuli Oct 18 '16 at 19:35
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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