Pick's theorem for a triangle

Question

I'm trying to show that Pick's theorem holds for any right triangle with vertices at the points $(0,0),(a,0),(0,b)$ with $a$ and $b$ both being positive integers.

I've managed to express the number of interior points as the sum $$\sum_{k=1}^{a-1} \left( \left\lceil k \frac{b}{a} \right\rceil-1 \right) ,$$ and the number of boundary points as $$a+b+\gcd(a,b). $$ Pick's theorem then suggests that $$\sum_{k=1}^{a-1} \left( \left\lceil k \frac{b}{a} \right\rceil-1 \right) +\frac{1}{2} \left( a+b+\gcd(a,b) \right) -1=\frac{ab}{2},$$ or equivalently $$\sum_{k=1}^{a-1} \left\lceil k\frac{b}{a} \right\rceil=\frac{a-b+ab-\gcd(a,b)}{2}.$$ I couldn't prove this equality is true. I've thought about using induction on either $a$ or $b$, but the $\gcd$ makes it difficult for me. Any thoughts on how to prove this would be welcome, Thanks!

P.S. Wikipedia suggests a similar identity for the floor function $$\sum_{k = 1}^{n - 1} \left\lfloor \frac{k m}{n} \right\rfloor = \frac{(m - 1)(n - 1)+\gcd(m,n)-1}2 ,$$ but I couldn't find a proof of that one either.

Answer 1

Call this triangle $T'$ The slick way to do this is to observe that the triangle $T'$ with vertices $(a,0)$, $(0,b)$ and $(a,b)$ has the same number of lattice points as $T$ (a bijection is $(x,y)\mapsto(a-x,b-y)$). Then $T\cup T'$ is a closed rectangle with $(a+1)(b+1)/2$. So the number of lattice points in $T$ is $$\frac{(a+1)(b+1)+C}2=\frac{ab}2+\frac{a+b+C}2+\frac12$$ where $C$ is the number of lattice points on the hypotenuse of $T$. We see that $a+b+C$ is one more than the number of lattice points on the perimeter of $T$. This gives Pick for $T$.

Answer 2

We will prove both of the equations $$f_1(a,b):=\sum_{k=1}^a \left\lceil k \frac{b}{a} \right\rceil=\frac{ab+a+b-\gcd(a,b)}{2} =:g_1(a,b), \\ f_2(a,b):=\sum_{k=0}^{a-1} \left\lfloor k \frac{b}{a} \right\rfloor=\frac{ab-a-b+\gcd(a,b)}{2}:=g_2(a,b),$$ hold for positive integers $a$, and nonnegative integers $b$. It is clear that if $a \mid b$ then $$f_1(a,b)=\frac{b}{a}\sum_{k=1}^a k=\frac{(a+1)b}{2}=g_1(a,b), \\ f_2(a,b)=\frac{b}{a} \sum_{k=0}^{a-1}k=\frac{(a-1)b}{2}=g_2(a,b). $$ Otherwise we can use Euclidean division to get $$b=aq+r, $$ with $q \in \mathbb{Z}_{\geq 0}$ and $0 \leq r <a$. Plugging this into $f_1(a,b)$ gives $$f_1(a,b)=\sum_{k=1}^a kq+\sum_{k=1}^a \left\lceil k \frac{r}{a} \right\rceil=\frac{qa(a+1)}{2}+\sum_{k=1}^a \left\lceil k \frac{r}{a} \right\rceil .$$ Observe now that for $1\leq m \leq r$, $\left\lceil k \frac{r}{a} \right\rceil=m$ precisely when $\left\lfloor(m-1) \frac{a}{r} \right\rfloor+1 \leq k \leq \left\lfloor m \frac{a}{r} \right\rfloor$. Thus, one gets $$f_1(a,b)=\frac{qa(a+1)}{2}+\sum_{m=1}^rm \left(\left\lfloor m \frac{a}{r} \right\rfloor -\left\lfloor(m-1) \frac{a}{r} \right\rfloor\right).$$ Using summation by parts on the last formula yields $$f_1(a,b)=\frac{qa(a+1)}{2}+a(r+1)-\sum_{m=1}^r \left\lfloor m \frac{a}{r} \right\rfloor=\frac{qa(a+1)}{2}+ar-\sum_{m=0}^{r-1} \left\lfloor m \frac{a}{r} \right\rfloor. $$ Another way to put this is $$f_1(a,b)=\frac{(b-r)(a+1)}{2}+ar-f_2(r,a) ,\quad b=aq+r, $$ and a similar process gives the result $$f_2(a,b)=\frac{(b-r)(a-1)}{2}+ar-f_1(r,a) ,\quad b=aq+r. $$ We have shown that $f_1,f_2$ satisfy a particular system of recursive equations, with the base cases being those in which the the first argument divides the second. We know that iterating the Euclidean algorithm will get to these cases in finitely many steps. We also know that in these base cases $(f_1,f_2)=(g_1,g_2)$. If one can show that $(g_1,g_2)$ satisfy the same recursive system, the proof would be finished. This last step is easy, and I won't write the proof here.