How to show that the following relation is valid for nested summation?

Question

I have seen following relation in a research paper $$\sum_{x_1=1,x_1\neq1}^{K}~\sum_{x_2=x_1+1,x_2\neq 1}^K\cdots \sum_{x_n=x_{n-1}+1,x_n\neq1}^Kf(x_1,x_2,\cdots,x_n)+\sum_{x_1=1,x_1\neq2}^{K}~\sum_{x_2=x_1+1,x_2\neq 2}^K\cdots \sum_{x_n=x_{n-1}+1,x_n\neq2}^Kf(x_1,x_2,\cdots,x_n)+\cdots \sum_{x_1=1,x_1\neq K}^{K}~\sum_{x_2=x_1+1,x_2\neq K}^K\cdots \sum_{x_n=x_{n-1}+1,x_n\neq K}^Kf(x_1,x_2,\cdots,x_n)=(K-n)\sum_{x_1=1}^{K}~\sum_{x_2=x_1+1}^K\cdots \sum_{x_n=x_{n-1}+1}f(x_1,x_2,\cdots,x_n).$$ Where $K$ and $n$ are some positive constants. I do not know how to prove that the left hand side is equal to the right hand side. Any help in this regard will be much appreciated. Thanks in advance.

Answer 1

We transform the left-hand side into a somewhat more convenient representation. This way we can better see why the equality is valid.

We obtain \begin{align*} \sum_{{x_1=1}\atop{x_1\ne 1}}^K&\sum_{{x_2=x_1+1}\atop{x_2\ne 1}}^K\cdots\sum_{{x_n=x_{n-1}+1}\atop{x_n\ne 1}}^Kf(x_1,x_2,\ldots,x_n)\\ &\qquad+\sum_{{x_1=1}\atop{x_1\ne 2}}^K\sum_{{x_2=x_1+1}\atop{x_2\ne 2}}^K\cdots\sum_{{x_n=x_{n-1}+1}\atop{x_n\ne 2}}^Kf(x_1,x_2,\ldots,x_n)\\ &\qquad\,\,\vdots\\ &\qquad+\sum_{{x_1=1}\atop{x_1\ne K}}^K\sum_{{x_2=x_1+1}\atop{x_2\ne K}}^K\cdots\sum_{{x_n=x_{n-1}+1}\atop{x_n\ne K}}^Kf(x_1,x_2,\ldots,x_n)\\ &=\sum_{{1\leq x_1<x_2<\cdots<x_n\leq K}\atop{x_j\ne 1, 1\leq j\leq n}}f(x_1,x_2,\ldots,x_n) +\sum_{{1\leq x_1<x_2<\cdots<x_n\leq K}\atop{x_j\ne 2, 1\leq j\leq n}}f(x_1,x_2,\ldots,x_n)\\ &\qquad+\cdots+\sum_{{1\leq x_1<x_2<\cdots<x_n\leq K}\atop{x_j\ne K, 1\leq j\leq n}}f(x_1,x_2,\ldots,x_n)\\ &=\color{blue}{\sum_{k=1}^K\sum_{{1\leq x_1<x_2<\cdots<x_n\leq K}\atop{x_j\ne k, 1\leq j\leq n}}f(x_1,x_2,\ldots,x_n)}\tag{1}\\ &\;\color{blue}{=(K-n)\sum_{1\leq x_1<x_2<\cdots<x_n\leq K}f(x_1,x_2,\ldots,x_n)}\tag{2}\\ &=(K-n)\sum_{x_1=1}^K\sum_{x_2=x_1+1}^K\cdots\sum_{x_n=x_{n-1}+1}^Kf(x_1,x_2,\ldots,x_n) \end{align*}

The crucial part is the step from (1) to (2). Let us consider in (2) a specific valid $n$-tupel $x^0=(x_1^0,x_2^0,\ldots,x_n^0)$ with $1\leq x_1^0<x_2^0<\cdots <x_n^0\leq K$ and ask how often it occurs in (1).

Since the first component in $x^0$ is $x_1^0$, the index $k=x_1^0$ is to exclude. Since the second component in $x^0$ is $x_2^0$, the index $k=x_2^0$ is to exclude. Continuing this way, we have to sum over $k\in\{1,2,\ldots,K\}\setminus\{x_1^0,x_2^0,\ldots,x_n^0\}$ in (1) and since $x_1^0<x_2^0<\cdots<x_n^0$ are $n$ different values, the $n$-tupel $x^0$ occurs precisely in $K-n$ inner sums of (1).

This holds for each $n$-tupel occurring in (2), so that the factor $K-n$ is justified.