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

  • 1
    $\begingroup$ if $x=1.6$ and $n=2$, then $\dfrac{\{(n+1)x\}}{\lfloor (n+1)x\rfloor}<\dfrac{1}{2n+1}$ means $\frac{4.8}{4}<\frac{1}{5}$, but it is not true. $\endgroup$
    – xunitc
    Mar 7 '17 at 7:17
  • $\begingroup$ Indeed it is quite apparent that (1) is much stronger than the desired inequality (and, as it happens, too strong). $\endgroup$
    – Did
    Mar 7 '17 at 7:19
  • $\begingroup$ I think the inequality should be true in general for x>2 see desmos.com/calculator/ldz4ewl7m8 $\endgroup$
    – Navin
    Mar 7 '17 at 8:37
  • $\begingroup$ @navinstudent Well, of course it is since, for every $x>2$, $(n+1)x>2n+2$ hence $$\frac{\{(n+1)x\}}{\lfloor(n+1)x\rfloor}<\frac1{2n+2}$$ The question asks for every $x>1$. $\endgroup$
    – Did
    Mar 7 '17 at 8:43
  • 1
    $\begingroup$ Source: China Team Selection Test 2017 TST 1 Day Problem 2. (2017.03.06) artofproblemsolving.com/community/… $\endgroup$
    – River Li
    Nov 6 '19 at 4:15

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.

enter image description here

  • $\begingroup$ At the Second Case, how it becomes to $\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}$ please? If $1 \le k \le \frac{n}{2}$ or $1+\frac{n}{2} \le k \le n$, I think when $n=3$ it misses $k=2$, maybe it is $1 \le k \le \frac{n}{2}$ or $\frac{n}{2} < k \le n$. and then, when $\lfloor (2-\epsilon) k\rfloor \le 2k-2$, by reciprocal, $\frac{1}{\lfloor (2-\epsilon) k\rfloor} \ge \frac{1}{2k-2}$, so inequality reverse? I can not understand, could you explain it in detail please? $\endgroup$
    – xunitc
    Apr 23 '17 at 4:13
  • $\begingroup$ @xunitc you are right it should be $1 \leq k \leq \frac{n}{2}+1$ and $\frac{n}{2}+2 \leq k \leq n$, and doing the same to the general case, but i checked and it does not effect that much and the argument holds true. $\endgroup$
    – Ahmad
    Apr 23 '17 at 9:00
  • $\begingroup$ well, let $n$ is even. then at $\frac{1}{n} < \epsilon < \frac{2}{n}$, we have $\lfloor (2-\epsilon) k \rfloor \le 2k-2$, but not $\lfloor (2-\epsilon) k \rfloor \color{red}{=} 2k-2$, so by inequality, I think we just can write$$\sum_{k=1}^{n}\frac{kx}{[kx]} = \sum_{k=1}^{n/2}\frac{kx}{[kx]}+\sum_{k=n/2+1}^{n}\frac{kx}{[kx]} \le \sum_{k=1}^{n/2}\frac{kx}{2k-1}+\sum_{k=n/2+1}^{n}\frac{kx}{\color{green}{2k-1}}$$ the green part can not be $2k-2$ by '$\le$'. and $kx$ on numerator, I think it is $kx = k(2-\varepsilon) < k(2-\frac{1}{n})$, not $< k(2-\frac{2}{n})$. what is my problem please? $\endgroup$
    – xunitc
    Apr 23 '17 at 10:25
  • $\begingroup$ @xunitc here you are relaxing my argument because $\sum \limits_{k=n/2+1}^{n} \frac{k x}{2k-2} > \sum \limits_{k=n/2+1}^{n} \frac{k x}{2k-1}$, thus i proved it to the extreme point and what you did is just a relaxation, because you are right $\lfloor (2-\epsilon)k \rfloor =2k-1$ for most of the cases but even if it did not hold even for one $k$ then the proof will collapse in the contrary, in my argument i took it to the extreme. $\endgroup$
    – Ahmad
    Apr 26 '17 at 17:00
  • $\begingroup$ Thank you. I know your means now. Thank you for your patience. $\endgroup$
    – xunitc
    Apr 28 '17 at 8:03

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

