How to prove floor function inequality $\sum\limits_{k=1}^{n}\frac{\{kx\}}{\lfloor kx\rfloor }<\sum\limits_{k=1}^{n}\frac{1}{2k-1}$ for $x>1$

Question

Let $x>1$ be a real number. Show that for any positive $n$ $$\sum_{k=1}^{n}\dfrac{\{kx\}}{\lfloor kx\rfloor }<\sum_{k=1}^{n}\dfrac{1}{2k-1}\tag{1}$$ where $\{x\}=x-\lfloor x\rfloor$

My attempt: I try use induction prove this inequality.

It is clear for $n=1$, because $\{x\}<1\le \lfloor x\rfloor$.

Now if assume that $n$ holds, in other words: $$\sum_{k=1}^{n}\dfrac{\{kx\}}{\lfloor kx\rfloor }<\sum_{k=1}^{n}\dfrac{1}{2k-1}$$ Consider the case $n+1$. We have

$$\sum_{k=1}^{n+1}\dfrac{\{kx\}}{\lfloor kx\rfloor }=\sum_{k=1}^{n}\dfrac{\{kx\}}{\lfloor kx\rfloor }+\dfrac{\{(n+1)x\}}{\lfloor (n+1)x\rfloor}<\sum_{k=1}^{n}\dfrac{1}{2k-1}+\dfrac{\{(n+1)x\}}{\lfloor (n+1)x\rfloor}$$ It suffices to prove that $$\dfrac{\{(n+1)x\}}{\lfloor (n+1)x\rfloor}<\dfrac{1}{2n+1}\tag{2}$$ But David gives an example showing $(2)$ is wrong, so how to prove $(1)$?

Answer 1

Equation (1) is not true in general, in fact, for every $n$ one can find an $x$ for which it is false. Specifically, given $n\ge1$, choose $$x=\frac{n+\frac74}{n+1}>1\ .$$ Then $2n>1$, so $4n+4=4n+3+1<6n+3$, so $$\frac{\{(n+1)x\}}{\lfloor(n+1)x\rfloor} =\frac{\frac34}{n+1}=\frac3{4n+4}>\frac3{6n+3}=\frac1{2n+1}\ .$$

Answer 2

Some thoughts:

Looking at several plots indicates that $$f_n(x):=\sum_{k=1}^n{\{kx\}\over\lfloor kx\rfloor}$$ is largest immediately to the left of $x=2$. Now for $x=2-\epsilon$ with $0<\epsilon\ll1$ one has $$\lfloor kx\rfloor=2k-1,\quad\{kx\}=1-2k\epsilon$$ and therefore $$f_n(x)=\sum_{k=1}^n{1-2k\epsilon\over2k-1}<\sum_{k=1}^n{1\over2k-1}\ .$$ Maybe you want to take a look at the following graph of $f_{250}$:

Answer 3

To start the proof, first it's proven that the inequality is true for all $x \geq 2$ so we are interested in the case $ 1 \leq x \leq 2$.

also its true for $n=1$ because in that case its just $\frac{x}{\lfloor x \rfloor} < 2$ which is $ x < 2$ because $\lfloor x \rfloor = 1$ since $1 \leq x \leq 2$ exclusion.

also from now on we will let $x=2-\epsilon$ such that $0 < \epsilon <1$

First Case : $0 < \epsilon < \frac{1}{n}$ so $\lfloor (2-\epsilon) k \rfloor$ is less than or equal to $2k-1$ so it becomes $\sum \limits_{k=1}^{n} \frac{(2-\epsilon)k}{2k-1} < \sum \limits_{k=1}^{n} \frac{2k}{2k-1}$ which is clearly true (even just be looking at it).

Second Case : $\frac{1}{n} < \epsilon < \frac{2}{n}$ so $\lfloor (2-\epsilon) k\rfloor$ is less than or equal to $2k-1$ when $1 \leq k \leq \frac{n}{2}$ and is less than or equal to $2k-2$ when $1+\frac{n}{2} \leq k \leq n$ so it becomes

