# How do we show the equality of these two summations?

How do you show the following? $$\sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1 = \sum \limits_{j=1}^{n}\ \sum \limits_{k=1}^{j}\ \sum \limits_{i=1}^{k}\ 1$$ It's not obvious why this is true, but I have tested it with a program and it works.

-
I am just passing by and wow... It's like 1000 times more tedious to post an answer on math SE than on stackoverflow (auto syntax coloring, indentation etc)! kudos to all math SE answerers! – Jake Nov 1 '11 at 7:56

Both count the cardinality of the set $\{ (i, j, k) \in \mathbb Z^3 \mid 1 \leq i \leq k \leq j \leq n \}$.

Explanation. We try to count the set $$S := \{ (i, j, k) \in \mathbb Z^3 \mid 1 \leq i \leq k \leq j \leq n \}$$ in two ways.

Right hand side.

1. First fix the largest item of the triple, namely $j$; this can take values from $1$ to $n$. Then we fix $k$ and $i$ in that order.

2. For any given value of $j$, the variable $k$ can take values from $1$ to $j$ (since we know that $1 \leq k \leq j$).

3. Given the values of $k$ and $j$, the variable $i$ can take values from $1$ up to the smaller of $k$ and $j$, namely $k$ (since we know that $i \leq k$ and $i \leq j$).

Can you see how the right hand side expression corresponds to the above explanation?

Left hand side. We adopt a similar strategy of fixing the values of variables one at a time. But this time, we fix them in the order $i, j, k$.

1. As before, $i$ takes values from $1$ to $n$.

2. Once we fixed the value of $i$, it's clear that $j$ takes values from $i$ to $n$.

3. Given the values of $i$ and $j$, the variable $k$ takes values in the range $[i, j]$.

If you write this down in terms of the summation notation, do you see how you get the left hand side?

-
I am looking for a more rigorous explanation. Could you elaborate a little more? – Mark Nov 1 '11 at 0:58
@Mark I have added an explanation. Is it clearer now? – Srivatsan Nov 1 '11 at 1:12
Yes, it clearer now, I have accepted the answer, but do you know a more visual explanation or a more general approach to construct these types of summations? – Mark Nov 1 '11 at 1:22
@Mark A visual proof is implicit in Sivaram's answer. For e.g., if you want to visualize $\sum_{i=1}^n \sum_{j=i}^n 1 = \sum_{j=1}^n \sum_{i=1}^j n$, then you can visualize the diagonal $i=j$ (in the "$i$-$j$ plane"), and count all the lattice points either on the diagonal (i.e., $i=j$) or above it (i.e., $i < j$). – Srivatsan Nov 1 '11 at 1:37

This looks like a pretty good excuse to switch to Iverson brackets. Letting $[p]$ be $1$ if $p$ is true, and $0$ if $p$ is false, we express the sum on the left as

$$\sum_i\sum_j\sum_k [1 \leq i \leq n][i \leq j \leq n][i \leq k \leq j]$$

where the sum is taken over all $i,j,k$. This can be rightly taken as an infinite triple series with nonnegative terms: the Iverson brackets ensure that terms that weren't present in the original series are nicely zeroed.

Using the fact that $[p][q]=[p\text{ and }q]$, we have the equivalent expression

$$\sum_i\sum_j\sum_k [1\leq i\leq k\leq j\leq n]=\sum_j\sum_k\sum_i [1\leq i\leq k\leq j\leq n]$$

where we were free to permute the order of summation.

We can slowly peel Iverson factors out like so:

\begin{align*}\sum_j\sum_k\sum_i [1\leq i\leq k\leq j\leq n]&=\sum_j\sum_k\sum_i [1\leq i\leq k][1\leq k\leq j\leq n]\\&=\sum_j\sum_k\sum_i [1\leq i\leq k][1\leq k\leq j][1\leq j\leq n]\\&=\sum_j[1\leq j\leq n]\sum_k[1\leq k\leq j]\sum_i [1\leq i\leq k]\end{align*}

and the last expression is precisely the sum on the right, rewritten in Iversonian form.

