1

Let $S={1,2,...,j}$ be a set.For every nonempty subset of $A$ of $S$,let $m(A)$ denote the maximum element of $A$.Then find $$\sum_{\text{over all subsets of S}} m(A)$$

By seeing the answer I could easily prove inductively that the summation is equal to $$(j-1)2^j+1$$But I am facing difficulty actually evaluating it without knowing the result already.I tried to work with many cases but failed.Any ideas?Thanks.

Navin
  • 2,605
  • here is an idea to try. For any fixed $k$ with $1\le k\le j$, how many subsets are there for which $k$ is the maximum? For example, when $k=3$ then these subsets are ${3}, {1,3}, {2,3}, {1,2,3}$. – Mirko Feb 16 '17 at 18:27

1 Answers1

3

Order the elements of $S$ in decreasing order.

Take the first element $j$, which is the greatest, and find all the subsets of the set $S-\{j\}$ and put $j$ in every single of them. All of them would have $j$ as the maximum. The number of the subsets is $2^{j-1}$. Multiplying it by $j$ would give $j2^{j-1}$, which is part of $\sum_{\text{over all subsets of S}} m(A)$.

Do the same for $j-1$, for the set $S-\{j,j-1\}$. You get

$(j-1)2^{j-2}$

So, you need to calculate the following sum.

$\sum_{i=1}^{j}i2^{i-1}$

To do so, you may write it as a function of $x$

$f(x)=\sum_{i=1}^{j}ix^{i-1}$

Then, $F(x)=\sum_{i=1}^{j}x^{i}$ and $F'(x)=f(x)$

Using the sum of geometrical series formula

$F(x)=\frac{x^{j+1}-x}{x-1}$

$F'(x)=\frac{(x-1)[(j+1)x^j-1]-x^{j+1}+x}{(x-1)^2}$

Finally, you need to do the evaluation below

$f(2)=F'(2)$

Med
  • 2,530
  • Seems like a nice hint, also using the derivative, except when you evaluated $F'(x)$ you seem to have a typo and the simplification didn't work the same way when I tried it. At the very least, there should be no $n$ is the expression for $F'(x)$. Also, it seems the numerator of your formula for $F(x)$ is not correct, shouldn't it be $-1$ instead of $-x$? – Mirko Feb 16 '17 at 18:37
  • @Mirko, Thank you. I edited it. Hope it is correct now. – Med Feb 16 '17 at 18:39
  • well, I just corrected my first comment, adding that the $F$ you start with might be incorrect. (See above.) Did you do the simplifications all the way, to see that you get the correct answer (e.g. compare with the OP answer, and some easy to compute small $j$ answers)? ... it might be that your $F(x)$ is correct as is, I need to check (as summation starts at $1$, not $0$), will check one more time. – Mirko Feb 16 '17 at 18:40
  • I think your $F(x)$ is right, but $F'(x)$ is not yet right, even after the correction. Isn't it $F'(x)=\frac{jx^{j+1}-(j+1)x^j+1}{(x-1)^2}$? Then you get $F'(2)=j2^{j+1}-(j+1)2^j+1=2^j(2j-j-1)+1=2^j(j-1)+1$ as the OP suggests. – Mirko Feb 16 '17 at 18:53
  • @Mirko, I made a bad mistake. Thanks for caring. Please check again if it is right now. – Med Feb 16 '17 at 19:22
  • yes, what you have now is correct :) – Mirko Feb 16 '17 at 19:28