Interesting identity $\sum_{A\subseteq X\\B\subseteq X}|A\cap B|=n4^{n-1}$

Question

Let $X = \{1,2,\dots,n\}$. Prove that the following identity holds: $$\sum_{A,B\subseteq X}|A\cap B|=n4^{n-1}$$

I noticed by using Inclusion-Exclusion formula that $$ \begin{aligned} \sum_{A\subseteq X\\B\subseteq X}|A\cap B| &=\sum_{A\subseteq X\\B\subseteq X}|A|+\sum_{A\subseteq X\\B\subseteq X}|B|-\sum_{A\subseteq X\\B\subseteq X}|A\cup B|\\ &=\sum_{A\subseteq X}|A|2^{n}+\sum_{B\subseteq X}|B|2^{n}-\sum_{A\subseteq X\\B\subseteq X}|A\cup B|\\ &=2^n\sum_{A\subseteq X}|A|+2^{n}\sum_{B\subseteq X}|B|-\sum_{A\subseteq X\\B\subseteq X}|A\cup B|\\ &=2^{n+1}\sum_{k=1}^nk\binom{n}{k}-\sum_{A\subseteq X\\B\subseteq X}|A\cup B| \end{aligned} $$ By using identity $\sum_{k=1}^nk\binom{n}{k}=n2^{n-1}$, we get: $$ \sum_{A\subseteq X\\B\subseteq X}|A\cap B|=n4^{n}-\sum_{A\subseteq X\\B\subseteq X}|A\cup B|$$ But now i am stuck.

Answer 1

You've written the sum in terms of an equally difficult sum, so it's not clear how to progress there.

To compute the sum directly, try writing it this way: $$\sum_{A\subseteq X\\B\subseteq X}|A\cap B| = \sum_{x\in X}\sum_{x\in A\cap B}1$$

For any $x$, there are exactly $2^{n-1}$ subsets of $X$ containing $x$, and we need to pick two of them, so there are $2^{n-1} \cdot 2^{n-1} = 4^{n-1}$ nonzero terms in the inner sum. So we get: $$\sum_{x\in X}\sum_{x\in A\cap B}1 = \sum_{x\in X} 4^{n-1} = n 4^{n-1}$$

Answer 2

Choose two sets $A$ and $B$ at random and independent. Let $X$ be $|A\cap B|$. Then $X = X_1+X_2+...+X_n$ where $X_i$ is indicator variable for element $i$, i.e. $X_i=1$ if $i\in A\cap B$ else $X_i=0$. So we have $$E(X) = E(X_1) +...+E(X_n) =n\cdot {(2^{n-1})^2\over (2^n)^2} ={n\over 4}$$

But $$E(X) = \sum{|A\cap B|\over (2^n)^2}$$ and thus a conclusion.