How do we show the equality of these two summations?

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

If you are not satisfied with Srivatsan's proof (which I think is 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)$. 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 similar to 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.

Else you prove it again by induction.

Answer 4

My answer is not mathematically rigorous but it should help visualizing other solutions. First of all, without loss of generality, the right hand side indexing 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 inside summations which can be shown as red areas on the left and right in the below picture respectively. (Pardon my quick drawing.)

From $i = 0$ 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.