Let $x\in[1,+\infty)\subset\mathbb{R}$. I would like to show that $$\sum_{d=1}^{\lfloor x\rfloor}\left(\frac{x}{d}-\left\lfloor\frac{x}{d}\right\rfloor\right)\leq x-1,$$ where $\lfloor\cdot\rfloor$ is the floor function. I understand that, since $$\frac{x}{d}-\left\lfloor\frac{x}{d}\right\rfloor\leq1,$$ we have $$\sum_{d=1}^{\lfloor x\rfloor}\left(\frac{x}{d}-\left\lfloor\frac{x}{d}\right\rfloor\right)\leq \sum_{d=1}^{\lfloor x\rfloor}1=\lfloor x\rfloor\leq x.$$ How can I come up with the finer bound? Any hints? Thank you in advance.
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
We have \begin{align*} & \sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } {\left( {\frac{x}{d} - \left\lfloor {\frac{x}{d}} \right\rfloor } \right)} = \sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } {\left( {\frac{x}{d} - \left\lfloor {\frac{{\left\lfloor x \right\rfloor }}{d}} \right\rfloor } \right)} = \sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } {\left( {\frac{x}{d} - \frac{{\left\lfloor x \right\rfloor }}{d}} \right)} + \sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } {\left( {\frac{{\left\lfloor x \right\rfloor }}{d} - \left\lfloor {\frac{{\left\lfloor x \right\rfloor }}{d}} \right\rfloor } \right)} \\ & \le (x - \left\lfloor x \right\rfloor )\sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } {\frac{1}{d}} + \sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } {\left( {1 - \frac{1}{d}} \right)} = (x - \left\lfloor x \right\rfloor - 1)\sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } {\frac{1}{d}} + \sum\limits_{d = 1}^{\left\lfloor x \right\rfloor } 1 \\ & = x - 1 + (x - \left\lfloor x \right\rfloor - 1)\sum\limits_{d = 2}^{\left\lfloor x \right\rfloor } {\frac{1}{d}} \le x - 1. \end{align*}
$\begingroup$
$\endgroup$
Your sum can be re-written as $$ \sum_{d \leq x} \Big ( \frac{x}{d} - \sum_{\substack{n \leq x \\ d | n}} 1 \Big ) $$ Interchanging the two sums you get $$ x \sum_{d \leq x} \frac{1}{d} - \sum_{n \leq x} d(n) $$ where $d(n)$ counts the number of divisors of $n$. Thus the problem is reducing to computing $$ \sum_{n \leq x} d(n). $$ There is a geometric interpretation of this sum as counting the number of lattice points inside the hyperbola $x y = n$. Using this geometric interpretation (the so-called "Hyperbola method" of Dirichlet) you can show that, $$ \sum_{n \leq x} d(n) = x \log x + (2 \gamma - 1) x + O(\sqrt{x}) $$ where $\gamma$ is the Euler-Mascheroni constant. Recall that $$ \sum_{d \leq x} \frac{1}{d} = \log x + \gamma + O(1/x). $$ So this gives, $$ x \sum_{d \leq x} \frac{1}{d} - \sum_{n \leq x} d(n) = (1 - \gamma) x + O(\sqrt{x}) $$ and therefore proves your claim (in stronger form) for all large $x$. Working out explicit constants in $O(\cdot)$ (which is easy by looking it up on the internet) will give you a bound and you can check on a computer that the claim is true for the remaining values. Note that this problem is a bit delicate because you cannot beat $x$ by too much, the asymptotic is actually $(1 - \gamma) x$ and $1 - \gamma \approx 0.4227843351$.
