Let $x>1$ ,$n$ be positive integer. Prove that$$\sum_{k=1}^{n}\frac{\{kx \}}{[kx]}<\sum_{k=1}^{n}\frac{1}{2k-1}$$Where $[kx ]$ be the integer part of $kx$ ,$\{kx \}$ be the decimal part of $kx$.
Problem
Source: China Shanghai ,Mar 6, 2017
Tags: inequalities, algebra, China TST
07.03.2017 19:29
Ain't this easy , first show that $X < 2$ and then subsititute $2-\epsilon$ to get the inequality.
08.03.2017 06:59
any solution
08.03.2017 09:28
I believe the main idea is some kind of Abel sum: it suffices to show that for all natural $c$, $$\sum_{k,[kx\le c]}\{kx\} \le \lceil \frac{c}2 \rceil$$However, this bound is not good enough specifically when $c$ is even. To fix it, we convert $\frac{\{kx\}}{[kx]}\le \frac{1}2\cdot\left(\frac{\{kx\}}{[kx]+1}+\frac{\{kx\}}{[kx]-1}\right)$ whenever $[kx]$ is even. This cuts the final term by half whenever $c$ is even, which Is good enough. I don't have a clean way to show the bound, but otherwise we can seperate the sum into consecutive values of $[kx]$, then by a suitable pairing (and making use of the extra 0's between these "blocks") we can show that the average of all the terms is roughly half.
12.03.2017 09:36
$$\sum_{k=1}^{n}\frac{max \{ \frac{\{x \}+1}{2} ,\{kx \} \}}{[kx]}<\sum_{k=1}^{n}\frac{1}{2k-1}$$
14.03.2017 09:07
galav wrote: Ain't this easy , first show that $X < 2$ and then subsititute $2-\epsilon$ to get the inequality. Are you sure?
10.04.2017 19:07
Does anyone have a full solution to this problem? Thanks!
06.05.2017 19:36
Here's my solution. When $x$ is an integer, $L.H.S = 0 < R.H.S$, obviously true. Now, let's suppose $x$ is not an integer and have a discussion. We call the inequality to be proved as $( * )$. a) $x>2$ $( * ) \Leftrightarrow \sum\limits_{k = 1}^n {\frac{{kx}}{{kx - \left\{ {kx} \right\}}}} < \sum\limits_{k = 1}^n {\frac{{2k}}{{2k - 1}}} $. Notice that $x>2$ and $\left\{ {kx} \right\} < 1$, so $\frac{{kx}}{{kx - \left\{ {kx} \right\}}} < \frac{{kx}}{{kx - 1}} < \frac{{2k}}{{2k - 1}}$. By adding these up we get the wanted inequality. b) $1<x<2$ Let $\alpha = \left\{ x \right\} \in (0,1)$, then $x = 1 + \alpha $. Thus $\left( * \right) \Leftrightarrow \sum\limits_{k = 1}^n {\frac{{\left\{ {k\alpha } \right\}}}{{k + \left[ {k\alpha } \right]}}} < \sum\limits_{k = 1}^n {\frac{1}{{2k - 1}}} $. lemma: For positive integers $m$, $a \le b$, satisfying $\forall k \in \left[ {a,b} \right] \cap N$, $\left[ {k\alpha } \right] = m$ and $\left[ {(a - 1)\alpha } \right] < m$, we have $\sum\limits_{k = a}^b {\frac{{\left\{ {k\alpha } \right\}}}{{k + \left[ {k\alpha } \right]}}} < \sum\limits_{k = a}^b {\frac{1}{{2k - 1}}} $. proof: The wanted inequality above can be rewritten as $\sum\limits_{k = a}^b {\frac{{\left\{ {k\alpha } \right\}}}{{k + \left[ {k\alpha } \right]}}} < \sum\limits_{k = a}^b {\frac{1}{{2k - 1}}} $. From the qualification we know that $(a - 1)\alpha < m \le a\alpha $, $b\alpha < m + 1$. We will discuss on $\alpha$. 1st case: $\alpha \ge \frac{1}{{b - a + 1}}$ For $k \in \left[ {a,b} \right]$, since $\left[ {k\alpha } \right] = \left[ {b\alpha } \right]$, we get $\left\{ {k\alpha } \right\} = \left\{ {b\alpha } \right\} - (b - k)\alpha < 1 - (b - k)\alpha $. Combining this with $m > b\alpha - 1$, we get \[\begin{array}{l} k + m - (2k - 1)\left\{ {k\alpha } \right\}\\ > k + b\alpha - 1 - (2k - 1)(1 - (b - k)\alpha )\\ = k\left[ {\left( {2b - 2k + 1} \right)\alpha - 1} \right] \end{array}\]$\therefore \sum\limits_{k = a}^b {\frac{{k + m - (2k - 1)\left\{ {k\alpha } \right\}}}{{(2k - 1)(k + m)}}} > \sum\limits_{k = a}^b {\frac{{(2b - 2k + 1)\alpha - 1}}{{(2 - \frac{1}{k})(k + m)}}} $. Notice that $(2b - 2k + 1)\alpha - 1$ and $\frac{1}{{(2 - \frac{1}{k})(k + m)}}$ both decrease when $k$ increases, so by Chebyshev's inequality, we have \[\sum\limits_{k = a}^b {\frac{{(2b - 2k + 1)\alpha - 1}}{{(2 - \frac{1}{k})(k + m)}}} \ge \frac{1}{{b - a + 1}}\sum\limits_{k = a}^b {\left( {(2b - 2k + a)\alpha - 1} \right)} \cdot \sum\limits_{k = a}^b {\frac{1}{{(2 - \frac{1}{k})(k + m)}}} \]Since $\alpha \ge \frac{1}{{b - a + 1}}$ $\therefore \sum\limits_{k = a}^b {\left( {(2b - 2k + a)\alpha - 1} \right)} = (b - a + 1)\left( {(b - a + 1)\alpha - 1} \right) \ge 0$. Besides, $\sum\limits_{k = a}^b {\frac{1}{{(2 - \frac{1}{k})(k + m)}}} > 0$, so we can get $\sum\limits_{k = a}^b {\frac{{(2b - 2k + 1)\alpha - 1}}{{(2 - \frac{1}{k})(k + m)}}} \ge 0$, which proves the inequality wanted. 2nd case: $\alpha < \frac{1}{{b - a + 1}}$ By the same means, first notice that $\left\{ {k\alpha } \right\} = \left\{ {a\alpha } \right\} + (k - a)\alpha < (k - a + 1)\alpha $. Combining with $m > (a - 1)\alpha $, we get \[\begin{array}{l} k + m - (2k - 1)\left\{ {k\alpha } \right\}\\ > k + (a - 1)\alpha - (2k - 1)(k - a + 1)\alpha \\ = k\left( {1 - (2k - 2a + 1)\alpha } \right) \end{array}\]And with the same reason as before, by Chebyshev's inequality, with $\alpha < \frac{1}{{b - a + 1}}$, we can get \[\begin{array}{l} \sum\limits_{k = a}^b {\frac{{k + m - (2k - 1)\left\{ {k\alpha } \right\}}}{{(2k - 1)(k + m)}}} > \sum\limits_{k = a}^b {\frac{{1 - (2k - 2a + 1)\alpha }}{{(2 - \frac{1}{k})(k + m)}}} \\ \ge \frac{1}{{b - a + 1}}\sum\limits_{k = a}^b {\left( {1 - (2k - 2a + 1)\alpha } \right)} \cdot \sum\limits_{k = a}^b {\frac{1}{{(2 - \frac{1}{k})(k + m)}}} \\ = \left( {1 - (b - a + 1)\alpha } \right)\sum\limits_{k = a}^b {\frac{1}{{(2 - \frac{1}{k})(k + m)}}} > 0 \end{array}\]So far, the lemma is proved. By using the lemma proved, we prove $\left( * \right)$ at once.
07.05.2017 02:09
Thank you very much.
07.05.2017 19:05
If u dont no solution be calm and dont do show man To galav
26.12.2017 18:54
Wrong solution...
23.01.2018 21:35
wrong solution
23.01.2018 22:41
I don't get why $\{kx\}<\frac{\ell+1}{k}$. From your's we have only $\{x\}<\frac{\ell+1}{k}$
08.11.2019 22:17
This problem blew up on Reddit (via Math StackExchange), so I'll complete the idea presented by DVDthe1st above. 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:
Lemma: For any real $x\geq1$ and any integer $c\geq1$, we have $$\sum_{0<ix<c}\{ix\}<\frac c2.$$
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.
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).
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.
08.11.2019 22:31
for63434 wrote: $\frac{k\alpha+k}{k+[k\alpha]} \le \frac{k\alpha+k+(k-1-[k\alpha])}{k+[k\alpha]+(k-1-[k\alpha])}$ (well known equality since $k-1-[k\alpha] \ge 0$) Unfortunately, since LHS $>1$, the "well-known inequality" holds in the wrong direction.
07.06.2020 02:39
Solved with Th3Numb3rThr33. For \(x\ge2\), the bound is obvious. We restrict our attention to \(x\) in the interval \((1,2)\). Lemma: [Weak form of lemma] For all \(x\in(1,2)\) and integers \(k\), we have \[\sum_{ix<k}\{ix\}<\frac k2.\] Proof. Strong induct on \(k\). First, observe that the left-hand expression, as a function of \(x\), is increasing except at certain discontinuities --- specifically, \(x\) where \(ix\) is an integer less than \(k\) for some \(i\). These \(x\) are of the form \(p/q\), where \(\gcd(p,q)=1\) and \(p\le k\). It will suffice to prove the bound for \(x=p/q-\varepsilon\), where \(\varepsilon>0\) is arbitrarily small. If \(p<k\), then \begin{align*} \sum_{ix<k}\{ix\}&=\sum_{ix<p}\{ix\}+\sum_{p\le ix<k}\{ix\}\\ &=\sum_{ix<p}\{ix\}+\sum_{jx<k-p}\{jx+p\}\\ &=\sum_{ix<p}\{ix\}+\sum_{jx<k-p}\{jx\}, \end{align*}and the bound follows by inductive hypothesis on \(p\) and \(k-p\). For the case \(p=k\), observe that as \(x\) approaches \(p/q\), the \(q\) numbers \(\{x\}\), \(\{2x\}\), \ldots, \(\{qx\}\) form a permutation of \(\frac1q\), \(\frac2q\), \ldots, \(\frac qq\), so \[\sum_{x<q}\{ix\}<\frac1q+\frac2q+\cdots+\frac qq=\frac{q+1}2\le\frac p2,\]as claimed. \(\blacksquare\) Lemma: [Strong form of lemma] For all \(x\in(1,2)\) and integers \(k\), we have \[\sum_{ix<k-1}\{ix\}+\frac12\sum_{k-1\le ix<k}\{ix\}<\frac{k-1}2.\] Proof. The proof is basically identical to that of the weak version. Set \(x=p/q-\varepsilon\) again; the case \(p<k\) is handled analogously. For \(p=k\), observe that the second term in the left-hand expression is always \(\frac12\), and that \(\{x\}\), \(\{2x\}\), \ldots, \(\{(q-1)x\}\) approaches a permutation of \(\frac1q\), \(\frac2q\), \ldots, \(\frac{q-1}q\), so \[\sum_{x\le q-1}\{ix\}+\left[\frac{\{ix\}}2\right]_{x=q}<\left(\frac1q+\frac2q+\cdots+\frac{q-1}q\right)+\frac12=\frac q2\le\frac{p-1}2,\]as claimed. \(\blacksquare\) We instead consider the sequence \((a_i)_{i>0}\) defined by \[a_n:=\begin{cases}\{kx\}&\text{if }n=\lfloor kx\rfloor\text{ for some }k,\\ 0&\text{if no such }k\text{ exists}.\end{cases}\]The key idea in this problem is to instead consider the partial sums \(s_k:=a_1+\cdots+a_k\). By the two lemmas above, we know that for all \(k\), \[s_k<\frac k2\quad\text{and}\quad\frac{s_{k-1}+s_k}2<\frac{k-1}2.\] Spamming the inequality \(\frac2i<\frac1{i-1}+\frac1{i+1}\), we have \begin{align*} \sum_{i=1}^{2n-1}\frac{a_i}i&\le\frac12\left(\frac{a_1}1+\frac{a_1}1+\frac{a_2}1+\frac{a_2}3+\frac{a_3}3+\frac{a_3}3+\frac{a_4}3+\frac{a_4}5+\cdots\right)\\ &=\frac12\left[\frac{a_1}1+\frac{a_2}1+\frac{a_3}3+\frac{a_4}3+\cdots\right]+\frac12\left[\frac{a_1}1+\frac{a_2}3+\frac{a_3}3+\frac{a_4}5+\cdots\right]\\ &=\frac12\left[\left(\frac11-\frac13\right)s_2+\left(\frac13-\frac15\right)s_4+\cdots+\left(\frac1{2n-3}-\frac1{2n-1}\right)s_{2n-2}+\frac{s_{2n-1}}{2n-1}\right]\\ &\qquad+\frac12\left[\left(\frac11-\frac13\right)s_1+\left(\frac13-\frac15\right)s_3+\cdots\left(\frac1{2n-3}-\frac1{2n-1}\right)s_{2n-3}+\frac{s_{2n-1}}{2n-1}\right]\\ &=\left(\frac11-\frac13\right)\frac{s_1+s_2}2+\left(\frac13-\frac15\right)\frac{s_3+s_4}2+\cdots+\frac{2s_{2n-1}}{2n-1}\\ &<\frac2{1\cdot3}\frac12+\frac2{3\cdot5}\frac32+\cdots+\frac2{(2n-3)(2n-1)}\frac{2n-3}2+1\\ &=1+\frac13+\frac15+\cdots+\frac1{2n-1}, \end{align*}as desired.
09.08.2020 08:01
Another proof of Lemma appeared during hutu683's awesome proof(#8) without dividing cases. After the lemma, just wrap terms with same $[k \alpha]$ and the problem is solved. hutu683 wrote: [Lemma] For positive integers $m$, $a \le b$, satisfying $\forall k \in \left[ {a,b} \right] \cap N$, $\left[ {k\alpha } \right] = m$ and $\left[ {(a - 1)\alpha } \right] < m$, we have $$\sum\limits_{k = a}^b {\frac{{\left\{ {k\alpha } \right\}}}{{k + \left[ {k\alpha } \right]}}} < \sum\limits_{k = a}^b {\frac{1}{{2k - 1}}}$$. Proof) Subtracting the corresponding terms, the lemma is equivalent to $\sum\limits_{k = a}^b (2m+1-(2k-1)\alpha) \times \left( {\frac{k}{(2k - 1)(k+m)}}\right)>0$. We can see that both $x_k = 2m+1-(2k-1)\alpha$ and $y_k= \frac{k}{(2k - 1)(k+m)}$ decrease when $k$ increases. Therefore, using Chebyshev's inequality, we get $$ \sum_{k=a}^b x_k y_k \ge \frac{1}{b-a+1} \sum_{k=a}^b x_k \sum_{k=a}^b y_k$$. Since $y_k >0$, it is enough to show that $\sum_{k=a}^b x_k>0$. By simple calculation, $$\sum_{k=a}^b x_k = (b-a+1)(2m+1)-(b+a-1)(b-a+1)\alpha = (b-a+1) (( m+1 - b\alpha) +(m - (a-1)\alpha))$$Since we assumed $[b\alpha]=m$ and $(a-1)\alpha<m$, we get $\sum_{k=a}^b x_k >0$ and the lemma is proven. $\blacksquare$