Let $X$ be a finite set. Recall that the power set of $X$ is the set of all subsets of $X$. We denote the power set of $X$ by $\mathcal{P}(X)$. It can be proved that, if $X$ has $n$ elements $(n \in \mathbb{N}_0)$, then $\lvert \mathcal{P}(X) \rvert = 2^n$.
Question. What is the value of $ \sum_{A \in \mathcal{P}(X)} \lvert \mathcal{P}(A) \rvert$?
I imagine there is a basic combinatorial identity that I - an humble programmer - am unaware of.
On
If $n=|X|$ denotes the size of the finite set $X$, then $$\begin{align}\sum_{A \in \mathcal{P}(X)} \lvert \mathcal{P}(A) \rvert&=\sum_{A\in P(X)}2^{|A|}\\&=\sum_{k=0}^n2^k\;|\{A\in P(X):|A|=k\}|\\&=\sum_{k=0}^n2^k\binom nk\\&=3^n\end{align}$$ (the last equality stems from the binomial formula).
Alternatively, you can find a very nice "direct" proof here, if you first realize that $$\sum_{B\in \mathcal P(X)}\lvert\mathcal P(B) \rvert= \lvert\{(A,B):A\subseteq B\subseteq X\}\rvert.$$
You must first find the distribution of sizes of the parts $A$ of $X$. This is conveniently expressed by the "size-generating polynomial" $P=\sum_{k=0}^nc_kY^k\in\Bbb{Z}[Y]$ where $c_k$ is the number of parts $A$ of $X$ of size $k$. You probably know that $c_k=\binom nk$ and therefore $P=\sum_{i=0}^n\binom{n}kY^k=(1+Y)^n$ by the binomial theorem. Now for every part $A$ of size $k$ you want to contribute $2^k$; since such a part contributed $1$ to the coefficient $c_k$ of $Y^k$, your summation simply becomes the result of substituting $Y=2$ into $P$; this gives $P[Y:=2]=(1+2)^n=3^n$ as value.