Waste less time on Facebook — follow Brilliant.
×

Proving a floor sum.

Given that \(a,b\in\Bbb{Z}^+\) and \(\gcd(a,b)=1\).

Prove the following:

\[\left\lfloor\frac{a}{b}\right\rfloor+\left\lfloor2\cdot\frac{a}{b}\right\rfloor+\left\lfloor3\cdot\frac{a}{b}\right\rfloor+\ldots+\left\lfloor(b-1)\cdot\frac{a}{b}\right\rfloor=\frac{(a-1)(b-1)}{2}\]


Clarifications:

  • \(\lfloor\cdot\rfloor\) denotes the floor function (greatest integer function).
  • \(\gcd(x,y)\) denotes the greatest common divisor of \(x\) and \(y\).

Hint:

It'd be helpful to prove this first before attempting to prove the main problem.

\[\forall~a,b\in\Bbb{Z}^+\mid\gcd(a,b)=1\implies n\frac{a}{b}\not\in\Bbb{Z}~~\forall~~0\lt n\lt b~\land~n\in\Bbb{Z}\]

Note by Prasun Biswas
1 year, 10 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Use the fact that \(\lfloor x\rfloor=x-\{x\}\) to rewrite as

\[\sum_{k=1}^{b-1}\left\lfloor\dfrac{ka}{b}\right\rfloor=\dfrac a b\sum_{j=1}^{b-1} j-\sum_{k=1}^{b-1}\left\{\dfrac{ka}{b}\right\}=\dfrac{a(b-1)}{2}-\sum_{k=1}^{b-1}\left\{\dfrac{ka}{b}\right\}.\]

Now

\[\sum_{k=1}^{b-1}\left\{\dfrac{ka}{b}\right\}=\sum_{k=1}^{(b-1)/2}\left(\left\{\dfrac{ka}{b}\right\}+\left\{\dfrac{(b-k)a}{b}\right\}\right)=\sum_{k=1}^{(b-1)/2}\left(\left\{\dfrac{ka}{b}\right\}+\left\{a-\dfrac{ka}{b}\right\}\right).\]

Here no term can be zero since \(na/b\) is not integer for \(1\le n<b\) provided that \((a,b)=1\). So \(\forall k\in[1, (b-1)/2]\)

\[\left\{\dfrac{ka}{b}\right\}+\left\{a-\dfrac{ka}{b}\right\}=1\implies \sum_{k=1}^{(b-1)/2}\left(\left\{\dfrac{ka}{b}\right\}+\left\{a-\dfrac{ka}{b}\right\}\right)=\sum_{k=1}^{(b-1)/2}1=\dfrac{b-1}{2}\]

and we're, um, done. Jubayer Nirjhor · 1 year, 10 months ago

Log in to reply

@Jubayer Nirjhor Consider \(b=8\) and \(a=9\). We have \(\gcd(a,b)=1\) but \(\frac{(b-1)}{2}\) is not a positive integer \(\geq 1\). Then, what does the sum \(\displaystyle\sum_{k=1}^{(b-1)/2}(1)\) mean? Prasun Biswas · 1 year, 10 months ago

Log in to reply

@Prasun Biswas The sum is to \( b-1\), as in \( \lfloor (b-1) \frac{ a}{b} \rfloor \), and not to \( \frac{ b-1}{2} \) as you had it. Calvin Lin Staff · 1 year, 10 months ago

Log in to reply

@Jubayer Nirjhor Very well done.... Vighnesh Raut · 1 year, 10 months ago

Log in to reply

Warning: there is a huge hint below.

\(na (\mod b)\) is pairwise distinct for \(n=1, 2, ..., b\). Proof: The opposite is false by Pigeonhole Principle. Hence if we limit \(n\) to \(1, 2, 3, ..., b-1\) the possible remainders are \(1, 2, ..., b-1\), once each.

From here we can find the sum of the \(b-1\) fractional parts of \(n•\frac {a}{b}, n=1, 2, ..., b-1\). We know their sum, so we know the sum of their floors. Joel Tan · 1 year, 10 months ago

Log in to reply

@Joel Tan There's an easier approach (though essentially based on the same idea).

Hint: Heads and tails. Calvin Lin Staff · 1 year, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...