4
$\begingroup$

Assume $a,b,c$ be positive integers. Show that:

$$\sum_{k=0}^{n-1} \left\lfloor \frac{ak+b}{c} \right\rfloor = \sum_{k=0}^{\left\lfloor \dfrac{an+b}{c}\right\rfloor} \left\lfloor\dfrac{ck+(an+b)\pmod {c}}{a}\right\rfloor$$

My approach is the following:

let $an+b=cl+r,0\le r<c$, then we have $\left\lfloor \dfrac{an+b}{c} \right\rfloor=l$, For the right hand $$\sum_{k=0}^{\left\lfloor \dfrac{an+b}{c}\right\rfloor} \left\lfloor\dfrac{ck+(an+b)\pmod {c}}{a}\right\rfloor=\sum_{k=0}^{l}\left\lfloor\dfrac{k+r}{a}\right\rfloor$$

Well and now I'm stuck and don't know how to proceed.

$\endgroup$
5
  • $\begingroup$ @prasun dont put displaystyle or left right in titles, see meta. $\endgroup$ – dustin Mar 21 '15 at 4:37
  • $\begingroup$ Your identity is false for all the values I tried, you probably made a typo somewhere. Where does your question come from ? $\endgroup$ – Ewan Delanoy Mar 23 '15 at 13:39
  • $\begingroup$ Hello,have you some counter-example? is other people give me a question,if this problem wrong, and How the least modification makes this problem is right? $\endgroup$ – user225250 Mar 23 '15 at 13:41
  • 1
    $\begingroup$ For example it is false with $a=1$, $b=0$, $c=1$. The sum runs to $n-1$ on the LHS and to $n$ on the RHS. $\endgroup$ – Dan Brumleve Mar 25 '15 at 2:45
  • $\begingroup$ ok wow this looks like a lot of fun, I will have a look at it 225250 but firstly I will need to clarify what is meant by mod in your identity, if you are referring to the modulo operation, and wish to express the remainder of the division of $an+b$ by $c$, then you will need to fix those brackets. If you are referring to a congruence modulo $c$, then I really can't help but feel this will turn out to be a "non statement" like "A implies A" which is perfectly fine, but I make enough of those myself that waste a lot of my time $\endgroup$ – Adam L May 8 '18 at 5:50
1
+50
$\begingroup$

Here is a way to compute LHS. Consider line $L$ in the plane defined by $y = \frac{ax+b}{c}$. Clearly, LHS is counting the lattice points in $[0,n)\times (0,\infty]$ on/under the line. Call the set of such lattice points $A$.

Alternatively, one may count lattice points in $A$ "horizontally". Specifically, for each $y\in \{1, \ldots, Y\}$, where $Y:=\lfloor(an+b)/c\rfloor$, the largest possible $y$-coordinate of points in $A$, the size of $A_y := A\cap [0,n)\times \{y\}$ is equal to

  1. $n$, if $y \leq a/c$.
  2. $\lfloor\frac{an+b-cy}{a}\rfloor$,if $y > a/c$.

Therefore, one may change RHS to $$n\lfloor a/c \rfloor + \sum_{k=\lfloor a/c\rfloor+1}^{\lfloor(an+b)/c\rfloor}\lfloor\frac{an+b-ck}{a}\rfloor.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy