# Thread: an identity of floor function

1. ## an identity of floor function

Prove that $\displaystyle \; n =\sum_{k=0}^{\infty} \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor, \; \forall n \in \mathbb{N}.\;$ where $\displaystyle \lfloor x \rfloor$ is the floor of $\displaystyle 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 $\displaystyle n$ : it's trivial for $\displaystyle n=1$, so suppose it holds for $\displaystyle n-1$. Write $\displaystyle n$ in binary as $\displaystyle n=2^{m_1}+\dots + 2^{m_s}$, with $\displaystyle m_1>\dots >m_s \geq 0$. We want to show that

$\displaystyle 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 $\displaystyle a, d$, we have
$\displaystyle \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 $\displaystyle k$ for which $\displaystyle 2^{k+1}|(n+2^k)$, namely $\displaystyle 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 $\displaystyle n$ : it's trivial for $\displaystyle n=1$, so suppose it holds for $\displaystyle n-1$. Write $\displaystyle n$ in binary as $\displaystyle n=2^{m_1}+\dots + 2^{m_s}$, with $\displaystyle m_1>\dots >m_k \geq 0$. We want to show that

$\displaystyle 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 $\displaystyle a, d$, we have
$\displaystyle \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 $\displaystyle k$ for which $\displaystyle 2^{k+1}|(n+2^k)$, namely $\displaystyle k=m_e$.
Nice!

What exactly is the index $\displaystyle e$?

4. $\displaystyle (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 $\displaystyle k$ makes $\displaystyle 2^k$ the max factor of n in power of $\displaystyle 2$ which is, of course, unique.

5. Originally Posted by elim
$\displaystyle (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 $\displaystyle k$ makes $\displaystyle 2^k$ the max factor of n in power of $\displaystyle 2$ which is, of course, unique.
Yes, $\displaystyle m_s$ is what I meant (edited!).

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

$\displaystyle 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 $\displaystyle p$ is necessarily set to be prime ,

We have

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

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

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

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

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

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

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

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

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

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

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

Finally ,

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

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

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

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

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

$\displaystyle = n$

8. Originally Posted by elim
Prove that $\displaystyle \; n =\sum_{k=0}^{\infty} \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor, \; \forall n \in \mathbb{N}.\;$ where $\displaystyle \lfloor x \rfloor$ is the floor of $\displaystyle x$
$\displaystyle [\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:

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

Lemma:

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

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

Proof:

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

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

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

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

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

[x]=t

Hence:

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

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

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

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

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

Hence:

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

Now, back to our problem...

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

$\displaystyle =[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 $\displaystyle x\in\mathbb{R}$ and $\displaystyle n\in\mathbb{N},\;n>1$

$\displaystyle \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
$\displaystyle [\frac{n+1}{2}]+[\frac{n+2}{2^2}]+...+[\frac{n+2^k}{2^{k+1}}]+...$
$\displaystyle [\frac{n}{2}+\frac{1}{2}]+[\frac{n}{2^2}+\frac{1}{2}]+...+[\frac{n}{2^{k+1}}+\frac{1}{2}]+...$

$\displaystyle =[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.