Results 1 to 4 of 4

Math Help - Help with proof with greatest integer function

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    7

    Help with proof with greatest integer function

    I'm having a hard time with this proof:
    Show that if a and b are positive integers then
    \sum_{i = 1}^{[a/2]} [\frac{ib}{a}] + \sum_{j = 1}^{[b/2]} [\frac{ja}{b}] = [\frac{a}{2}][\frac{b}{2}] + [\frac{(a,b)}{2}]

    Thanks everyone!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by rubik mania View Post
    I'm having a hard time with this proof:
    Show that if a and b are positive integers then
    \sum_{i = 1}^{[a/2]} [\frac{ib}{a}] + \sum_{j = 1}^{[b/2]} [\frac{ja}{b}] = [\frac{a}{2}][\frac{b}{2}] + [\frac{(a,b)}{2}]

    Thanks everyone!
    You must have written this down wrong, because we can disprove it by letting a=4 and b=8. Then

    \sum_{i = 1}^{a/2}\frac{ib}{a} + \sum_{j = 1}^{b/2}\frac{ja}{b}=\sum_{i = 1}^{4/2}\frac{i8}{4} + \sum_{j = 1}^{8/2}\frac{j4}{8}

    =2\sum_{i = 1}^{2}i + \frac{1}{2}\sum_{j = 1}^{4}j

    =2(1+2) + \frac{1}{2}(1+2+3+4)

    =6+ 5

    =11.

    But \frac{a}{2}\left(\frac{b}{2}\right)+\frac{(a,b)}{2  }=\frac{4}{2}\left(\frac{8}{2}\right)+\frac{(4,8)}  {2}

    =2\left(4\right)+\frac{4}{2}

    =8+2

    =10\neq11.

    So your proof is impossible without further parameters.

    Here is a proper rendering:

    \sum_{i = 1}^{a/2}\frac{ib}{a} + \sum_{j = 1}^{b/2}\frac{ja}{b} =\frac{b}{a}\sum_{i = 1}^{a/2}i+\frac{a}{b}\sum_{j = 1}^{b/2}j

    =\frac{b}{a}\left(\frac{(a/2)(a/2+1)}{2}\right)+\frac{a}{b}\left(\frac{(b/2)(b/2+1)}{2}\right)

    =\frac{b}{a}\left(\frac{a^2/4+a/2}{2}\right)+\frac{a}{b}\left(\frac{b^2/4+b/2}{2}\right)

    =b\left(\frac{a+2}{8}\right)+a\left(\frac{b+2}{8}\  right)

    =\frac{ab+2b+ab+2a}{8}

    =\frac{ab+a+b}{4}. \blacksquare
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    7
    Sorry, I forgot to mention:[x] is the greatest integer function.

    so \sum_{i = 1}^{a/2}[\frac{ib}{a}] + \sum_{j = 1}^{b/2}[\frac{ja}{b}]=\sum_{i = 1}^{4/2}[\frac{i8}{4}] + \sum_{j = 1}^{8/2}[\frac{j4}{8}]
    = (2 + 4) + ([4/8] + [8/8] + [12/8] + [16/8])
    = 6 + 0 + 1 + 1 + 2 = 10, so it actually works.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    Posts
    7
    ok, this is what I have so far...
    Let \ell be the set of all pairs of integers (x,y) satisfying
    1 \leq x \leq \left[\frac{a}{2}\right], 1 \leq y \leq \left[\frac{b}{2}\right]

    The set \ell has \left[\frac{a}{2}\right]\left[\frac{b}{2}\right] members

    Separate \ell into subsets \ell_1  \&  \ell_2, according as bx < ay, \mbox{ or } bx > ay

    The set \ell_1 can be described as the set of all pairs (x,y) such that 1 \leq x \leq \left[\frac{a}{b}\right],   1 \leq y \leq \frac{bx}{a}

    The number of pairs in \ell_1 is then seen to be \sum_{x = 1}^{[a/2]} \left[\frac{bx}{a}\right]


    Similarly, \ell_2 consists of the pairs of (x,y) such that
    1 \leq y \leq \left[\frac{b}{2}\right], 1 \leq x \leq \frac{ay}{b}
    and the number of pairs in \ell_2 is \sum_{y = 1}^{[b/2]} \left[\frac{ay}{b}\right]

    Now this is where I am still stuck on:
    somehow, when you account for bx = ay, there may be a third set, that is somehow equivalent to \left[\frac{(a,b)}{2}\right] number of elements total. How do you show that this is true?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Integer Function
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 12th 2009, 03:24 PM
  2. Greatest integer function limit?
    Posted in the Calculus Forum
    Replies: 17
    Last Post: June 11th 2009, 04:01 AM
  3. Limits of the Greatest Integer Function
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: March 17th 2008, 09:51 AM
  4. Greatest integer function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 14th 2007, 04:09 PM
  5. Greatest Integer Function
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 28th 2006, 06:12 AM

Search Tags


/mathhelpforum @mathhelpforum