• 0 Votes - 0 Average
• 1
• 2
• 3
• 4
• 5
 an identity of floor function
08-05-2010, 10:31 AM
Post: #1
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
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$
08-06-2010, 12:21 AM
Post: #2
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
The Proof...
Notice that $$\left \lfloor \frac{a}{b} \right \rfloor - \left \lfloor \frac{a-1}{b} \right \rfloor=\begin{cases} 1& \text{ if }\; b \mid a\\ 0& \text{ if }\; b \nmid a \end{cases}$$
and $$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 there exists one and only one $$k$$ such that $$\left \lfloor \frac{n+2^k}{2^{k+1}} \right \rfloor - \left \lfloor \frac{n -1 +2^k}{2^{k+1}} \right \rfloor$$ not be zero but $$1$$.
Now the result follows from $$\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) =1$$
 « Next Oldest | Next Newest »

Forum Jump: