Construct a Circuit computing all boolean functions over n bits
Given the circuit $C_n$, you can compute $C_{n+1}$ using $O(2^{2^{n+1}})$ additional gates. Indeed, each output gate of $C_{n+1}$ is of the form
$$
(\lnot x_{n+1} \land y_i) \lor (x_{n+1} \land y_j)
$$
for some $i,j$, so can be computed from the outputs of $C_n$ using $O(1)$ additional gates.

In total, the circuit $C_n$ uses $O(2^{2^n} + 2^{2^{n-1}} + \cdots) = O(2^{2^n})$ gates.