Prove that $\sum\limits_{A\subseteq [n]}\sum\limits_{B\subseteq [n]} |A\cap B|=n4^{n-1}$ I want to prove the following.
$$\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} |A\cap B|=n4^{n-1}$$
Here is what I have thought of so far:
We can treat subsets of $[n]=\{1,2, \ldots, n\}$ as sequences consisting of $1$s and $0$s, where $1$ in the $k$th entry indicates that $k$ is in the subset and a $0$ indicates it is not. 
When comparing two subsets $A,B \subseteq [n]$ at a particular $k$th entry, there are $4$ possibilities: 
1) both $A$ and $B$ have a $1$ at the $k$th entry,
2) $A$ has a $0$ and $B$ has a $1$ at the $k$th entry,
3) $A$ has a $1$ and $B$ has a $0$ at the $k$th entry,
4) both $A$ and $B$ have a $0$ at the $k$th entry.
Since $0\leq k \leq n$ then there are $4^n$ possibilities in total. However, for each $k$ only one possibility contributes to the sum, namely possibility (1), so we must divide by 4 to count each of the four possibilities as $1$, which is how I believe we have $4^{n-1}$.
Maybe this is a bogus explanation but I fail to see where the $n$ comes from.
 A: Consider a random experiment, where I pick two n-bit strings $X$ and $Y$ independently and uniformly at random from $\{0,1\}^n$ and count the number of coordinates in which both of the strings is one. Let us identify subsets of $[n]$ with $n$-bit strings. We have
\begin{align*}
\mathbb E[|X\cap Y|] = \sum_{i=1}^n\mathbb E[|X_i\cap Y_i|]
\end{align*}
by using the fact that expectation is linear. Now if you toss two coins independently, the probability that they are both heads is $1/4$, therefore $\mathbb E[|X_i\cap Y_i|]=1/4$. Summing over $n$ indices and normalizing by $2^n\times 2^n$, we obtain the identity you desire.
A: You can prove this by induction.
Let $S_n = \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} |A\cap B|,$ where $[n] = \lbrace 1, \dots, n \rbrace.$  (We're taking $[0]$ to be the empty set.)
For $n\ge 0,$ the subsets of $[n+1]$ that contain $n+1$ as a member are precisely the sets of the form $A \cup \lbrace n+1 \rbrace,$ where $A$ is a subset of $[n].$
The subsets of $[n+1]$ that do not contain $n+1$ as a member are precisely the subsets of $[n].$
So
\begin{align}
S_{n+1} &= \sum_{A\subseteq [n+1]}\sum_{B\subseteq [n+1]} \mid A\cap B \;\mid
\\ &= \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid 
\\ & \hphantom{===} + \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid(A\cup \lbrace n+1 \rbrace)\cap B\;\mid 
\\ & \hphantom{===}+ \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap (B\cup \lbrace n+1 \rbrace)\;\mid \\ & \hphantom{===}+ \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid(A\cup \lbrace n+1 \rbrace)\cap (B\cup \lbrace n+1 \rbrace)\;\mid
\\ &= \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid 
\\ & \hphantom{===}+\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid
\\ & \hphantom{===}+\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid
\\ & \hphantom{===}+\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \big(1+\mid A\cap B\;\mid\big)
\\ &= \left(\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} 1\right) + 4 \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid
\\ &= 2^n 2^n + 4 \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid
\\ &= 4^n + 4 S_n.
\end{align}
With this formula in hand to express $S_{n+1}$ in terms of $S_n,$ it's easy to use induction to verify that $S_n=n\cdot 4^{n-1}$ for all non-negative integers $n\!:$
The basis $S_0=0$ is trivial.
Assuming $S_n=n\cdot 4^{n-1}$ as induction hypothesis, we have
\begin{align}
S_{n+1} &= 4^n + 4 S_n
\\ &= 4^n + 4 (n\cdot 4^{n-1})
\\ &= 4^n + n \cdot 4^n
\\ &= (n+1)4^n,
\end{align}
as desired.
A: *

