# Questions on a proof to show if $\Phi(n)=\sum^n_{i=1}\phi(i)$, where $\phi$ is the Euler phi function then $\Phi(n)=\tfrac{3n^2}{\pi}+O(n\log(n))$

I'm trying to understand a proof of a theorem in my notes but there are multiple parts I simply can't follow , The theorem is as follows :

Let $$\Phi(n)=\sum^n_{i=1}\phi(i)$$, where $$\phi(n)$$ is the Euler phi function then $$\Phi(n)=\tfrac{3n^2}{\pi}+O(n\log(n))$$.

The proof goes as follows:

Note $$\mu$$ is the mobius function, $$[\tfrac{n}{d}]$$ is the integer part of n divided by , and $$O$$ is defined as ; given two functions $$f,g$$ we write $$f(x)=(Og(x))$$ if there exists a constant $$c$$ s.t. $$f(x)\leq cg(x)$$ for all c

$$\Phi(n)=\sum^n_{i=1}\phi(i)=\sum^n_{i=1}\sum_{d|i}\tfrac{i}{d}\mu(d)$$

let $$\tfrac{i}{d}=d'$$ so $$i=dd'$$, then,

$$\Phi(n)=\sum_{dd'\leq n}d'\mu(d)$$

$$=\sum^n_{d=1}\mu(d)\sum^{[\tfrac{n}{d}]}_{d=1}d'$$ ……..

=$$\tfrac{1}{2}\sum^n_{d=1}\mu(d)([\tfrac{n}{d}]^2+[\tfrac{n}{d}])$$...…(1)

=$$\tfrac{1}{2}\sum^n_{d=1}\mu(d)(\tfrac{n^2}{d^2}+O(n/d))$$...….

=$$\tfrac{1}{2}\sum^n_{d=1}\mu(d)\tfrac{n^2}{d^2}+\tfrac{1}{2}\sum^n_{d=1}\mu(d)O(n/d)$$

=$$\tfrac{n^2}{2}\sum^n_{d=1}\tfrac{\mu(d)}{d^2}+O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})$$...….(2)

=$$\tfrac{n^2}{2}(\sum_{d=1}^\infty\tfrac{\mu(d)}{d^2}-\sum^{\infty}_{d=n+1}\tfrac{\mu(d)}{d^2})+O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})$$

Consider $$O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})=O(n\sum^n_{d=1}\tfrac{1}{d})$$.....(3)

$$=O(n\log(n))$$

so now we have $$\Phi(n)=\tfrac{3n^2}{\pi}+O(n\log(n))$$.

My specific questions are :

(1) How is $$\sum^{[\tfrac{n}{d}]}_{d=1}d'$$ equal to $$\tfrac{1}{2}([\tfrac{n}{d}]^2+[\tfrac{n}{d}])$$ as this equality suggests ?

(2) Why can we say that $$O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})=\tfrac{1}{2}\sum^n_{d=1}\mu(d)O(n/d)$$ ? It confuses me as it's only changing inside the bracket which seems to imply to me it's saying $$n\sum^n_{d=1}\tfrac{\mu(d)}{d}=n/d$$, but I feel it may just be a case of abusive notation?

3) Similarly why can we write this equality

(1) is just the usual sum: $$1+2+..n=\frac{n(n+1)}{2}$$ though the index of the inside sum $$\sum^{[\tfrac{n}{d}]}_{d=1}d'$$ should be $$d'$$, so the sum should actually be $$\sum^{[\tfrac{n}{d}]}_{d'=1}d'$$, hence maybe the confusion is due to a typo
(2) straightforward from the definition of $$O$$ - just absorb the constants inside:
$$\tfrac{1}{2}\sum^n_{d=1}\mu(d)O(n/d)$$ means a quantity $$|A| \le C|\tfrac{1}{2}\sum^n_{d=1}\mu(d)(n/d)|$$ for some absolute -meaning same for all $$n,d$$ -constant $$C$$, since $$\frac{n}{d} >0$$, while $$O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})$$ means a quantity $$|B| \le C_1|n\sum^n_{d=1}\tfrac{\mu(d)}{d}|$$ for some absolute constant $$C_1$$ and by taking $$n$$ factor in the first expression it is plain that the two are equivalent with $$C=2C_1$$
(3) follows from $$|\mu(d)| \le 1$$