# Confusion with $O$ function

I read this identity in lecture notes and need help understand ing the $O$ function

$$\sum_{1\leq d\leq x}\mu(d)\cdot \frac{1}{2}\left\lfloor\frac xd\right\rfloor\left(\left\lfloor\frac xd\right\rfloor+1\right)=\sum_{1\leq d\leq x}\mu(d)\left(\frac{x^2}{2d^2}+O(x/d)\right)$$

Attempt: This implies

$$\frac{1}{2}\left\lfloor\frac xd\right\rfloor\left(\left\lfloor\frac xd\right\rfloor+1\right)=\frac{x^2}{2d^2}+O(x/d)$$

From the definition of $\left\lfloor\theta\right\rfloor$ being the greatest integer not exceeding $\theta$

I can see that $\left\lfloor\frac xd\right\rfloor=x/d+O(1)$,

But substituting this in cannot lead to an expression with $O(x/d)$, where does this come from?

How do I derive this expression

• Um, what? What is $c$? And $O$ is used for estimation, but what you've stated is an exact equality. You'd pretty much never us $O$ in a proof of an equality, unless the equality included limits. – Thomas Andrews May 21 '15 at 12:34
• Corrected the 'c' part – Sam Houston May 21 '15 at 12:38
• Also, the limits are set by the summation sign – Sam Houston May 21 '15 at 12:39

Let's realize what you really want is:

$$\lfloor y\rfloor (\lfloor y\rfloor +1)=y^2+O(y)$$

Let $f(y)=y(y+1)$. Then $f(y)-f(\lfloor y\rfloor) = f'(z) (y-\lfloor y\rfloor)$ for some $z\in [\lfloor y\rfloor, y]\subseteq (y-1,y]$.

But $f'(z)=2z+1$ so $f'(z)= O(y)$ when $z\in (y-1,y]$, and $0\leq y-\lfloor y\rfloor <1$, so $f(y)-f(\lfloor y\rfloor) = O(y)$ and $f(y)=y^2+O(y)$.

So $$f(\lfloor y\rfloor)=f(y)-(f(y)-f(\lfloor y\rfloor) = y^2 + O(y) - O(y)= y^2+O(y).$$

$$\frac{1}{2}[x/d]([x/d]+1)=\frac12\left(\frac xd+O(1)+1\right)\left(\frac xd+O(1)\right)=\frac{x^2}{2d^2}+\frac xdO(1)+O'(1)\\ =\frac{x^2}{2d^2}+O''\left(\frac xd\right).$$

• Could you elaborate on the last equality please, still confused by that, what is the realationship betweeen $O(1)$ and $O(x/d)$ – Sam Houston May 21 '15 at 12:42
• Do you know the big-$O$ notation ? – Yves Daoust May 21 '15 at 12:43
• I am working on becoming more familiar with it, not clear on it yet – Sam Houston May 21 '15 at 12:47