*The number $k$ of elements in $A\cap B$ may vary from $0$ to $n$. Since there are $\binom{n}{k}$ possibilities to select subsets of size $k$ from $[n]$, the contribution is
\begin{align*}
\sum_{k=0}^nk\binom{n}{k}
\end{align*}

*To each selection $A\cap B$ of size $k$ the size of $A$ may vary from $k$ up to $n$. There are $\binom{n-k}{j}$ possibilities to complete $A$ with $0\leq j\leq n-k$ elements. The contribution is
\begin{align*}
\sum_{j=0}^{n-k}\binom{n-k}{j}
\end{align*}

*To each selection $A$ of size $k+j, 0\leq k\leq n, 0\leq j\leq n-k$ we can select up to $n-k-j$ elements from $[n]$ which are not in $A$ to complete $B$. There are $2^{n-k-j}$ possibilities to do so.

Putting all together gives:
  \begin{align*}
\sum_{A\subset[n]}\sum_{B\subset[n]}|A\cap B|&=\sum_{k=0}^nk\binom{n}{k}\sum_{j=0}^{n-k}\binom{n-k}{j}2^{n-k-j}
\end{align*}
We obtain for $n\geq 1$:
\begin{align*}
\sum_{k=0}^nk\binom{n}{k}\sum_{j=0}^{n-k}\binom{n-k}{j}2^{n-k-j}
&=\sum_{k=0}^nk\binom{n}{k}\sum_{j=0}^{n-k}\binom{n-k}{j}2^{j}\tag{1}\\
&=\sum_{k=1}^nk\binom{n}{k}3^{n-k}\tag{2}\\
&=n\sum_{k=1}^n\binom{n-1}{k-1}3^{n-k}\tag{3}\\
&=n\sum_{k=0}^{n-1}\binom{n-1}{k}3^{n-1-k}\tag{4}\\
&=n4^{n-1}
\end{align*}
and the claim follows.

Comment:


*

*In (1) we change the order of summation in the inner sum by: $j\rightarrow n-k-j$.

*In (2) we apply the binomial theorem.

*In (3) we apply the binomial identity $k\binom{n}{k}=n\binom{n-1}{k-1}$.

*In (4) we shift   the  index  to start   from $k=0$    and     apply the binomial theorem again.
A: Each $k\in[n]$ is counted once in the double summation for each ordered pair $\langle A,B\rangle$ of subsets of $[n]$ such that $k\in A\cap B$. Fix $k\in[n]$, and let 
$$\mathscr{P}_k=\{\langle A,B\rangle\in[n]\times[n]:k\in A\cap B\}\;.$$
The map
$$\varphi:\big([n]\setminus\{k\}\big)\times\big[n]\setminus\{k\}\big)\to\mathscr{P}_k:\langle A,B\rangle\mapsto\langle A\cup\{k\},B\cup\{k\}\rangle$$
is a bijection, so 
$$|\mathscr{P}_k|=\left|\big([n]\setminus\{k\}\big)\times\big[n]\setminus\{k\}\big)\right|=\left(2^{n-1}\right)^2=4^{n-1}\;.$$
Thus, each $k\in[n]$ is counted $4^{n-1}$ times in the double summation, which must therefore be equal to $n4^{n-1}$.
The argument can also be carried out as a manipulation of summations:
$$\begin{align*}
\sum_{A\subseteq[n]}\sum_{B\subseteq[n]}|A\cap B|&=\sum_{A\subseteq[n]}\sum_{B\subseteq[n]}\sum_{k\in A\cap B}1\\
&=\sum_{k\in[n]}\sum_{k\in A\subseteq[n]}\sum_{k\in B\subseteq[n]}1\\
&=\sum_{k\in[n]}\sum_{k\in A\subseteq[n]}2^{n-1}\\
&=\sum_{k\in[n]}\left(2^{n-1}\cdot2^{n-1}\right)\\
&=\sum_{k\in[n]}4^{n-1}\\
&=n4^{n-1}
\end{align*}$$
