1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Your notation: two $j$'s on the left with totally different functions, and you want to sum over subsets not integers up to $\binom{N}{n}$. See my answer for a more reasonable notation.. $\endgroup$ Commented Mar 4, 2020 at 16:14

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .