TITLE: Calculate $\sum_{A,B \subset X} |A \cup B|$ for $|X|=n$
QUESTION [1 upvotes]: I need to calculate the sum $\sum_{A,B \subset X} |A \cup B|$ for $|X|=n$
Well I guess we can think of $X=\{1,...,n\}$. 
Well, in my opinion this is basically this.
$\sum_{k=1}^n {{n}\choose{k}}*2^{k-1}$, because first we choose which elements appear in the sum $A \cup B$ and then we find $2^k$ subsets that fullfill this. We divide it by two because we counted each subset twice (one for $B$ and one for $A$). 
And this sum can be easily deciphered using annihilators or generating functions.
Is my reasoning correct?

REPLY [1 votes]: An different answer (look my comment to see how you can adapt your solution):
Each element $x\in X$ is counted $2^{n-1}2^n+2^n2^{n-1}-2^{n-1}2^{n-1}$ times ($x\in A + x\in B - x\in (A\cap B)$).
The answer is then $n 2^{2(n-1)}(2+2-1)= 3 n 4^{n-1}$ (your formula simplifies to $(3^n-1)/2$ which is different).
{"set_name": "stack_exchange", "score": 1, "question_id": 667516}