Results 1 to 4 of 4

Thread: 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
    $\displaystyle \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
    $\displaystyle \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 $\displaystyle a=4$ and $\displaystyle b=8$. Then

    $\displaystyle \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}$

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

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

    $\displaystyle =6+ 5$

    $\displaystyle =11$.

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

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

    $\displaystyle =8+2$

    $\displaystyle =10\neq11$.

    So your proof is impossible without further parameters.

    Here is a proper rendering:

    $\displaystyle \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$

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

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

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

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

    $\displaystyle =\frac{ab+a+b}{4}$. $\displaystyle \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 $\displaystyle \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}]$
    $\displaystyle = (2 + 4) + ([4/8] + [8/8] + [12/8] + [16/8])$
    $\displaystyle = 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 $\displaystyle \ell$ be the set of all pairs of integers (x,y) satisfying
    $\displaystyle 1 \leq x \leq \left[\frac{a}{2}\right], 1 \leq y \leq \left[\frac{b}{2}\right]$

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

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

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

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


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

    Now this is where I am still stuck on:
    somehow, when you account for $\displaystyle bx = ay$, there may be a third set, that is somehow equivalent to $\displaystyle \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: Aug 12th 2009, 03:24 PM
  2. Greatest integer function limit?
    Posted in the Calculus Forum
    Replies: 17
    Last Post: Jun 11th 2009, 04:01 AM
  3. Limits of the Greatest Integer Function
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: Mar 17th 2008, 09:51 AM
  4. Greatest integer function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 14th 2007, 04:09 PM
  5. Greatest Integer Function
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Mar 28th 2006, 06:12 AM

Search Tags


/mathhelpforum @mathhelpforum