Subsets of a set, symmetric differences of the form $\{ i , i + 1 \}$

Question

Let $A_i = \{i, i + 1\}$. Which subsets of $\{1, 2, 3, . . . , n \}$ can be written as the symmetric difference of a number of the sets $A_1, A_2, . . . A_{n−1}$?

Answer 1

The answer is that any subset which contains an even number of elements can be written as such a symmetric difference.

To prove that this is the case, it suffices to prove the following:

• If $S$ contains an even number of elements, then $S \triangle \{i,i+1\}$ also contains an even number of elements
• If $S$ contains an even number of elements, then we can write $S$ as a $k$-fold symmetric difference $S = A_{i_1} \triangle \cdots \triangle A_{i_k}$ for some $i_1,\dots,i_k$ between $1$ and $n-1$.