4
$\begingroup$

I have to prove $$\sum_{n=1}^N\lambda(n)[N/n]=[\sqrt{N}]$$ I tried using the approach in this question but I don't know how I'll get $\sqrt{N}$. Please help.

$\endgroup$
6
$\begingroup$

HINT

$$\sum_{n=1}^N\lambda(n)[N/n] =\sum_{n=1}^N\sum_{d|n}\lambda(d) $$

Next use this to conclude that the double sum equals the number of perfect squares not exceeding $N$

$\endgroup$
  • $\begingroup$ Can you explain how you convert it into a double sum? $\endgroup$ – Bosnia Mar 15 '15 at 13:26
  • $\begingroup$ Notice that for a fixed $n$, on the left hand side the function $\lambda(n)$ is getting evaluated $[N/n]$ times. On the right hand side also the specific term $\lambda(n)$ appears exactly $[N/n]$ times in the expanded sum because the number of integers divisible by $n$ is $[N/n]$ $\endgroup$ – ganeshie8 Mar 15 '15 at 13:36
  • $\begingroup$ More generally we have below for any number theoretic function $f$ : $$\sum_{n=1}^N f(n) [N/n] =\sum_{n=1}^N\sum_{d|n}f(d)$$ $\endgroup$ – ganeshie8 Mar 15 '15 at 13:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.