For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$ Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that
$(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.)
The answer is all powers of 2, and it's fairly simple to see why they work, but the hard part is proving all non-powers of 2 don't work. In the solution, it says
"If $n$ is not a power of 2, say $n=2^i(2j+1),j\ge1$, then the smallest m for which $\binom{n}{m}$ is odd is $2^j$."
I don't see why. I know the highest power of $2$ in $\binom{n}{m}$ is $\sum_{k\ge1}[n/2^k]-[m/2^k]-[(n-m)/2^k]$ where $[.]$ is the greatest integer function. Also each summand is 0 or 1. It's 1 when the sum of fractional parts $\{m/2^k\} + \{(n-m)/2^k\}\ge1$, and 0 otherwise.
 A: The parity of a binomial coefficient can be quickly checked using Lucas' theorem.
Let $p$ be a prime. Write $n$ and $k$ in base $p$ as
$$
n=\sum_{\ell\ge0}n_\ell p^\ell,\qquad k=\sum_{\ell\ge0}k_\ell p^\ell
$$
with $0\le n_\ell,k_\ell <p$ for all $\ell$. Then we have the congruence
$$
{n\choose k}\equiv\prod_{\ell\ge0}{n_\ell\choose k_\ell}\pmod p,
$$
where we interpret a binomial coefficient as zero, if $k_\ell>n_\ell$ for some $\ell$.
For a proof see for example this answer.
In your case $p=2$, and the congruence tells you the parity: the binomial coefficient ${n\choose k}$ is odd, if and only if $n_\ell=1$ whenever $k_\ell=1$.
You have $n=2^i(2j+1)$, so we see that $n_\ell=0$ for all $\ell<i$ and $n_i=1$.
Therefore for the binomial coefficient ${n\choose k}$ to be odd, we must have $k_\ell=0$ for all $\ell<i$ also. The smallest positive integer $k$ with this property is, of course $k=2^i$. As then $k_\ell=0$ for all $\ell>i$, Lucas' theorem then tells us that ${n\choose k}$ is, indeed, an odd integer.
A: Slightly variant tact: observe that if $m>1$ is odd then in ${\bf F}_2[[x]]$ we may compute
$$\left(1+\sum_{k=0}^\infty x^{2^k}\right)^{2^lm}+\left(\sum_{k=0}^\infty x^{2^k}\right)^{2^lm}=\left(1+\sum_{k=l}^\infty x^{2^k}\right)^m+\left(\sum_{k=l}^\infty x^{2^k}\right)^m\equiv 1+x^{2^l}~\bmod x^{2^l+1}. $$