enter image description here

  • $\begingroup$ Thanks,This inequality prove by $x\in (1,2)$ is key,so How prove it? $\endgroup$
    – math110
    Mar 7 '17 at 23:11

Source: China Team Selection Test 2017 TST Day 1 Problem 2. (2017.03.06) https://artofproblemsolving.com/community/c422484_2017_china_team_selection_test

AoPS user hutu683 gave a solution. I put it here for people to check the proof.

hutu683's solution: Clearly, we only need to prove the case when $x \in (1, 2)$. Let $x = 1 + \alpha$ with $\alpha \in (0, 1)$. We need to prove that $$\sum_{k=1}^n \frac{\{k\alpha \}}{k + \lfloor k\alpha \rfloor} < \sum_{k=1}^n \frac{1}{2k-1}. \tag{1}$$

To proceed, we need the following lemma. The proof is given later.

Lemma 1: For positive integers $a\le b$ and $m$ satisfying $\lfloor k \alpha\rfloor = m, \forall k \in [a, b]\cap\ \mathbb{N}$ and $\lfloor (a-1)\alpha\rfloor < m$, we have $$\sum_{k=a}^b \frac{\{k\alpha \}}{k + \lfloor k\alpha \rfloor} < \sum_{k=a}^b \frac{1}{2k-1}.$$

From Lemma 1, the inequality in (1) holds. This completes the proof.


Remarks: Here I give some explanation about what hutu683's proof did.

Let $I_m = \{k: \ \lfloor k\alpha\rfloor = m, \quad k\in \{1, 2, \cdots, n\}\}$ for $m = 0, 1, 2, \cdots, \lfloor n\alpha \rfloor$. Then $\{I_0, I_1, \cdots, I_{\lfloor n\alpha \rfloor}\}$ is a partition of $\{1, 2, \cdots, n\}$. We have $$\sum_{k=1}^n \frac{\{k\alpha \}}{k + \lfloor k\alpha \rfloor} = \sum_{m=0}^{\lfloor n\alpha \rfloor} \sum_{k\in I_m} \frac{\{k\alpha \}}{k + \lfloor k\alpha \rfloor}, \quad\quad \sum_{k=1}^n \frac{1}{2k-1} = \sum_{m=0}^{\lfloor n\alpha \rfloor} \sum_{k\in I_m} \frac{1}{2k-1}. $$ It suffices to prove that $$\sum_{k\in I_m} \frac{\{k\alpha \}}{k + \lfloor k\alpha \rfloor} < \sum_{k\in I_m} \frac{1}{2k-1}$$ for $m = 0, 1, 2, \cdots, \lfloor n\alpha \rfloor$.

For $m=0$, clearly we have $$\sum_{k\in I_0} \frac{\{k\alpha \}}{k + \lfloor k\alpha \rfloor} = \sum_{k\in I_0} \frac{k\alpha}{k} = |I_0|\alpha < 1 \le \sum_{k\in I_0} \frac{1}{2k-1}.$$

For $m \in \{1, 2, \cdots, \lfloor n\alpha \rfloor\}$ (only if $\lfloor n\alpha \rfloor \ge 1$), we need to prove that $$\sum_{k\in I_m} \frac{k+m - (2k-1)\{k\alpha\}}{(2k-1)(k+m)} > 0. \tag{2}$$ From hutu683's Lemma 1, the inequality in (2) is true.


Proof of Lemma 1: From the conditions, we have $(a-1)\alpha < m \le a\alpha$ and $b\alpha < m + 1$. We need to prove that $$\sum_{k=a}^b \frac{k+m - (2k-1)\{k\alpha\}}{(2k-1)(k+m)} > 0.$$

There are two possible cases as follows.

