Results 1 to 10 of 10

Math Help - an identity of floor function

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

    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
    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 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.
    Last edited by Bruno J.; August 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 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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    From
    usa
    Posts
    83
    (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.
    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
    (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!).
    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 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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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
    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 \; 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
    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  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}
    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
    [\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.
    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: November 14th 2010, 11:44 AM
  2. Replies: 1
    Last Post: December 3rd 2009, 08:45 AM
  3. Replies: 4
    Last Post: February 21st 2009, 06:10 PM
  4. floor function - An Identity
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 3rd 2009, 07:28 AM
  5. Floor function
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 21st 2008, 10:13 PM

Search Tags


/mathhelpforum @mathhelpforum