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

Question

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

A more interesting question is how much the two sums differ without the 1/n in front. — marty cohen, Jan 31 '18 at 14:29
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! :) — StefanH, Jan 31 '18 at 14:47

score 2 · Accepted Answer · answered Jan 31 '18 at 13:53

2

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.

answered Jan 31 '18 at 13:53

The Phenotype

5,199

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

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

1 Answers1

Linked