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. 
 A: 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}$
A: 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


*

*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$$

*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$$
