25
$\begingroup$

Let $u_{b}(n)$ be equal to to number of odd digits of $n$ in base $b$.

For example:
In base $10$, $u_{10}(15074) = 3$
In base $13$, $u_{13}(15610) = u_{13}([7, 1, 4, 10]_{13}) = 2$

What is the value of $$\sum_{n=1}^\infty \frac{u_b(2^n)}{2^n}$$ I don't think there's a nice closed form solution in the general case.
But when the base is even, it seems that the sum evaluates to $\frac{1}{b-1}$.

I have no idea how to approach it. I tried thinking about the generating function. But I can't find a recurrence relation or any nice properties.

$\endgroup$
  • 1
    $\begingroup$ This is an incredible phenomenon $\endgroup$ – Stella Biderman Jan 30 '16 at 20:15
23
+400
$\begingroup$

Here is my solution:

If $a=\sum_{j\geq 0} a_j b^j$, then $u_b(a) = \frac{1}{2}\sum_j (1-(-1)^{a_j})$ because $1-(-1)^m=\begin{cases} 0 & 2\mid m\\ 2 & 2\nmid m\end{cases}$. Note that $a_j$ is the digit directly left of the decimal point in the $b$-adic expansion of $ab^{-j}$, i.e. $a_j = \lfloor ab^{-j} \rfloor \mod b$. Now if $b$ is even we can therefore replace $(-1)^{a_j}$ by $(-1)^{\lfloor ab^{-j} \rfloor}$.

Thus: $$\sum_{n\geq 1} 2^{-n} u_b(2^n) = \sum_{n\geq 1,j\geq 0} 2^{-n} \frac{1}{2} (1-(-1)^{\lfloor 2^n b^{-j}\rfloor})$$ Observe that for $j=0$ we always have $2^n b^{-j} \in 2\mathbb{N}$ so that all summands for $j=0$ vanish. Thus we assume $j\geq 1$ from now on.

Now we have to think about $2^n b^{-j}$. This suggests looking at the $2$-adic expansion of $b^{-j}$: $$b^{-j} =\sum_{n\geq 1} d_n 2^{-n}$$ for some $d_n\in\{0,1\}$ so that $\lfloor 2^n b^{-j} \rfloor \mod 2 = d_n$.

The nice thing about the digits $d$ of any $2$-adic expansion is that $\frac{1}{2}(1-(-1)^d)$ not just indicates whether or not $d$ is odd, it is actually equal to $d$, because $d\in\{0,1\}$. Therefore $\frac{1}{2}(1-(-1)^{\lfloor 2^{n} b^{-j} \rfloor})=\frac{1}{2}(1-(-1)^{d_n})=d_n$.

Thus: $$\sum_{j\geq 1} \sum_{n\geq 1} 2^{-n} \frac{1}{2}(1-(-1)^{\lfloor 2^n b^{-j} \rfloor}) = \sum_{j\geq 1} \sum_{n\geq 1} 2^{-n} d_n = \sum_{j\geq 1} b^{-j} = \frac{1}{b-1}$$ and that's what we wanted to prove.

$\endgroup$
  • $\begingroup$ That was an amazing proof. Much more simple than I imagined. $\endgroup$ – Kitegi Jan 31 '16 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.