The error when we rounding down and sum in $\sum_i \lfloor n/i \rfloor$ vs. $\sum_i n/i$.

68 Views Asked by At

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}$?

1

There are 1 best solutions below

1
On BEST ANSWER

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.