$\sum \limits_{k=1}^{\frac{n}{2}} \frac{(2-\frac{2}{n})k}{2k-1}+\sum \limits_{k=1+\frac{n}{2}}^{n} \frac{(2-\frac{2}{n})k}{2k-2} < \sum \limits_{k=1}^{n} \frac{2k}{2k-1} $ evaluating this summation and moving all terms to the right side we arrive at : $$0<-\frac{n^2+n^2 \psi ^{(0)}\left(\frac{n}{2}+1\right)-n^2 \psi ^{(0)}\left(\frac{n}{2}\right)-3 n-n \psi ^{(0)}\left(\frac{n}{2}+1\right)-n \psi ^{(0)}\left(\frac{n}{2}\right)+2 n \psi ^{(0)}(n)+2 \psi ^{(0)}\left(\frac{n}{2}\right)-2 \psi ^{(0)}(n)+2}{2 n}-\frac{(n-1) \left(n+\psi ^{(0)}\left(\frac{n}{2}+\frac{1}{2}\right)-\psi ^{(0)}\left(\frac{1}{2}\right)\right)}{2 n}+\frac{1}{2} \left(2 n+\psi ^{(0)}\left(n+\frac{1}{2}\right)-\psi ^{(0)}\left(\frac{1}{2}\right)\right)$$

simplifying this expression we arrive at results : $$\frac{n H_{n-\frac{1}{2}}-(n-1) H_{\frac{n-1}{2}}+2 n+2 (n-1) \psi ^{(0)}\left(\frac{n}{2}\right)-2 (n-1) \psi ^{(0)}(n)+\log (4)}{2 n} >0$$

just to state before continuing in the proof :

1) $\psi^{(k)}(n)$ is the poly gamma function, a special case to this function is $\psi^{(0)}(n)$ which is equal to $H_{n-1}-\gamma$

2) $H_n = \sum \limits_{k=1}^{n} \frac{1}{k}$ is the $n$-th harmonic number and Euler proved that $H_n \geq \ln(n) +\gamma$ and its also true that $H_n \leq \ln(n)+1$

3) $\gamma \approx 0.5772156649$ which is Euler–Mascheroni constant.

to return to the proof, with some arithmetic manipulation and lower and upper bound for $H_n$ as stated above we reach at : $$\frac{1}{2} n \left(3 \gamma n-n+n (-\log (n-1))-2 n \log (n)+n \log (2 n-1)+2 (n-1) \log \left(\frac{n-2}{2}\right)+2 \log (n)+\log (2 n-2)-2 \gamma +3\right)>0$$ multiply by $2n$ which will not effect the inequality because $n$ is positive. we arrive at : $$3 \gamma n-n+n (-\log (n-1))-2 n \log (n)+n \log (2 n-1)+2 (n-1) \log \left(\frac{n-2}{2}\right)+2 \log (n)+\log (2 n-2)-2 \gamma +3>0$$ solving it in Wolfram we get that its true for all $n>2.37646$ and we check for $n=1,2$ and by this we conclude the proof for the second case.

General Case : $\frac{m}{n} \leq \epsilon \leq \frac{m+1}{n}$ for any $1 \leq m \leq n$ so $\lfloor (2-\epsilon) k \rfloor$ is less or equal to $2k-1$ when $1 \leq k \leq \frac{n}{m}$ and $\lfloor (2-\epsilon) k \rfloor$ is less or equal to $2k-2$ when $ 1+\frac{n}{m} \leq k \leq \frac{2 n}{m}$ and in general $\lfloor (2-\epsilon) k \rfloor$ is less or equal to $2k-1-j$ when $1+\frac{j n}{m} \leq k \leq \frac{(j+1)n}{m}$ for $0 \leq j \leq m-1$.

so it becomes : $$\sum _{j=0}^{m-1} \left(\sum _{k=1+\frac{n j}{m}}^{\frac{n (j+1)}{m}} \frac{\left(2-\frac{m}{n}\right) k}{2 k-j-1}\right) < \sum \limits_{k=1}^{n} \frac{2k}{2k-1}$$ evaluating both sides in the inequality we get:

