The coefficient of $x^m$ in $(1+x)^n$ is odd iff al the $1$'s in the binary representation of $m$ appear in the binary representation of $n$ as well. If to each positive integer $p$ we associate a finite subset $S(p)$ of $\mathbb N$ whose characteristic vector is the binary representation of $p$ (and we make $S(0)=\emptyset$), then that condition is written as $S(n)\supseteq S(m)$. The only thing for which we need $i_1<i_j,\ \forall j>1$ is that we can conclude $\forall j>1,\ A(i_1)\not\supseteq A(i_j)$. Let $A_j=A(i_j),\ \forall j\in\overline{1,n}$. For a system of finite sets $M_1,\ldots,M_k$ we denote by $o(M_1,\ldots,M_k)$ the number of subsets of $\bigcup_{i=1}^kM_i$ which are contained in an odd number of sets $M_i$. The problem is now this: $(*)$ Given finite sets $A_1,\ldots,A_n$ s.t. $\forall i>1,\ A_1\not\supseteq A_i$, we have $o(A_1,\ldots,A_n)\ge o(A_1)$. Suppose we prove $(*)$ in the particular case $A_1=\emptyset$ (we call this restricted statement $(**)$). Then we can extend our proof to one for the general case as follows: For any subset $M$ suppose $A_1,\ldots,A_p$ are the $A_i$’s which contain $M$. Then we apply $(**)$ to the system $\emptyset=\bar A_1,\bar A_2,\ldots,\bar A_p$, where $\bar A_j=A_j\setminus A_1$. The conclusion is that we can find $S_M\subset\bigcup\bar A_j$ contained in an odd number of $\bar A_j$’s. The collection consisting of all the sets of the form $S_M\cup M,\ M\subseteq A_1$ has at least $2^{|A_1|}=o(A_1)$ elements, all contained in an odd number of $A_i$’s, and we’re done. All that’s left now is to prove $(**)$, i.e. that for $A_1=\emptyset$ we have $o(A_1,\ldots,A_n)\ge 1$. We start with the maximal elements of the multiset $\{A_i\}$. If every maximal element (wrt inclusion) appears an even number of times, we take all of them out, and continue with the maximal elements in the multiset we’re left with. We repeat this procedure, shrinking the multiset we’re working with each time, until we first meet a maximal element (in the respective truncated multiset) which appears an odd number of times, and choose that one. We must reach a stage when there is a maximal element appearing an odd number of times, because in the worst case scenario we take all the $A_i$’s out except for $A_1=\emptyset$, and because of the condition $\forall i>1,\ A_1\not\supseteq A_i,\ \emptyset=A_1$ appears just once (and thus an odd number of times) in each of our multisets.

Let $D(n)$ denote te positions in which $n$ has digit $1$'s in base $2$. So $n = \sum_{x \in D(n)} 2^x$, for example $D(4)=\{2\}$, $D(5)=\{2,0\}$. Notice that the coefficient of $x^k$ in $Q_n$ is odd iff $D(k) \subseteq D(n)$. I will create an injection $f$ from the $k$'s that satisfy $D(k) \subseteq D(i_1)$ to the $k$'s that satisfy $D(k) \subseteq D(i_j)$ for an odd number of $j$'s. This will end the problem. First of all, $f(k)$ will satisfy that $D(f(k)) \cap D(i_1) = D(k)$ (that is, $f(k)$ will be $k$ plus some other digits $1$ that are not in $i_1$). This will guarantee injectivity, since if $f(k_1)=f(k_2)$ then $D(k_1) = D(f(k_1)) \cap D(i_1) = D(f(k_2)) \cap D(i_1) = D(k_2)$ so $k_1=k_2$. Now we must prove we can construct such an $f$ such that $D(f(k)) \subseteq D(i_j)$ for an odd number of $j$'s. To do this, take $k$. Let $1 \textless j_1, ..., j_m$ be such that $D(k) \subseteq D(i_{j_t})$ for all $ 1 \le t \le m$. If $m$ is even, then $D(f(k)) \subseteq D(i_r)$ for an odd number of $r$'s, so let $f(k)=k$, which satisfies $D(f(k)) \cap D(i_1) = D(k)$ since $D(k) \subseteq D(i_1)$. If $m$ is odd, this is where the difficulty of the problem lies Let $D$ be the set of positions in binary that are $0$ in $i_1$, but that are $1$ in $i_r$ for some $r$. (This second restriction is only included in order to make $D$ finite). Since $i_1$ is the least of all $i$'s, then $i_{j_t}>i_1$, and so $i_{j_t}$ must contain a digit $1$ in a position where $i_1$ doesn't (otherwise we would have $i_{j_t} \le i_1$). For each $1 \le t \le m$ let $X_t$ be the set of nonempty sets $Y$ that satisfy $Y \subseteq D \cap D(i_{j_t})$. Notice that $D \cap D(i_{j_t}) \ge 1$ since $i_{j_t}$ has digits $1$ that are $0$ in $i_1$. Since $Y$ cannot be empty, we have that $|X_t|$ must equal a power of $2$ minus 1, and therefore $X_t$ is odd for all $1 \le t \le m$. But recall that $m$ is odd. Therefore the sum of all $|X_t|$ is odd. But the sum of all $|X_t|$ equals $\sum_{Y \subseteq D} g(Y)$, where $g(Y)$ is the number of $t$'s such that $Y \in X_t$. Therefore, there must exist a nonempty subset $Y$ of $D$ such that $g(Y)$ is odd. We will have $f(k)$ be such that $D(f(k))=D(k) \cup Y$. Clearly $D(f(k)) \cap D(i_1) = D(k)$. Now we must prove $D(f(k)) \subseteq D(i_r)$ for an odd number of $r$'s. Notice that $D(f(k)) \subseteq D(i_r)$ is only possible if $r=j_t$ for some $t$, or $r=1$. Since $Y$ is a nonempty set of positions in binary which are $0$ in $i_1$, we have that $r=1$ does not work. Therefore, the number of $r$'s for which $D(f(k)) \subseteq D(i_r)$ is equal to $g(Y)$ (by definition), which is odd! Therefore we have constructed $f$ successfully! Huzzah! We are done.