Prove that: $ \sum_{i=1}^{n^2} \lfloor \frac{i}{3} \rfloor= \frac{n^2(n^2-1)}{6}$ For all $ n \in N$.
Problem
Source: floor function identity
Tags: floor function, algebra proposed, algebra
06.11.2008 12:08
Let \[ f(m)=\sum_{i=1}^{m}[\frac{i}{3}]=\frac{m(m+1)}{2}-\frac 13 ([\frac{m+2}{3}]+2[\frac{m+1}{3}])=\frac{m(m-1)}{6}+\theta (m),\] \[ \theta (m)=\frac 13 (m-[\frac{m+2}{3}]-2[\frac{m+1}{3}]).\] Obviosly $ \theta (m+3)=\theta (m),\theta (0)=0=\theta (1),\theta (2)=-1$ Because $ n^2=0,1\mod 3$ we get $ \theta (n^2)=0.$
09.11.2008 23:29
Clearly we need only prove that \[ \sum_{i=1}^{n^2}\left\{\frac{i}{3}\right\}=\frac{n^2}{3}\] This is equivalent to showing that the number of $ i\equiv 2\mod{3},i\in[n^2]$ is equal to the number of $ i\equiv 0\mod{3}$, which is clear.
20.07.2014 20:40
First note that if the claim holds for $n=3k$ then it holds for $n=3k+1,3k+2$. To prove the claim for $n=3k$, double count the number of lattice points in the interior of the triangle defined by $y=0, y=x/3,x=n^2$. Since the triangle has lattice vertices, we can apply Pick's Theorem: $A=0.5*n^2*(n^2/3)=n^4/6=I+B/2-1$. The LHS of the given equation is $I+B-(n^2+1)$ and it is easy to show that $B=(n^2+1)+n^2/3+(n^2-3)/3=5n^2/3$. The rest is simple algebra.