-
+1 I would say this is the most convincing. =) – Srivatsan Nov 1 '11 at 1:43
Let us all thank Iverson and Knuth for making reindexing proofs easy. :) Sadly, it's a technique that is underappreciated by the people who need it the most. – J. M. Nov 1 '11 at 1:44

My answer is not mathematically rigorous, but it should help in visualizing the other solutions. First of all, without loss of generality, the indexing of the right hand side can be changed to match the left hand side as follows:

$$\sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1 = \sum \limits_{i=1}^{n}\ \sum \limits_{j=1}^{i}\ \sum \limits_{k=1}^{j}\ 1$$

Now the difference lies in two inner summations, which can be shown as red areas on the left and right respectively in the picture below. (Pardon my quick drawing.)

From $i = 1$ to $n$, the left hand side starts from the biggest triangle to the smallest, while the right hand side does the opposite. It is clear that both summations are the same.

-

If you are not satisfied with Srivatsan's proof (which I think is more elegant than mine), you can prove it by induction on $n$.

$$f(n) = \sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1,$$ $$g(n) = \sum \limits_{j=1}^{n}\ \sum \limits_{k=1}^{j}\ \sum \limits_{i=1}^{k}\ 1.$$

You want to prove $f(n) = g(n)$. This is easy to check for $n=1$.

For the induction step, note that $$f(n+1) = f(n) + \sum_{i=1}^{n+1} \sum_{k=i}^{n+1} 1$$ and $$g(n+1) = g(n) + \sum_{k=1}^{n+1} \sum_{i=1}^{k} 1$$

To prove $$\sum_{i=1}^{n+1} \sum_{k=i}^{n+1} 1 = \sum_{k=1}^{n+1} \sum_{i=1}^{k} 1$$, you can argue similarly with Srivatsan's earlier argument. Both count the number of lattice points on and above the diagonal of the square with vertices at $(0,0),(0,n+1),(n+1,n+1)$ and $(n+1,0)$ in the $i$-$k$ plane.

Otherwise, you prove it again by induction.

-

The idea of my answer is to unscramble the three summations on either the LHS or RHS into inequalities. Then, I use the unscrambled identity to rewrite the other side differently. WLOG, I'll start on the RHS.
RHS = $\underbrace{\sum \limits_{\color{darkorange}{j}=1}^{n}}_{1 \leq \color{darkorange}{j} \leq n} \underbrace{\sum \limits_{\color{darkorange}{k}=1}^{j}}_{1 \leq \color{darkorange}{k} \leq j} \underbrace{\sum \limits_{\color{darkorange}{i}=1}^{k}}_{1 \leq \color{darkorange}{i} \leq k} 1$

$\Longrightarrow 1 \leq j \leq n \, \& \, 1 \leq \color{limegreen}{k \leq j} \, \& \, 1 \leq \color{red}{i \leq k}$
$\Longrightarrow 1 \leq i \color{red}{\leq} k \color{limegreen}{\leq} j \leq n \tag{*}$

The key is just to rewrite the combined inequality above into three separate inequalities. To get different summation limits, I must ensure that at least one of the new inequalities must differ from those in (*).

1. Thus, I must fix either $i$ or $k$ first. WLOG, I choose $k$: $1 \leq k \leq n. \tag{**}$
2. After fixing $k$, I must fix either $i$ or $j$. WLOG, choose $j$: $k \color{limegreen}{\leq} j \leq n$
3. After fixing $j$ and $k$, $i$ remains to be fixed: $1 \leq i \color{red}{\leq} k$.

The above gives $\sum \limits_{k=1}^{n} \sum \limits_{j=k}^{n}\ \sum \limits_{1=i}^{k} 1$, NOT the LHS, but another way to rewrite the summation limits.

1. To get the LHS, I realise that I had needed to fix $i$ first in (**): $1 \leq i \leq n.$
2. After fixing $i$, I must fix either $j$ or $k$. WLOG, choose $j$: $i \color{limegreen}{\leq} j \leq n$
3. After fixing $i$ and $j$, $k$ remains to be fixed: $i \color{red}{\leq} k \color{limegreen}{\leq} j$.

Steps #4-6 yield the LHS = $\sum \limits_{i=1}^{n}\ \sum \limits_{j=i}^{n}\ \sum \limits_{k=i}^{j}\ 1$.

-