Question: Why does $$ \frac{(1 + x)^{2^k - 1} - (1 - x^2)^{2^{k-1} - 1}(1-x)}{2^k} $$ have integer coefficients?
Details: For a question I'm thinking about, I needed to know all the real numbers $c$ such that the generating function $$ p(x) = \frac{(1 + x)^{2^k - 1}}{2^k} - c \cdot(1 - x^2)^{2^{k-1} - 1}(1-x) $$ is a polynomial with integer coefficients and constant term $0$ or $1$. Plugging in $x = 0$ reveals that $c = -\frac{1}{2^k}$ or $c = 1 - \frac{1}{2^k}$. Both of these $c$ values seem to work empirically for all $k$, but it is unclear to me why this is the case. Binomial formula gives the coefficient of $x^i$ (for, say, $i$ even) as $$ \frac{{{2^k - 1} \choose {i}} - (-1)^{i/2}{2^{k-1} - 1 \choose i/2} }{2^k} $$
But I don't think this expression is nice.
Also, a search on oeis reveals that $p(x)$ is related to Hamming Codes.
Note that $$ \frac{(1+x)^{2^{k+1}-1}-(1-x^2)^{2^k-1}(1-x)}{2^{k+1}} =(1+x)^{2^k-1}\frac{(1+x)^{2^k}-(1-x)^{2^k}}{2^{k+1}} $$ $\frac{(1+x)^{2^k}-(1-x)^{2^k}}{2}$ is the odd part of $(1+x)^{2^k}$. Therefore, we just need to show that $\left.2^k\,\middle|\,\binom{2^k}{j}\right.$ when $j$ is odd. The number of factors of $2$ in $\binom{2^k}{j}$ is the sum of the bits in the binary representation of $j$ plus the sum of the bits in the binary representation of $2^k-j$ minus the sum of the bits in the binary representation of $2^k$. When $j$ is odd, this is $k$.
100000000000$\leftarrow2^k$ has $k$ zeros on the right001100100101$\leftarrow j$ is odd, so it has a one on the right010011011011$\leftarrow2^k-j$ is the complement of $j$ plus one (has a one on the right)Except for the rightmost bit, all bits of $j$ and $2^k-j$ are complements. Since the rightmost bit is one in both, the sum of the bits in $j$ and $2^k-j$ is $k+1$. The sum of the bits in $2^k$ is $1$. Thus, there are $k$ factors of $2$ in $\binom{2^k}{j}$. That is, $\left.2^k\,\middle|\,\binom{2^k}{j}\right.$ when $j$ is odd.