$$ \sum _{j=0}^{m-1} \frac{2 m^2 \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{1}{2}\right)+j m^2 \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{3}{2}\right)-m^2 \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{3}{2}\right)-j m^2 \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{n}{m}+\frac{1}{2}\right)-m^2 \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{n}{m}+\frac{1}{2}\right)-4 j n^2 \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{1}{2}\right)+4 j n^2 \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{3}{2}\right)+2 j m n \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{1}{2}\right)-4 m n \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{1}{2}\right)-4 j m n \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{3}{2}\right)+2 m n \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{3}{2}\right)+2 j m n \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{n}{m}+\frac{1}{2}\right)+2 m n \psi ^{(0)}\left(\frac{n j}{m}-\frac{j}{2}+\frac{n}{m}+\frac{1}{2}\right)+2 m^2-6 m n+4 n^2}{4 m n} <\frac{1}{2} \left(2 n+\psi ^{(0)}\left(n+\frac{1}{2}\right)-\psi ^{(0)}\left(\frac{1}{2}\right)\right) $$ , Wolfram was not able to evaluate the upper summation, (no problem) because the inner summation was increasing function with respect to $j$ (easy to see : will not prove),then by the summation bounded by integration law for increasing function $f$ we get that : $$ \sum \limits_{i=a}^{b} f(i) \leq \int \limits_{a}^{b+1} f(t)dt $$

