Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
an identity of floor function
08-05-2010, 10:31 AM
Post: #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$
Find all posts by this user
Quote this message in a reply
08-06-2010, 12:21 AM
Post: #2
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\)
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


Contact Us | Software Frontier | Return to Top | Return to Content | Lite (Archive) Mode | RSS Syndication