1st Case $\alpha \ge \frac{1}{b-a + 1}$: For $k\in [a, b]\cap\ \mathbb{N}$, since $\lfloor k\alpha \rfloor = \lfloor b\alpha \rfloor$, we have $\{k\alpha\} = \{b\alpha\} - (b-k)\alpha < 1 - (b-k)\alpha$. Combining this with $m > b\alpha - 1$, we have \begin{align} k + m - (2k-1)\{k\alpha\} &> k + b\alpha - 1 - (2k-1)(1-(b-k)\alpha)\\ &= k((2b-2k+1)\alpha - 1). \end{align} Thus, we have $$\sum_{k=a}^b \frac{k+m - (2k-1)\{k\alpha\}}{(2k-1)(k+m)} > \sum_{k=a}^b \frac{(2b-2k+1)\alpha - 1}{(2-\frac{1}{k})(k+m)}.$$ Note that $(2b-2k+1)\alpha - 1$ and $\frac{1}{(2-\frac{1}{k})(k+m)}$ both decrease when $k$ increases. Thus, by Chebyshev's sum inequality, we have \begin{align} \sum_{k=a}^b \frac{(2b-2k+1)\alpha - 1}{(2-\frac{1}{k})(k+m)} &\ge \frac{1}{b-a+1}\sum_{k=a}^b ((2b-2k+1)\alpha - 1) \sum_{k=a}^b \frac{1}{(2-\frac{1}{k})(k+m)}\\ &= \frac{1}{b-a+1}(b-a+1)((b-a+1)\alpha - 1) \sum_{k=a}^b \frac{1}{(2-\frac{1}{k})(k+m)}\\ &\ge 0. \end{align} The desired result follows.

2nd Case $\alpha < \frac{1}{b-a + 1}$: For $k\in [a, b]\cap\ \mathbb{N}$, since $\lfloor k\alpha \rfloor = \lfloor a\alpha \rfloor$, we have $\{k\alpha\} = \{a\alpha\} + (k-a)\alpha < \alpha + (k-a)\alpha$ where $\{a\alpha\} < \alpha$ follows from $(a-1)\alpha < m \le a\alpha$. Combining this with $m > (a-1)\alpha$, we have \begin{align} k+ m - (2k-1)\{k\alpha\} &> k+ (a-1)\alpha - (2k-1)(\alpha + (k-a)\alpha)\\ &= k(1 - (2k-2a+1)\alpha). \end{align} Thus, we have $$\sum_{k=a}^b \frac{k+m - (2k-1)\{k\alpha\}}{(2k-1)(k+m)} > \sum_{k=a}^b \frac{1 - (2k-2a+1)\alpha}{(2-\frac{1}{k})(k+m)}.$$ Note that $1 - (2k-2a+1)\alpha$ and $\frac{1}{(2-\frac{1}{k})(k+m)}$ both decrease when $k$ increases. Thus, by Chebyshev's sum inequality, we have \begin{align} \sum_{k=a}^b \frac{1 - (2k-2a+1)\alpha}{(2-\frac{1}{k})(k+m)} &\ge \frac{1}{b-a+1}\sum_{k=a}^b ( 1 - (2k-2a+1)\alpha) \sum_{k=a}^b \frac{1}{(2-\frac{1}{k})(k+m)}\\ &= \frac{1}{b-a+1}(b-a+1)(1-(b-a+1)\alpha)\sum_{k=a}^b \frac{1}{(2-\frac{1}{k})(k+m)}\\ &\ge 0. \end{align} The desired result follows. This completes the proof of Lemma 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}\ .$$

  • $\begingroup$ Thanks,that said my indution is not right.so How to prove $(2)$ $\endgroup$
    – math110
    Mar 7 '17 at 7:34
  • $\begingroup$ @HazemOrabi If $x>2$ one can even replace each $\frac1{2k-1}$ by $\frac1{2k}$ (and shorten considerably your approach, see my comment on main). $\endgroup$
    – Did
    Mar 7 '17 at 8:45
  • $\begingroup$ @Did yes, if $x>2$. $\{kx\}=kx-[kx]$, so just need to proof $$\sum_{k=1}^{n}\frac{kx-[kx]}{[kx]}<\sum_{k=1}^{n}\frac{1}{2k-1}$$ as $$\sum_{k=1}^{n}\frac{kx}{[kx]}<\sum_{k=1}^{n}(\frac{1}{2k-1}+1)=\sum_{k=1}^{n}\frac{2k}{2k-1}(*)$$ when $x \ge 2$, then $\frac{x}{2} \ge 1 > kx-[kx]$, so $[kx] > kx-\frac{x}{2}$ and $\frac{1}{[kx]} < \frac{1}{kx-\frac{x}{2}}$, so $\frac{kx}{[kx]} < \frac{kx}{kx-\frac{x}{2}} = \frac{2k}{2k-1}$. (*) is true. $\endgroup$
    – xunitc
    Mar 7 '17 at 8:49
  • $\begingroup$ @xunitc Please see previous comment to Hazem and/or comment on main, for a simpler approach to a stronger result when $x>2$. $\endgroup$
    – Did
    Mar 7 '17 at 9:13

