Assume $n$ is an even integer. For an odd integer $m$, a sequence of $m$ sets $S_1, \dots, S_m \subseteq [n]$ is a graceful chain of length $m$ if:
- $S_1 \subset S_2 \subset \dots \subset S_m$
- For every $1 \le i \le m − 1$ we have $|S_{i+1}| = |S_i| + 1$
- $|S_m| + |S_1| = n$.
Show that it is possible to decompose the $2^n$ subsets of $[n]$ using $\binom{n}{\frac{n}2}$ graceful chains.
Note: Of course, the chains do not have to be of the same length. Also, recall that by decomposition we mean that each of the $2^n$ sets $S \subseteq [n]$ should appear in exactly one of the graceful chains.