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.

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.

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?

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.