I tried all day and couldn't prove it but I made a little progress:

Let's define $\{x\}'$ to be 1 if $x$ is an integer and $\{x\}$ otherwise, and note that the LHS of the original inequality satisfies $$\sum_{k=1}^{n}\dfrac{\{kx\}}{\lfloor kx\rfloor} \leq \sum_{k=1}^{n}\dfrac{\{kx\}'}{\lceil kx\rceil-1}\tag{1}$$

If $a=\lceil nx\rceil$ then $\lceil kx\rceil=\lceil k\frac an\rceil$ for $k=1,2,... n$ (can be proved by contradiction), and the modified fractional part is non-decreasing, so it suffices to prove that $$\sum_{k=1}^{n}\dfrac{\{k\frac an\}'}{\lceil k\frac an\rceil-1}<\sum_{k=1}^{n}\dfrac{1}{2k-1}$$ for integers $a\in (n,2n)$ (since we can assume $1<x<2$).

The RHS of (1) can be rewritten as $$\sum_{k=1}^{n}\dfrac{\{kx\}'}{kx-\{kx\}'}=\sum_{k=1}^{n}\dfrac{1}{kx/\{kx\}'-1}$$ since $\lceil kx\rceil=kx+(1-\{kx\}')$.

Letting $x=\frac an$, if $\gcd(a,n)=1$ then $\{\{kx\}':k=1,2,...n\}=\{\frac 1n,\frac 2n,...\frac nn\}$. For $k\in[1,n-1]$, let unique $t\in[1,n]$ such that $t\equiv ak\pmod{n}$. Then $\{kx\}'=\frac tn$ and $k=[a^{-1}t]_n$ so we can write our summation with index $t$: $$\frac1{a-1}+\sum_{k=1}^{n-1}\dfrac{1}{kx/\{kx\}'-1}=\frac1{a-1}+\sum_{t=1}^{n-1}\dfrac{1}{k\frac an/\frac tn-1}$$ $$=\frac1{a-1}+\sum_{t=1}^{n-1}\dfrac{1}{k\frac at-1}$$ Now since $ka\equiv t\pmod n$ we have $ka=u_tn+t$ for some $u_t\in[1,a]$, so this then becomes $$=\frac1{a-1}+\sum_{t=1}^{n-1}\dfrac{1}{\frac {u_tn+t}t-1}$$ $$=\frac1{a-1}+\frac 1n\sum_{t=1}^{n-1}\dfrac{t}{u_t}$$

I stopped at this point but I'll try to see if I can turn it into a proof tomorrow. Comment if you have any ideas!


This problem blew up on Reddit, due to the massively machine-aided proof in the (as of now) top answer. Since this is a competition problem, one expects a more human solution. I'll complete the idea presented by DVDthe1st in the AoPS post for this problem.

We will need the following form of Abel summation: given real numbers $a_1,a_2,\ldots,a_m$ and $b_1\geq b_2\geq\cdots\geq b_m\geq b_{m+1}=0$, we have $$\sum_{1\leq i\leq m}a_ib_i=\sum_{1\leq i\leq m}a_i\sum_{j\geq i}(b_j-b_{j+1})=\sum_{1\leq j\leq m}(b_j-b_{j+1})\sum_{1\leq i\leq j}a_i.$$ Here we used telescoping series, then swapped the order of summation.

Main idea: we want to choose something like $b_i\overset?=\frac1i$ and $a_{\lfloor kx\rfloor}\overset?=\{kx\}$; then we can bound the original LHS by bounding partial sums of $\{kx\}$, which is much easier to handle.

First, we fix some notation to be used throughout the solution. We will be considering functions of the form $f(x)=\sum_j\lambda_j\{\mu_jx\}$ for positive constants $\lambda_j,\mu_j$; these functions are increasing except at integer multiples of $\frac1{\mu_j}$, where they jump downwards. At such a discontinuity $x=x_0$, we will say that $$f\rightsquigarrow C\text{ at }x=x_0^-$$ to mean that $$\lim_{x\to x_0^-}f(x)=C>\lim_{x\to x_0^+}f(x).$$ For example, in the original inequality, we have LHS $\rightsquigarrow$ RHS at $x=2^-$: if we take $x$ approaching $2$ from below (ie. $x=2-\varepsilon$ for small $\varepsilon>0$) then each term in LHS approaches the corresponding term in RHS, but equality is not achieved at either $x=2-\varepsilon$ or $x=2$, due to the jump discontinuity. (This also show that RHS is the best possible constant.)

Lemma: For any real $x\geq1$ and any integer $c\geq1$, we have $$\sum_{0<ix<c}\{ix\}<\frac c2.$$

Proof: We first consider the special case where $x=(\frac cd)^-$ for some integer $\frac c2<d<c$ coprime to $c$. Since the numbers $c,2c,\ldots,(d-1)c$ cover all nonzero residue classes (mod $d$), the numbers $\{x\},\{2x\},\ldots,\{(d-1)x\}$ form some permutation of $\frac1d,\frac2d,\ldots,\frac{d-1}d$. Now $x=(\frac cd)^-$ means that the term $\{dx\}$ is also counted in the sum, with value $\rightsquigarrow1$. Hence $$\sum_{0<ix<c}\{ix\}\rightsquigarrow\sum_{0<j\leq d}\frac jd=\frac1d\frac{d(d+1)}2=\frac{d+1}2\leq\frac c2.$$

For the general case, note that LHS is increasing in $x$ except at discontinuities, which occur whenever $bx$ hits an integer for some $k=b$ in the sum. Hence we may increase $x$ to $x=(\frac ab)^-$ for some integer $a\leq c$ and $a,b$ coprime. In this case we have $$\begin{aligned} \sum_{0<ix<c}\{ix\}&=\sum_{0<ix<a}\{ix\}+\sum_{a\leq ix<c}\{ix\}\\ &\rightsquigarrow\frac{b-1}2+\sum_{0<i'x<c-a}\{(i'+b)x\}\\ &\leq\frac a2+\sum_{0<i'x<c-a}\{i'x\}, \end{aligned}$$ and so we may finish by induction on $c$. (The base case $c=1$ is clearly true since LHS = 0.) $\square$

It turns out that the above lemma is too weak to be used with Abel summation directly. This is because the "equality case" of the original inequality, namely $x=2^-$, is not preserved in the lemma; specifically, the RHS of the lemma is $\frac12$ bigger than LHS when $x=2^-$ and $c$ is odd. As such, we need a stronger result which is tight at $x=2^-$. After a few more hours, we come up with the following:

Main Lemma: For any real $x\geq1$ and any integer $c\geq1$, we have $$\sum_{0<ix<c-1}\{ix\}+\frac12\sum_{c-1\leq ix<c}\{ix\}<\frac{c-1}2.$$

Note that this is equivalent to $$\sum_{0<ix<c-1}\{ix\}+\sum_{0<ix<c}\{ix\}<c-1,$$ while our previous lemma can only give $c-\frac12$ on the RHS.

Proof: In fact, the proof of the previous lemma carries over almost verbatim. The only difference is in the calculation for the special case, where we halve the last term: if $x=(\frac cd)^-$ then $$\sum_{0<ix<c}\{ix\}\rightsquigarrow\sum_{0<j\leq d-1}\frac jd+\frac12=\frac1d\frac{d(d-1)}2+\frac12=\frac d2\leq\frac{c-1}2.\quad\square$$

We are now ready to finish the proof. Remember that as long as we only use the Lemma for even $c$ and the Main Lemma for any $c$, we will preserve the equality case at $2^-$, so the bounds are guaranteed to work out (even if the calculations look intimidating).

Proof of original inequality: First, take $$a_i=\begin{cases}\{kx\},&\text{if }i=\lfloor kx\rfloor\text{ for some }k\geq1,\\0,&\text{else}.\end{cases}$$ This is well-defined since for each $i\geq1$ there is at most one $k\geq1$ such that $\lfloor kx\rfloor=i$ (because $x\geq1$). We also write $$A_k=\sum_{1\leq i\leq k}a_i=\sum_{0<ix<k+1}\{ix\},$$ so the Lemma states $A_k<\frac{k+1}2$, and the Main Lemma states that $A_{k-1}+A_k<k$.

Note that $$\sum_{1\leq k\leq n}\frac{\{kx\}}{\lfloor kx\rfloor}=\sum_{1\leq i\leq\lfloor nx\rfloor}\frac{a_i}i\leq\sum_{1\leq i\leq2n-1}\frac{a_i}i.$$ For even $i$ we will use the inequality $\frac1i\leq\frac12(\frac1{i-1}+\frac1{i+1})$, so we can rewrite the whole sum as $$\begin{aligned} \sum_{1\leq i\leq2n-1}\frac{a_i}i&\leq\frac12\left(a_1+a_2+\frac13(a_3+a_4)+\cdots+\frac1{2n-3}(a_{2n-3}+a_{2n-2})+\frac1{2n-1}a_{2n-1}\right)\\ &\qquad+\frac12\left(a_1+\frac13(a_2+a_3)+\cdots+\frac1{2n-1}(a_{2n-2}+a_{2n-1})\right)\\ &\overset{\text{Abel}}=\frac12\left[\left(1-\frac13\right)A_2+\left(\frac13-\frac15\right)A_4+\cdots+\left(\frac1{2n-3}-\frac1{2n-1}\right)A_{2n-2}+\frac1{2n-1}A_{2n-1}\right]\\ &\qquad+\frac12\left[\left(1-\frac13\right)A_1+\left(\frac13-\frac15\right)A_3+\cdots+\left(\frac1{2n-3}-\frac1{2n-1}\right)A_{2n-3}+\frac1{2n-1}A_{2n-1}\right]\\ &=\left(1-\frac13\right)\frac{A_1+A_2}2+\left(\frac13-\frac15\right)\frac{A_3+A_4}2+\cdots+\left(\frac1{2n-3}-\frac1{2n-1}\right)\frac{A_{2n-3}+A_{2n-2}}2+\frac1{2n-1}A_{2n-1}\\ &<\left(1-\frac13\right)(1)+\left(\frac13-\frac15\right)(2)+\cdots+\left(\frac1{2n-3}-\frac1{2n-1}\right)(n-1)+\frac1{2n-1}n\\ &=1+\frac13+\frac15+\cdots+\frac1{2n-1}, \end{aligned}$$ and we are done. $\square$

Spent a couple of days on this problem. I really enjoyed the statement and proof of the Lemma, which is essentially combinatorial in nature. Strengthening it to the Main Lemma is pretty crazy though; kudos to DVDthe1st for the idea.


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.