3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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*}

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

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.