Problem: Let $S$ be a set containing $n$ elements. Find $ \sum_{A \subseteq S} \sum_{B \subseteq S}|A \cap B| $ Solution: Observe that for any subsets $A,B\subseteq S$, we have that $ |A\cap B| =\sum_{x\in S}\mathbf{1}_{\{x\in A\cap B\}} =\sum_{x\in S}\mathbf{1}_{\{x\in A\}}\,\mathbf{1}_{\{x\in B\}}. $ Hence $ \sum_{A\subseteq S}\sum_{B\subseteq S}|A\cap B| =\sum_{A,B\subseteq S}\sum_{x\in S}\mathbf{1}_{\{x\in A\}}\,\mathbf{1}_{\{x\in B\}} =\sum_{x\in S}\sum_{A,B\subseteq S}\mathbf{1}_{\{x\in A\}}\,\mathbf{1}_{\{x\in B\}}. $ But for each fixed $x\in S$, $ \sum_{A\subseteq S}\mathbf{1}_{\{x\in A\}} =\bigl|\{A\subseteq S : x\in A\}\bigr| =2^{n-1}, $ since each of the other $n-1$ elements may freely be in or out of $A$. Likewise, $ \sum_{B\subseteq S}\mathbf{1}_{\{x\in B\}} =2^{n-1}. $ Therefore $ \sum_{A,B\subseteq S}\mathbf{1}_{\{x\in A\}}\,\mathbf{1}_{\{x\in B\}} =\bigl(2^{n-1}\bigr)\bigl(2^{n-1}\bigr) =4^{\,n-1}. $ Summing over all $x\in S$ gives $ \sum_{A\subseteq S}\sum_{B\subseteq S}|A\cap B| =\sum_{x\in S}4^{\,n-1} =n\,4^{\,n-1}. $