Results 1 to 10 of 10

Thread: an identity of floor function

  1. #1
    Member
    Joined
    Mar 2010
    From
    usa
    Posts
    91

    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$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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$.
    Last edited by Bruno J.; Aug 6th 2010 at 02:18 PM. Reason: Corrected my indices : I had used m_s, m_e, and m_k all for the same thing! Oops.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bruno J. View Post
    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 $?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    From
    usa
    Posts
    91
    $\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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by elim View Post
    $\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!).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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$.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 $
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by elim View Post
    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$
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    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} $
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Also sprach Zarathustra View Post
    $\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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Floor Function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 14th 2010, 11:44 AM
  2. Replies: 1
    Last Post: Dec 3rd 2009, 08:45 AM
  3. Replies: 4
    Last Post: Feb 21st 2009, 06:10 PM
  4. floor function - An Identity
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Jan 3rd 2009, 07:28 AM
  5. Floor function
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Dec 21st 2008, 10:13 PM

Search Tags


/mathhelpforum @mathhelpforum