so the above inequality becomes : $$ \int_0^m \frac{2 m^2-6 m n+4 n^2+2 m^2 \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{j n}{m}\right)-4 m n \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{j n}{m}\right)+2 j m n \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{j n}{m}\right)-4 j n^2 \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{j n}{m}\right)-m^2 \psi ^{(0)}\left(\frac{3}{2}-\frac{j}{2}+\frac{j n}{m}\right)+j m^2 \psi ^{(0)}\left(\frac{3}{2}-\frac{j}{2}+\frac{j n}{m}\right)+2 m n \psi ^{(0)}\left(\frac{3}{2}-\frac{j}{2}+\frac{j n}{m}\right)-4 j m n \psi ^{(0)}\left(\frac{3}{2}-\frac{j}{2}+\frac{j n}{m}\right)+4 j n^2 \psi ^{(0)}\left(\frac{3}{2}-\frac{j}{2}+\frac{j n}{m}\right)-m^2 \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{n}{m}+\frac{j n}{m}\right)-j m^2 \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{n}{m}+\frac{j n}{m}\right)+2 m n \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{n}{m}+\frac{j n}{m}\right)+2 j m n \psi ^{(0)}\left(\frac{1}{2}-\frac{j}{2}+\frac{n}{m}+\frac{j n}{m}\right)}{4 m n} \, dj < \frac{1}{2} \left(2 n+\psi ^{(0)}\left(n+\frac{1}{2}\right)-\psi ^{(0)}\left(\frac{1}{2}\right)\right)$$ now before evaluating the left side we want to find the values of $m$ that produces the maximum value, which mean the derivative of the left side is equal to $0$, assume that the left side integrate result is $F(m)-F(0)$ so the derivative is $F'(m)-F'(0)$ which is equal to $\sum _{k=1+\frac{m n}{m}}^{\frac{(m+1) n}{m}} \frac{\left(2-\frac{m}{n}\right) k}{2 k-m-1}-\sum _{k=1}^{\frac{n}{m}} \frac{\left(2-\frac{m}{n}\right) k}{2 k-1}$ which evaluate to $\frac{(m-2 n) \left((-m-1) H_{-\frac{(m+1) (m-2 n)}{2 m}}+(m+1) H_{-\frac{m}{2}+n-\frac{1}{2}}+H_{\frac{n}{m}-\frac{1}{2}}+\log (4)\right)}{4 n}$ we want this derivative to equal to $0$, one simple answer is when $m=\frac{n}{2}$ another answer which is a bit harder to see but also simple is $m=n$ (we know that one of the answer is minimum and one is maximum, calculation and experimentation suggest that $m=\frac{n}{2}$ is the maximum and $m=n$ is the minimum, assuming that we don't know which is which) we will substitute both values.

now back to were we left, we will evaluate the new left side, we arrive at:

$$ \frac{m^2 \log \left(32 \pi ^{12} A^{36}\right)-12 m \left((m+1) (m-2 n) \text{log$\Gamma $}\left(-\frac{m}{2}+n+\frac{1}{2}\right)+(m-2 n) \text{log$\Gamma $}\left(\frac{n}{m}+\frac{1}{2}\right)-(m+1) (m-2 n) \text{log$\Gamma $}\left(-\frac{m}{2}+n+\frac{1}{2}+\frac{n}{m}\right)+2 m \psi ^{(-2)}\left(-\frac{m}{2}+n+\frac{1}{2}\right)+2 m \psi ^{(-2)}\left(\frac{n}{m}+\frac{1}{2}\right)-2 m \psi ^{(-2)}\left(-\frac{m}{2}+n+\frac{1}{2}+\frac{n}{m}\right)\right)-12 n \left((m-2 n)^2+m \log (\pi )\right)}{12 n (m-2 n)} < \frac{1}{2} \left(2 n+\psi ^{(0)}\left(n+\frac{1}{2}\right)-\psi ^{(0)}\left(\frac{1}{2}\right)\right)$$

(note : the $A$ written after the evaluation is the Glaisher–Kinkelin constant,$A \approx 1.282427129$, and the function $Log\Gamma(x)$ is the log-gamma function which is just $\ln(\Gamma(t))$).

first we prove the inequality when $m=n$ we arrive at :

$$-(n+1) \text{log$\Gamma $}\left(\frac{n+1}{2}\right)+(n+1) \text{log$\Gamma $}\left(\frac{n+3}{2}\right)+n+n \left(-\log \left(\frac{n+1}{2}\right)\right)-\log (n+1)+\log (2)<\frac{1}{2} \left(2 n+\psi ^{(0)}\left(n+\frac{1}{2}\right)-\psi ^{(0)}\left(\frac{1}{2}\right)\right) $$

so giving the proper uppers bound and lower bounds and basic arithmetic manipulation we arrive at :

$$ n+n \left(-\log \left(\frac{n+1}{2}\right)\right)-\log (n+1)+(n+1) \log \left(\frac{n+3}{2}\right)+\log (2)< \frac{1}{2} \left(2 n+\log \left(n-\frac{1}{2}\right)+\gamma -\psi ^{(0)}\left(\frac{1}{2}\right)\right)$$ solving for $n$ we get that its true for all $n > 2.29577$ and we solved for $n=1,2$

so we are left with the last part of the proof,we prove the inequality when $m=\frac{n}{2}$ we arrive at :

$$ \frac{1}{24} \left(-3 (3 n+2) \text{log$\Gamma $}\left(\frac{3 n}{4}+\frac{1}{2}\right)+(9 n+6) \text{log$\Gamma $}\left(\frac{3 (n+2)}{4}\right)+24 n-9 n \log \left(\frac{1}{4} (3 n+2)\right)-2 \log (3 n+2)+\log (256)\right) < \frac{1}{2} \left(2 n+\psi ^{(0)}\left(n+\frac{1}{2}\right)-\psi ^{(0)}\left(\frac{1}{2}\right)\right)$$ we will do the same tricks of upper and lower bound and basic arithmetic manipulation,we get to : $$\frac{1}{24} \left(24 n-9 n \log \left(\frac{1}{4} (3 n+2)\right)+(9 n+6) \log \left(\frac{3 (n+2)}{4}\right)-2 \log (3 n+2)+\log (256)\right) < \frac{1}{2} \left(2 n+\log \left(n-\frac{1}{2}\right)+\gamma -\psi ^{(0)}\left(\frac{1}{2}\right)\right) $$ and solving this inequality we get that its true for all $n > 0.701281$ and thus concluding that the inequality is true for all $x \geq 1$ and $n$ positive integers.

note : please don't down vote, it took me 3 hours to finish the proof so if there is any poor language, or anything else cut me some slack.

hope its what your are looking for.