Strange Summation Identity

Question

I was looking at the Summation wikipedia(https://en.m.wikipedia.org/wiki/Summation) and found this rather strange identity: $$ \sum_{k\leq j\leq i\leq n} a_{i,j}=\sum_{i=k}^n\sum_{j=k}^i a_{i,j}=\sum_{j=k}^n\sum_{i=j}^n a_{i,j}=\sum_{j=0}^{n-k}\sum_{i=k}^{n-j} a_{i+j,i} $$ Can someone please explain me what the term before the first equal to sign mean and provide me with a proof of above?

Answer 1

The first term refers to a sum over all $a_{i, j}$ such that both indices $i$ and $j$ are between $k$ and $n$, but $j$ is less or equal to $i$. For example, if $k = 1$ and $n = 3$, we must sum the terms $a_{1, 1}, a_{2, 1}, a_{3, 1}$ and $a_{3, 2}$. Notice that the first index ($i$) is always greater or equal to the second one ($j$), so the summation doesn't account for terms like $a_{1, 2}$.

The first equal sign is just saying that performing this summation is the same thing as fixing the index $i$ and summing all the terms with index $j$ less or equal to $i$. We start by fixing $i = 1$ and performing the summation over $j$, then we set $i = 2$ and perform the summation over $j$ again and so on.

The validity of the second equal sign may be achieved by a similar reasoning, but now we change the order: we fix a index $j$ and sum all the index $i$ greater or equal $j$. This is possible because sum is commutative, so we may exchange the order like this.

The last term is a little bit different. The meaning of the variables has changed. Now, j is the difference between the first and second indices, so we are fixing the difference. For example, $j = 0$ means that we must sum all the pair of indices that have a difference of zero: (1, 1), (2, 2)... For $j = 1$ refers to the pairs that have a difference of 1: $(2, 1), (3, 2)$, etc. Notice that, as $j$ is positive, the first index which now is $i + j$, is necessarily greater than the second one, which is exactly what we wanted.

In the end of the day, all these summations are just different ways of performing a sum over the same set of indices, but written in different representations.