Could someone please help understand how this can be simplified? I don't understand how to solve/isolate the rightmost summation.
$$\sum_{i=1}^n \sum_{j=i}^n 1$$
Asked
Active
Viewed 513 times
0
-
7Hint: the inner sum contains a sum of $n-(i-1)$ $1’s$ so the sum is $n-(i-1)$. – insipidintegrator Jun 22 '22 at 18:04
-
2What are the pairs $(i,j)?$ They are the pairs $(i,j)$ with $1\leq i\leq j\leq n,$ each pair occurring exactly once. So you can rewrite the double sum as $$\sum_{j=1}^{n}\sum_{i=1}^j 1.$$ That might be easier. – Thomas Andrews Jun 22 '22 at 18:06
-
The title has a typo. – Dietrich Burde Jun 22 '22 at 18:17
-
2In general, $$\sum_{j=a}^b f(j)=\sum_{k=1}^{b-a+1} f(k+a-1).$$ In this case, when $f(n)=1,$ $$\sum_{k=1}^{b-a+1} 1=b-a+1.$$ – Thomas Andrews Jun 22 '22 at 18:17
-
Could you be specific, @DietrichBurde I edited the title, so if there is an error, I can fix it. – Thomas Andrews Jun 22 '22 at 18:18
-
2@ThomasAndrews The title says "double sum" but hasn't a double sum. – Dietrich Burde Jun 22 '22 at 18:19
-
For what it’s worth, we usually call the “right sum” the “inner sum.” – Thomas Andrews Jun 22 '22 at 18:19
-
@DietrichBurde Not so much a typo as a possible source of confusion - the body makes clear the source of the question is a double sum, even if the question is specifically about an inner (non-double) sum. – Thomas Andrews Jun 22 '22 at 18:21
-
@ThomasAndrews does that summation equality always work... I'm thinking that if our function is not linear, then we might be in trouble... right? – FafaDog Jun 22 '22 at 19:26
-
2No, you don’t need $f$ linear. The change of variables is $j=k+(a-1).$ When $j$ goes from $a$ to $b$ $k$ goes from $1$ to $b+1-a.$ @BigBear – Thomas Andrews Jun 22 '22 at 20:20
2 Answers
1
$$\begin{align} \sum_{i=1}^n \sum_{j=i}^n 1 &\stackrel{1.}= \sum_{i=1}^n (n+1-i) \\ &\stackrel{3.}= (n+1)\sum_{i=1}^n 1 - \sum_{i=1}^n i \\ &\stackrel{1., 2.}= (n+1)n - n(n+1)/2 \\ &\stackrel{3.}= n(n+1)/2 \end{align}$$
where
$\sum_{i=a}^b 1 = b-a+1$ provided $b\geqslant a$, i.e. there are $b-a+1$ integers in the set $\{a, a+1, ..., b\}$.
$\sum_{i=1}^n i = n(n+1)/2$ are triangular numbers.
Distributive law.
emacs drives me nuts
- 10,390
- 2
- 12
- 31
1
\begin{eqnarray} \sum_{j=i}^{n}1&=&\underbrace{1+1+\cdots+1}_{n-i+1\text{ times}}\\ &=&n-i+1\\ \sum_{i=1}^{n}\sum_{j=i}^{n}1&=&\sum_{i=1}^{n}n-i+1\\ &=&n(n+1)-\sum_{i=1}^{n}i\\ &=&n(n+1)-\dfrac{n(n+1)}{2}\\ &=&\dfrac{n(n+1)}{2} \end{eqnarray}