# Thread: an identity of floor function

1. ## an identity of floor function

Prove that $\; n =\sum_{k=0}^{\infty} \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor, \; \forall n \in \mathbb{N}.\;$ where $\lfloor x \rfloor$ is the floor of $x$

2. Very nice! I can prove it, but I can't give any "deep" reason why it should be true. I'm sure there is a deep idea behind this formula.

By induction on $n$ : it's trivial for $n=1$, so suppose it holds for $n-1$. Write $n$ in binary as $n=2^{m_1}+\dots + 2^{m_s}$, with $m_1>\dots >m_s \geq 0$. We want to show that

$1 = \sum_{k=0}^{\infty} \left(\left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor - \left\lfloor \frac{n-1+2^k}{2^{k+1}} \right\rfloor\right)$.

Now for any positive $a, d$, we have
$\left \lfloor \frac{a}{d}\right\rfloor - \left \lfloor \frac{a-1}{d}\right\rfloor = \left\{\begin{array}{l} 1 \mbox{ if }d|a, \\ 0 \mbox{ otherwise}.\end{array}$

Thus it suffices to notice that there is only one $k$ for which $2^{k+1}|(n+2^k)$, namely $k=m_s$.

3. Originally Posted by Bruno J.
Very nice! I can prove it, but I can't give any "deep" reason why it should be true. I'm sure there is a deep idea behind this formula.

By induction on $n$ : it's trivial for $n=1$, so suppose it holds for $n-1$. Write $n$ in binary as $n=2^{m_1}+\dots + 2^{m_s}$, with $m_1>\dots >m_k \geq 0$. We want to show that

$1 = \sum_{k=0}^{\infty} \left(\left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor - \left\lfloor \frac{n-1+2^k}{2^{k+1}} \right\rfloor\right)$.

Now for any positive $a, d$, we have
$\left \lfloor \frac{a}{d}\right\rfloor - \left \lfloor \frac{a-1}{d}\right\rfloor = \left\{\begin{array}{l} 1 \mbox{ if }d|a, \\ 0 \mbox{ otherwise}.\end{array}$

Thus it suffices to notice that there is only one $k$ for which $2^{k+1}|(n+2^k)$, namely $k=m_e$.
Nice!

What exactly is the index $e$?

4. $(2^{k+1} \mid (n+2^k)) \Leftrightarrow \exists m \in \mathbb{N} (n+2^k = m 2^{k+1})\Leftrightarrow \exists m \in \mathbb{N} (n = (2m-1)2^k)$
So $k$ makes $2^k$ the max factor of n in power of $2$ which is, of course, unique.

5. Originally Posted by elim
$(2^{k+1} \mid (n+2^k)) \Leftrightarrow \exists m \in \mathbb{N} (n+2^k = m 2^{k+1})\Leftrightarrow \exists m \in \mathbb{N} (n = (2m-1)2^k)$
So $k$ makes $2^k$ the max factor of n in power of $2$ which is, of course, unique.
Yes, $m_s$ is what I meant (edited!).

6. Here is (I think!) an equivalent formula with $3$ instead :

$n=\sum_{k=0}^\infty \left \lfloor \frac{n+3^k}{3^{k+1}}\right\rfloor + \left \lfloor \frac{n+2\times 3^k}{3^{k+1}}\right\rfloor$.

7. I don't know if $p$ is necessarily set to be prime ,

We have

$n = \sum_{k=0}^{\infty} \sum_{i=1}^{p-1} \lfloor{ \frac{ n + i p^k}{p^{k+1} } \rfloor }$

First , write $n$ in base-p representation , ie :

$a_m a_{m-1} ... a_1 a_0 _{(p)}$ (that means , the coefficient of $p^k$ is $a_k$ )

Let $F(k) = a_m a_{m-1} ... a_k _{(p)}$

Then $\lfloor{ \frac{ n + i p^k}{p^{k+1} } \rfloor }$

$= F(k+1)$ if $a_k + i < p$

$= F(k+1) + 1$ if $a_k + i \geq p$

Consider $\sum_{i=1}^{p-1} \lfloor{ \frac{ n + i p^k}{p^{k+1} } \rfloor }$

We have first $p-1-a_k$ terms belonging to the first case and other belonging to the second ( because if $i \leq p-1-a_k$ , then $i + a_k \leq p-1 < p$ but the next term $[(p-1-a_k) + 1 ] + a_k = p$ so $p \geq p$ is true , the corresponding term should be in the second case . )

Therefore , we have $p-1 - (p-1-a_k) = a_k$ terms that belong to the second case and we can conclude that

$\sum_{i=1}^{p-1} \lfloor{ \frac{ n + i p^k}{p^{k+1} } \rfloor } = (p-1)F(k+1) + a_k$

Finally ,

$\sum_{k=0}^{\infty} \sum_{i=1}^{p-1} \lfloor{ \frac{ n + i p^k}{p^{k+1} } \rfloor }$

$= \sum_{k=0}^{\infty}[ (p-1)F(k+1) + a_k ]$

$= \sum_{k=1} a_k (p-1)( 1 + p + p^2 + ... p^{k-1} ) + \text{ sum of digits }$

$= \sum_{k=1} a_k( p^k - 1 ) + \text{ sum of digits }$

$= n - a_0 - \sum_{k=1} a_k + \text{ sum of digits }$

$= n$

8. Originally Posted by elim
Prove that $\; n =\sum_{k=0}^{\infty} \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor, \; \forall n \in \mathbb{N}.\;$ where $\lfloor x \rfloor$ is the floor of $x$
$[\frac{n+1}{2}]+[\frac{n+2}{2^2}]+...+[\frac{n+2^k}{2^{k+1}}]+...$

First it easy to show that the sum is finite.

Let us now write the above in another way:

$[\frac{n}{2}+\frac{1}{2}]+[\frac{n}{2^2}+\frac{1}{2}]+...+[\frac{n}{2^{k+1}}+\frac{1}{2}]+...$

Lemma:

For every $x\in \mathbb{R}$:

$[x+\frac{1}{2}]=[2x]-[x]$

Proof:

Every $x\in \mathbb{R}$ can be written:

$x=t+\frac{1}{2}+\theta$ or $x=t+\theta$, when $0 \leq\theta<\frac{1}{2}$ and $t\in \mathbb{Z}$

If $x=t+\theta$, then:

$[x+\frac{1}{2}]=[t+\theta +\frac{1}{2}]=t$

$[2x]=[2t+2\theta]=2t$

[x]=t

Hence:

$[x+\frac{1}{2}]=[2x]-[x]$

Now, if $x=t+\theta+\frac{1}{2}$, then:

$[x+\frac{1}{2}]=[t+\theta+1]=t+1$

$[2x]=[2t+1+2\theta]=2t+1$

$[x]=[t+\theta+\frac{1}{2}]=t$

Hence:

$[x+\frac{1}{2}]=[2x]-[x]$

Now, back to our problem...

$[\frac{n}{2}+\frac{1}{2}]+[\frac{n}{2^2}+\frac{1}{2}]+...+[\frac{n}{2^{k+1}}+\frac{1}{2}]+...$

$=[n]-[\frac{n}{2}]+[\frac{n}{2}]-[\frac{n}{4}]+[\frac{n}{2}]+...+[\frac{n}{2^k}]-[\frac{n}{2^{k+1}}]+...=[n]=n$

9. I can be shown for $x\in\mathbb{R}$ and $n\in\mathbb{N},\;n>1$

$\displaystyle \sum_{k=0}^{\infty} \sum_{i=1}^{n-1} \left\lfloor{ \frac{ x + i n^k}{n^{k+1} } \right\rfloor } = \begin{cases} \lfloor x\rfloor \text{, if } x\geq0 \\ \lceil x\rceil \text{, if } x<0,\; x\not\in\mathbb{Z} \\ x+1 \text{, if } x<0,\; x\in\mathbb{Z} \end{cases}$

10. Originally Posted by Also sprach Zarathustra
$[\frac{n+1}{2}]+[\frac{n+2}{2^2}]+...+[\frac{n+2^k}{2^{k+1}}]+...$
$[\frac{n}{2}+\frac{1}{2}]+[\frac{n}{2^2}+\frac{1}{2}]+...+[\frac{n}{2^{k+1}}+\frac{1}{2}]+...$

$=[n]-[\frac{n}{2}]+[\frac{n}{2}]-[\frac{n}{4}]+[\frac{n}{2}]+...+[\frac{n}{2^k}]-[\frac{n}{2^{k+1}}]+...=[n]=n$
Very nice! I like your proof better than mine.