Let $N$, $n$ be two natural numbers, with $N > n$. We define the set A as
$$
A = \{ x_1, x_2, x_3, …, x_N \}, x_1,…,x_N \in \mathbb{R}
$$
If we randomly pick $n$ elements from the set $A$, we have $N$ choose $n$ combinations. In other words, is it possible to pick $n$ elements from $A$ and observe that their sum, over all the possible combinations satisfies the following relation:
$$
\sum_{j = 1}^\binom{N}{n} \left( \sum_{j=1}^{n} x_j \right) = \binom{N-1}{n-1} \sum_{j=1}^{N} x_j
$$
I've checked this relation to be true in several cases, but the notation is somewhat not convincing… Can somebody please help me formalize better this concept?
Best Answer
Your sum notation is off, let $S(N,n)$ be the set of all $n$-size subsets of $\{1,2, \ldots,N\}$, there are $\binom{N}{n}$ many of them.
Then the sum you want is ( I think):
$$\sum_{S \in S(N,n)} \sum_{i \in S} x_i\tag{1}$$
and we can count it like this: for every $x_i$ (fixed), we can see that it is part of $\binom{N-1}{n-1}$ many distinct subsets from $S(N,n)$ and so added in a sum that many times, so contributes $x_i \binom{N-1}{n-1}$ to the total sum in $(1)$. As this holds for all elements $x_i$, $i \in \{1,\ldots,N\}$, the sum under $(1)$ equals
$$\binom{N-1}{n-1} \sum_{i=1}^N x_i$$
which is what I think you meant.