Identity about generating function related to binary expression of integers For any nonnegative integer $n$, let $\mu(n)$ be $1$ if the binary expression of $n$ contains even number of ones; and $-1$ if the binary expression of $n$ contains odd number of ones. For example, $\mu(5)=1$, since $5=101$ in binary.
I want to show
$$\sum_{n = 0}^\infty \mu(n)x^n = \prod_{n = 0}^\infty \left(1-x^{2^n}\right) \tag{1}$$
by showing that
$$\prod_{n = 0}^{k} \left(1-x^{2^n}\right) = \sum_{n = 0}^{2^{k+1}-1} \mu(n)x^n, \tag{2}$$
for all nonnegative integer $k$ using induction on $k$.
For $k=0$, we have
$$\prod_{n=0}^0 (1-x^{2^n}) = 1-x = \mu(0)+\mu(1)x = \sum_{n=0}^{2^{0+1}-1} \mu(n)x^n.$$
Hence, the base case is done. Now, assume that $(1)$ holds for $k=m$. I want to show that $(1)$ holds for $k=m+1$. Notice that
\begin{align*}
\prod_{n=0}^{m+1}(1-x^{2^n}) &= (1-x)(1-x^2)\ldots(1-x^{2^m})(1-x^{2^{m+1}}) \\
&= (\mu(0)+\mu(1)x+\mu(2)x^2+\cdots+\mu(2^{m+1}-1)x^{2^{m+1}-1})(1-x^{2^{m+1}}) \\
&= \mu(0)+\mu(1)x+\mu(2)x^2+\cdots+\mu(2^{m+1}-1)x^{2^{m+1}-1}+\mu(2^{m+1})x^{2^{m+1}}+\mu(2^{m+1}+1)x^{2^{m+1}+1} \\
& \quad + \cdots + \mu(2^{m+2}-1)x^{2^{m+2}-1}
\end{align*}
holds if and only if
$$-\mu(i)=\mu(2^{m+1}+i) \tag{3}$$
for all $i \in \{0,1,2,\ldots,2^{m+1}-1\}$.
To show $(3)$, I use the relation (which is not proved yet)
$$\mu(2^{m+1}+i)=\mu(2^{m+1})\mu(i) \tag{4}$$
for all $i \in \{0,1,2,\ldots,2^{m+1}-1\}$.
This is because if $(4)$ holds, then Equation $(3)$ becomes
$$-\mu(i)=\mu(2^{m+1})\mu(i) \implies \mu(2^{m+1})=-1,$$
which is true for any nonnegative integer $m$.
On the other hand, I have a relation
$$\mu(n)=(-1)^{\sum_{j=0}^{\lfloor \log_2 (n+1) \rfloor} \lfloor \frac{n}{2^j} \rfloor} \qquad \tag{5}$$
for any nonnegative integer $n$. But also, I have no idea to prove this mathematically.
So here, my question is, how to show that the Equation $(4)$ hold? Also, how to show the relation $(5)$ mathematically?
I have no idea to prove it till now. Any idea please?
Many thanks in advanced for the helps.
 A: Hint:

*

*In (4) it's not nocessary to provide more details as its correctness is obvious. You could add some information with respect to binary representation if you like.

*

*On the one hand we have $\mu\left(2^{m+1}\right)=\mu\left(10^{m+1}_2\right)=-1$ as it contains just a single $1$ in binary notation.

*It follows $\mu\left(2^{m+1}+i\right)=-\mu\left(i\right), 0\leq i\leq 2^{m+1}-1$.



*In (5) it is sufficient to state that the right hand side counts the number of ones in binary notation which is just the definition of $\mu$.

Using a somewhat more compact notation we can write the proof by induction as follows:
The base step $k=0$ has already been shown.
Induction hypothesis: $k=m$ We assume
\begin{align*}
\prod_{n=0}^{m}\left(1-x^{2^{n}}\right)=\sum_{n=0}^{2^{m+1}-1}\mu(n) x^n\tag{1}
\end{align*}

Induction step: $k=m+1$
We obtain
\begin{align*}
\color{blue}{\prod_{n=0}^{m+1}}\color{blue}{\left(1-x^{2^{n}}\right)}
&=\prod_{n=0}^{m}\left(1-x^{2^{n}}\right)\left(1-x^{2^{m+1}}\right)\\
&=\prod_{n=0}^{m}\left(1-x^{2^{n}}\right)-x^{2^{m+1}}\prod_{n=0}^{m}\left(1-x^{2^{n}}\right)\\
&=\sum_{n=0}^{2^{m+1}-1}\mu(n) x^n-\sum_{n=0}^{2^{m+1}-1}\mu(n) x^{n+2^{m+1}}\tag{2.1}\\
&=\sum_{n=0}^{2^{m+1}-1}\mu(n) x^n+\sum_{n=2^{m+1}}^{2^{m+2}-1}\mu(n) x^{n}\tag{2.2}\\
&\,\,\color{blue}{=\sum_{n=0}^{2^{m+2}-1}\mu(n) x^{n}}
\end{align*}
and the claim follows.

Comment:

*

*In (2.1) we apply the induction hypothesis twice. Note, the left-hand sum of (2.1) contains as exponents of $x$ all non-negative numbers less than $2^{m+1}$, whereas the right-hand sum contains the same numbers as exponents each increased by $2^{m+1}$. This means in binary notation that each summand has precisely one bit additionally set, namely the most significant bit at position $m+2$ (counting starts from zero).


*In (2.2) we shift the index of the right-hand sum to start with $n=2^{m+1}$. We adopt the exponent of $x$ accordingly. We can still write $\mu(n)$ since we respect the additional power $2^{m+1}$ by merging the minus sign into it. The relationship between $\mu(n)$ in (2.1) and (2.2) is
\begin{align*}
\mu(n)=-\mu(n+2^{m+1})\qquad\qquad 0\leq n\leq 2^{m+1}-1
\end{align*}
Taking $m=1$ for instance we have
\begin{align*}
\mu(0)=-\mu(0+2^2)=-\mu(4)\\
\mu(1)=-\mu(1+2^2)=-\mu(5)\\
\mu(2)=-\mu(2+2^2)=-\mu(6)\\
\mu(3)=-\mu(3+2^2)=-\mu(7)\\
\end{align*}
which gives in binary notation
\begin{align*}
\mu(0_2)&=-\mu(0_2+100_2)=-\mu(100_2)\\
\mu(1_2)&=-\mu(1_2+100_2)=-\mu(101_2)\\
\mu(10_2)&=-\mu(10_2+100_2)=-\mu(110_2)\\
\mu(11_2)&=-\mu(11_2+100_2)=-\mu(111_2)\\
\end{align*}
