How do you solve $\sum_{k=0}^{\infty} \sum_{i=1}^{m-1} \left \lfloor \frac{x+im^k}{m^{k+1}} \right \rfloor$?

Question

Let $m > 1$ be an integer, x is a real number and $f(x)=\sum_{k=0}^{\infty} \sum_{i=1}^{m-1} \left \lfloor \frac{x+im^k}{m^{k+1}} \right \rfloor$

Do you have any idea how can I show this?

$f(x)= \begin{cases} \left \lfloor x \right \rfloor & \text{if } x\geq 0\\ \left \lfloor x+1 \right \rfloor & \text{if } x<0 \end{cases}$

Answer 1

Another solution: We will use the identity $\left \lfloor nx\right \rfloor = \sum_{k = 0}^{n - 1} \left \lfloor x + \frac{k}{n} \right \rfloor$,

$\sum_{k=0}^{\infty} \sum_{i=1}^{m-1} \left \lfloor \frac{x+im^k}{m^{k+1}} \right \rfloor = \sum_{k=0}^{\infty} \sum_{i=1}^{m-1} \left \lfloor \frac{x}{m^{k+1}} + \frac{i}{m} \right \rfloor = \sum_{k=0}^{\infty}( \sum_{i=0}^{m-1} \left \lfloor \frac{x}{m^{k+1}} + \frac{i}{m} \right \rfloor - \left \lfloor \frac{x}{m^{k+1}}\right \rfloor)$

Now we can apply the identity from above on $\frac{x}{m^{k+1}}$, and we are left with,

$\sum_{k=0}^{\infty} \left \lfloor m \frac{x}{m^{k+1}} \right \rfloor - \left \lfloor \frac{x}{m^{k+1}} \right \rfloor = \sum_{k=0}^{\infty} \left \lfloor \frac{x}{m^{k}}\right \rfloor - \left \lfloor \frac{x}{m^{k+1}}\right \rfloor$, this is just a telescoping series that converges to $\left \lfloor x\right \rfloor$ if we choose $x\geq0$.

If x is negative then $- \left \lfloor \frac{x}{m^{k+1}}\right \rfloor$ turns into $+ 1$ as $ \frac{x}{m^{k+1}}$ aproaches 0 from the left. So the result holds.

Answer 2

The key to solving the sum is realising that for any $k$ you can write $x$ uniquely as $x = m^{k+1} q_{k+1} + m^k r_{k}$ with $q_{k+1} \in \mathbb{Z}$ and $r_k \in [0, m) \subset \mathbb{R}$.

You can think of this as writing $x$ in base $m$ and splitting into two numbers corresponding to the first couple of digits and the remaining digits. For example if $x=1234.56$ and $m=10$ then $q_2 = 12$ and $r_{1} = 3.456$. We also have that $$m^{k+1} q_{k+1} + m^k r_k = m^k q_k + m^{k-1} r_{k-1} = m^{k+1} q_{k+1} + m^k ((q_k - m q_{k+1}) + r_{k-1} /m)$$ so $r_k = (q_k - m q_{k+1}) + r_{k-1}/m$ which implies $\lfloor r_k \rfloor = (q_k - m q_{k+1})$. Which makes sense if you think of the integral part of $r_k$ as the 'next digit'.

Motivation aside, this notation makes it possible to simplify the sum as follows:

$$ \begin{align} \sum_{k=0}^{\infty} \sum_{t=1}^{m-1} \left \lfloor \frac{x+tm^k}{m^{k+1}} \right \rfloor &= \sum_{k=0}^{\infty} \sum_{t=1}^{m-1} \left \lfloor \frac{m^{k+1} q_{k+1} + m^{k} r_{k} + tm^k}{m^{k+1}} \right \rfloor \\&= \sum_{k=0}^{\infty} \sum_{t=1}^{m-1} \left \lfloor q_{k+1} + \frac{(r_k +t)m^k}{m^{k+1}} \right \rfloor \\&= \sum_{k=0}^{\infty} \sum_{t=1}^{m-1} q_{k+1} + \left \lfloor \frac{r_k + t}{m} \right \rfloor \\ &= \sum_{k=0}^{\infty} (m-1) q_{k+1} + \lfloor r_k \rfloor\\ &= \sum_{k=0}^{\infty} (m-1) q_{k+1} + (q_k - mq_{k+1})\\ &= \sum_{k=0}^{\infty} q_k - q_{k+1} \end{align} $$

Now note that $$ \lim_{N\to\infty} \sum_{k=0}^{N} q_k - q_{k+1} = \lim_{N\to\infty} q_0 - q_N = q_0 = \begin{cases} \left \lfloor x \right \rfloor & \text{if } x\geq 0\\ \left \lfloor x+1 \right \rfloor & \text{if } x<0 \end{cases} $$