1

Question:

Simplify $$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1}1$$

My attempt:

$$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1}1 =\sum_{i=0}^{n-1} (n-1-i) $$.

Would this now be the sum of the first $n-1$ integers?

Hypergeometricx
  • 22,657
  • @G.Sassatelli Thats strange because my textbook says that it is equal to sum of the first $n$ integers –  Oct 18 '17 at 01:34
  • $\sum_{i=0}^{n-1} n-1-i$ is the sum of the first $n-1$ positive integers and zero. However, $\sum_{j=i}^{n-1} 1\ne n-1-i$. In general, if $a\le b$, $\sum_{k=a}^b 1=b-a+1$. –  Oct 18 '17 at 01:35
  • How should I figure what the nested sum is equal to? –  Oct 18 '17 at 01:36
  • You should just realize it. –  Oct 18 '17 at 01:36
  • My guess is $n-i$ ? –  Oct 18 '17 at 01:37
  • 3
    A sum of 1's means counting. How many pairs of indices $(i,j)$ are there such that $0 \leq i \leq j \leq n-1$? – Catalin Zara Oct 18 '17 at 01:42

4 Answers4

2

$$\begin{align} \sum_{i=0}^{n-1} \sum_{j=i}^{n-1}1&=\sum_{j=0}^{n-1}\sum_{i=0}^{j}1 &&\scriptsize(0\le i\le j\le n-1)\\ &=\sum_{j=0}^{n-1}(j+1)\\ &=\sum_{j=1}^n j\\ &=\color{red}{\frac 12n(n+1)=\binom {n+1}2}\end{align} $$

Hypergeometricx
  • 22,657
1

The number of integers from $1$ to $m$ would be $m$. It can be computed by $m-1+\color{red}{1}$.

The number of integer from $i$ to $n-1$ would be $(n-1)-i+1=n-i$

$$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1}1 =\sum_{i=0}^{n-1} (n-1-i+\color{red}{1})= \sum_{i=0}^{n-1} (n-i)$$

When $i=0$, $n-i=n$.

When $i=n-1$, $n-i=n-(n-1)=1$.

Hence we are adding from $1$ to $n$ in the backward direction.

There is a special formula for $\sum_{i=1}^n i$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
1

$\sum_{i=0}^{n-1}\sum_{j=i}^{n-1}1 $ counts the elements of $\{(i,j)\in\{0,..,n-1\}^2: i\leq j\}$

From the set $\{0,..,n-1\}$, there are $\underline{\phantom{\binom{n}2}}$ ways to select two distinct elements ($i<j$), and $\underline{\phantom{\binom n1}}$ ways to select two identical indices ($i=j$).

$$\therefore\qquad\sum\limits_{i=0}^{n-1}\sum\limits_{j=i}^{n-1}1 ~= \dbinom{n+1}2$$

Graham Kemp
  • 129,094
0

Put the sequence in a matrix, you have a $n\times n$ matrix, the first row is full of 1's the second row 1's except the first position, and so on... if you sum through columns you should have the sequence of the first $n$ integers.

Daniel Ordoñez
  • 844