1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that [a/b]+[2a/b]+...+[(b-1)a/b]=(a-1)(b-1)/2

  1. Aug 8, 2015 #1

    Titan97

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    Prove that $$\sum_{r=1}^{b-1}[\frac{ra}{b}]=\frac{(a-1)(b-1)}{2}$$ where [.] denotes greatest integer function and a & b have no common factors.

    2. Relevant equations
    ##n\le [n]<n+1##
    <x> denotes fractional part of x.

    3. The attempt at a solution

    I first added and subtracted ##a/b + 2a/b +3a/b +...+(b-1)a/b## to get:
    $$\frac{a(b-1)}2-\sum_{r=1}^{b-1}<\frac{ra}{b}>$$ where <.> denotes fractional part. This way I got closer to the answer. Also, <x> is a periodic function and it would be better to convert [.] to <.>. But I am stuck at this step.
     
  2. jcsd
  3. Aug 8, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It can be interesting to have a look at
    $$\sum_{r=1}^{b-1}<\frac{ra}{b}> + \sum_{r=1}^{b-1}<\frac{b-ra}{b}>$$
     
  4. Aug 8, 2015 #3

    Titan97

    User Avatar
    Gold Member

    ##\frac{b-ra}{b}=1-\frac{ra}{b}##.
    The sum will be b-1
     
  5. Aug 8, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Sure. The two sums are the same if you transform one of them, so both contribute (b-1)/2.
     
  6. Aug 8, 2015 #5

    Titan97

    User Avatar
    Gold Member

    That solves the problem. But how did you do that post #2 magic? Did it pop in your mind when you saw the question? Or have you come across problems like these before? Is it because of practice?
     
  7. Aug 8, 2015 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The sum runs over all remainders of n/b, and it does so in a symmetric way.
    That trick is not so uncommon.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted