# 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.

• Since there are $n$ values of $k$ (from $1$ to $n$)? Commented Sep 21, 2016 at 4:31
• You can rewrite your sum as $\sum_{k\leq n} \binom nk k 3^{n-k}$. Thinking combinatorially will help. Commented Sep 21, 2016 at 4:36
• @i707107 I sort of see where you're coming from. There are $\binom{n}{k}$ possible $k$-subsets of $[n]$. For each of the $k$ entries of each of these subsets there are $3^{n-k}$ possibilities of something...Well, $n-k$ is the number of elements not in the $k$-subset...I still don't see where the $3$ comes from.
– Ana
Commented Sep 21, 2016 at 4:41
• The remaining $n-k$ elements should be distributed into three disjoint sets $A\cap B^c$, $B\cap A^c$ and $[n] - (A\cup B)$. Commented Sep 21, 2016 at 4:43
• Note that, for every set $S$, $$|S|=\sum_x[x\in S]$$ and that, for every $x$, $A$, $B$, $$[x\in A\cap B]=[x\in A]\cdot[x\in B]$$ hence the sum of interest is $$\sum_A\sum_B\sum_x[x\in A]\cdot[x\in B]=\sum_x\left(\sum_A[x\in A]\right)^2$$ Each inner sum enumerates the subsets of $[n]$ containing $x$, there are $2^{n-1}$ of them hence the sum of interest is $$\sum_x\left(2^{n-1}\right)^2=4^{n-1}\sum_x1=4^{n-1}\cdot n$$
– Did
Commented Sep 21, 2016 at 5:45

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.

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.

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

• 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.