# How to find $\sum_{A \subset S} (\min A)$ and $\sum_{A \subset S} (\max A)$ if $S=\{1,2,…,n\}$?

Here, $\min A$ and $\max A$ denote the minimum and maximum element respectively of the set $A$.

So I have to calculate how many subsets of S have min/max element $1$, how many subsets have min/max element $2$, ... all the way upto $n$? I am not being able to intuitively understand the problem.

I want to know if there is an elegant way to do this.

• There are $2^{n-a}$ subsets whose minimal element is $a$ -- this is the number of subsets of $\{a+1,a+2,\ldots,n\}$. – Henning Makholm Jun 30 '16 at 16:43
• But which term in the sum will correspond to $A=\varnothing$? – Henning Makholm Jun 30 '16 at 16:43
• None. $\min$ and $\max$ are not defined in tihs case. – Daniel Jun 30 '16 at 16:46
• @HenningMakholm I'm afraid you have to break it down for me. – StubbornAtom Jun 30 '16 at 16:49
• For each $A$, let $\tilde{A}$ denote $n+1-A=\left\{n+1-a\,|\,a\in A\right\}$. Then, $\max(A)=n+1-\min\left(\tilde{A}\right)$. If you know $\sum\limits_{\substack{{A\subseteq S}\\{A\neq \emptyset}}}\,\max(A)$, then $$\sum_{\substack{{A\subseteq S}\\{A\neq \emptyset}}}\,\min(A)=(n+1)\left(2^n-1\right)-\sum_{\substack{{A\subseteq S}\\{A\neq \emptyset}}}\,\max(A)\,.$$ – Batominovski Jul 1 '16 at 11:09

You can work recursively. For the minimum: Denote the sum of the minimums with $m_n$ $$m_n:=\sum_{A\subset S_n}\min A$$ where $S_n=\{1,2,\dots,n\}$. Hence $S_n$ has $2^n$ subsets. Now consider the set $S_{n+1}=\{1,2,\dots,n,n+1\}$. The set $S_{n+1}$ has $2^{n+1}=2^n+2^n$ sets. The first $2^n$ sets are exactly the subsets of $S_n$ and the other $2^n$ are exactly the sets of $S_n$ with additionally the element $n+1$. So, the sum of the minimum of the first $2^n$ sets is again $m_n$ and the sum of the second $2^n$ is $m_n+(n+1)$ since $n+1$ is the minimum only of the set $\emptyset \cup \{n+1\}=\{n+1\}$. This gives you the recurrence relation $$m_{n+1}=2m_n+n+1$$ for $n\ge 1$, with $m_0=0$. Similarly, for the maximum you obtain the relation $$M_{n+1}=M_n+2^n(n+1)$$ for $n\ge 1$ with $M_0=0$.

To solve the recurrence relations, note that both are of the form $g_{n}=c\cdot g_{n-1}+f(n)$, for $n\ge 1$ with $g(0)=0$ (in the second case $c=1$ which makes things even simpler). For a general solution, rewrite this as $$\frac1{c^n}g_n=\frac{c}{c^n}g_{n-1}+\frac{f(n)}{c^n}\implies x_n=x_{n-1}+t(n)$$ with $x_n:=\dfrac{g_n}{c^n}$ and $t(n):=\dfrac{f(n)}{c^n}$. Hence, repeated substitution leads to $$x_n=x_{n-1}+t(n)=x_{n-2}+t(n-1)+t(n)=\cdots=x_0+\sum_{k=1}^nt(k)$$ Since in both cases the initial condition is $g_0=0$ you get here $$x_n=\sum_{k=1}^nt(k)\implies g_n=c^n\sum_{k=1}^nt(k)$$ or explicitly

1. For the $\min$ $($ here $c=2, f(n)=n)$: $$m_n=2^n\sum_{k=1}^n\frac{k}{2^k}=\dots=2^{n+1}-n-2$$

2. For the $\max$ $($ here $c=1, f(n)=2^{n-1}n)$: $$M_n=\sum_{k=1}^n2^{k-1}k=\dots=2^{n}(n-1)+1$$

Note. I assume that $m(\emptyset)=0$.

Question. Consider the set $S=\{1,2,3,\dots,j\}$. Let $m(A)$ denote a maximum element of a subset $A$ of $S$. Prove that $$\sum_{A\subseteq S}m(A) = (j-1)2^j+1$$ where summation ranges over all subsets $A$ of $S$.

Solution. Let us consider the element $4$. $4$ will be maximum element if we pick elements from the set $\{1,2,3,4\}$. So basically we want to count number of subsets of the set $\{1,2,3,4\}$ which contain the element $4$. This is the same as counting the number of subsets of $\{1,2,3\}$ and for each subset of $\{1,2,3\}$ we append the element $4$ to it. There are $2^3$ subsets of $\{1,2,3\}$, namely \begin{align*} \binom30 &= \{\emptyset\} \to \{4\}=\{4\}\\ \binom31 &= \{\{1\},\{2\},\{3\}\} \to \{4\}=\{\{1,4\},\{2,4\},\{3,4\}\}\\ \binom32 &= \{\{1,2\},\{1,3\},\{2,3\}\} \to \{4\}=\{\{1,2,4\},\{1,3,4\},\{2,3,4\}\}\\ \binom33 &= \{1,2,3\} \to 4=\{1,2,3,4\} \end{align*} So this gives us a one-one correspondence between the subsets of $\{1,2,3,4\}$ containing $4$ and the subset of $\{1,2,3\}$. So in general the subset of $\{1,2,3,\dots,j\}$ containing $j$ is in one-one correspondence between the subsets of $\{1,2,3,\dots,(j-1)\}$. Therefore the sum $$\sum_{A\subseteq S}m(A) = \sum_{i=1}^j i \cdot 2^{i-1}= (j-1)2^j+1.$$ Note $1\cdot1+2\cdot2+3\cdot2^3+4\cdot2^3+\dots+n\cdot2^{n-1}= \frac{d}{dx} (x+x^2+x^3+\dots+x^n)_{x=2}$

• Even if you are "too bored to tex", I think that mentioning the source of the image would be a useful information (and it would not require too much effort on your side). I suppose it is taken from some book. – Martin Sleziak Jul 1 '16 at 6:10
• @MartinSleziak This is not taken from a book. The same question was asked in a entrance exam couple of years ago. I tried solving it and sent the .pdf file to friends to share. Unfortunately I don't have the .tex file of that. I already told, in the beginning that I solved it. Why should I mention the source?? – crskhr Jul 1 '16 at 6:25
• @sc By source I meant the book from which the screenshot was taken. Now that you clarified that it is screenshot from the pdf you created and not from a book, this is no longer relevant. (And probably the page number should help me to guess that it is not from a book, if I had looked carefully enough. However, it seemed to me very likely that if this was from your own notes, you would have TeX-source, that's why asked.) In any case, since the screenshot looked like something from the book, it shows that you have TeX-ed it very nicely. – Martin Sleziak Jul 1 '16 at 6:32
• @MartinSleziak No problem. IF I had the TeX source I wouldn't be lazy to copy paste it here ;) – crskhr Jul 1 '16 at 6:35
• I have noticed that somebody downvoted your post - I am not sure whether the downvoter did this because of the picture instead of text or whether they had other reasons. In any case, I tried to edit the post based on your screenshot. It's up to you whether you will edit the text further. – Martin Sleziak Jul 1 '16 at 8:19