Identity about generating function related to binary expression of integers

Question

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.

Answer 1

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*}