For some $x \in \mathbb R$ denote by $\lfloor x \rfloor := \sup\{ k \in \mathbb Z \mid k \le x \}$ the biggest integer smaller than $x$, the so called floor function.

Then in my textbook it is claimed that:

$$ \frac{1}{n} \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \sim \frac{1}{n} \sum_{i=1}^n \frac{n}{i} $$ where the error as we go from $\lfloor n/i \rfloor$ to $n/i$ is smaller than $1$, hence also in the sum.

Why is the error in the sum smaller than $1$, surely the error between $\lfloor n/i \rfloor$ to $n/i$ is smaller than $1$, but I do not see that this holds true for the error between the sums $\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$ and $\sum_{i=1}^n \frac{n}{i}$?

  • $\begingroup$ A more interesting question is how much the two sums differ without the 1/n in front. $\endgroup$ – marty cohen Jan 31 '18 at 14:29
  • $\begingroup$ Thats was what I was trying to determine, as I overlooked the $1/n$, so if you know it, feel free to give an answer! :) $\endgroup$ – StefanH Jan 31 '18 at 14:47

For the sums (up to $n$) the error becomes $n$, and then you divide the sums by $n$, hence the error is $1$.

I believe you read over the $\frac{1}{n}$ part in the quote.

  • $\begingroup$ Oh yes, sometimes I am just blind... thank u! $\endgroup$ – StefanH Jan 31 '18 at 14:10

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.