First of all we write $[kx]=kx-\{kx\}$. So, we need to prove that $\sum_{1}^{n}\left(\frac{\{kx\}}{k}\right)\geq \{nx\}.$ Let's denote $a_k=\{kx\}$. It is easy to see that $a_k+a_m \geq a_{k+m}$. We need to prove $\sum_{1}^{n}\left(\frac{a_k}{k}\right)\geq a_n.$ We will prove it by induction by $n$. The base is obvious, so we need to make a step. Let's take $m$ such that $\frac{a_m}{m}$ is minimal. If $m=n$ then our inequality is obvious. So, $m<n$. Then, by induction, $\sum_{1}^{n-m}\left(\frac{a_k}{k}\right)\geq a_{n-m}$ and $\sum_{n-m+1}^{n}\left(\frac{a_k}{k}\right)\geq m\cdot \frac{a_m}{m}=a_m$. Now we can add these two inequalities and get \[\sum_{1}^{n}\left(\frac{a_k}{k}\right) \geq a_{n-m}+a_m \geq a_n\]

Binomial-theorem wrote: If $x$ is a positive real number, and $n$ is a positive integer, prove that \[[ nx] > \frac{[ x]}1 + \frac{[ 2x]}2 +\frac{[ 3x]}3 + \cdots + \frac{[ nx]}n,\] where $[t]$ denotes the greatest integer less than or equal to $t$. For example, $[ \pi] = 3$ and $\left[\sqrt2\right] = 1$. I think x should be non-integer positive real numbers..... as equality holds when x is a positive integer....

we can use induction on n and simple floor function identitiies

I immediately thought about induction on n, but I still can't make the n+1 step... It seems very strange to me and I'm a little bit embarrased!!

In fact, for $x=m+\varepsilon$, with $m$ a non-negative integer and $0\leq \varepsilon< 1/n$ we also have equality.

mavropnevma, can you show us the solution please? I'm very interested in this kind of induction

Hi. Here is the method by using induction. Let $ A_k=\sum_{k=1}^n\frac{\lfloor{kx}\rfloor}{k} $ It is obvious that the inequality holds when $ n=1 $ We assume that the inequality holds when $ n\leqslant k-1 $, and we'll get $ kA_k-\sum_{i=1}^{k-1}A_i=\sum_{i=1}^{k}\left \lfloor {ix} \right \rfloor $ $ kA_k=\sum_{i=1}^{k}\left \lfloor {ix} \right \rfloor+\sum_{i=1}^{k-1}A_i\leqslant \sum_{i=1}^{k}\left \lfloor {ix} \right \rfloor+\sum_{i=1}^{k-1}\left \lfloor {ix} \right \rfloor=\sum_{i=1}^{k}\(\left \lfloor {ix} \right \rfloor+\left \lfloor {(k-i)x} \right \rfloor)\leqslant k\left \lfloor {kx} \right \rfloor $ $ \therefore A_k\leqslant \left \lfloor {kx} \right \rfloor $ thereby showing that the inequality holds when $ n=k $. Hence it's proven that the inequality holds $ \forall n\in \mathbb{N} $

I will present my inductive proof too. For $n=1$ the equality is obvious. Now assume $[ nx] >\frac{[ x]}{1}+\frac{[ 2x]}{2}+\frac{[ 3x]}{3}+\cdots+\frac{[ nx]}{n}$ $ [(n+1)x] \geqslant [ nx ] + [ x ] = [ nx ] + [ \frac{(n+1)x}{n+1} ] \geqslant [ nx ] + \frac{[ (n+1)x ]}{n+1}$ Thus completing our proof.

utkarshgupta wrote: I will present my inductive proof too. For $n=1$ the equality is obvious. Now assume $[ nx] >\frac{[ x]}{1}+\frac{[ 2x]}{2}+\frac{[ 3x]}{3}+\cdots+\frac{[ nx]}{n}$ $ [(n+1)x] \geqslant [ nx ] + [ x ] = [ nx ] + [ \frac{(n+1)x}{n+1} ] \geqslant [ nx ] + \frac{[ (n+1)x ]}{n+1}$ Thus completing our proof. You wrote that $[x]\geqslant \dfrac{[(n+1)x]}{n+1}$ but it's wrong! Take $x=0,4$ and $n=2$.

We can also go about this without induction. Beginning as Pavel did, we transform the inequality into: \[\sum_{k=1}^n \frac{\{kx\}}{k} > \{nx\}\] Furthermore, similar to what mavropnevma said, with respect to the original inequality, jumps on either side of the inequality only occur for rationals of the form $\frac{p}{q}$ with $q \in \{1,2,3,\ldots,n\}$, so that we need only consider $x$ at these values. In addition, we may limit $x$ to the interval $[0,1)$ WLOG. So, we consider $0 \le x = \frac{p}{q} < 1$ with $p$, $q$ relatively prime. In that case, $\frac{\{kx\}}{k}$ is just the remainder taken $\pmod q$ of $kp$, then divided by $q$. Since $p$ and $q$ are relatively prime, $p, 2p, 3p, \ldots, (q-1)p$ make up a permutation of the set of nonzero residues $\pmod q$. Call the permutation $\sigma$. So, if we truncate the sum in our new inequality to the $q^{th}$ term, we have: \[ \sum_{k=1}^n \frac{\{kx\}}{k} > \sum_{k=1}^{q-1} \frac{\{kx\}}{k} = \sum_{k=1}^{q-1} \frac{\sigma(k)/q}{k}\] and ideally, we would then like \[\sum_{k=1}^{q-1} \frac{\sigma(k)/q}{k} \ge \{nx\} = \frac{r}{q}\] where $r \equiv np \pmod{q}$. This simplifies to: \[\sum_{k=1}^{q-1} \frac{\sigma(k)}{k} \ge r\] By AM-GM, \[\sum_{k=1}^{q-1} \frac{\sigma(k)}{k} \ge (q-1)\left(\frac{\sigma(1)}{1}\cdots \frac{\sigma(q-1)}{q-1}\right)^{\frac{1}{q-1}} = q-1\] where the last equality holds since the product of numerators is a rearrangement of the product of denominators. Since the residue $r \pmod{q}$ is less than or equal to $q-1$, we do indeed get \[\sum_{k=1}^{q-1} \frac{\sigma(k)}{k} \ge r\] and the result holds.

problem wrote: If $x$ is a positive real number, and $n$ is a positive integer, prove that \[[ nx] \ge \frac{[ x]}1 + \frac{[ 2x]}2 +\frac{[ 3x]}3 + \cdots + \frac{[ nx]}n,\]where $[t]$ denotes the greatest integer less than or equal to $t$. For example, $[ \pi] = 3$ and $\left[\sqrt2\right] = 1$. There's a proof using the Generalization Principle (yes, I just made the name up; oh and I changed $>$ to $\ge$ in the quote because $x=1\implies ?$). We will show that for and reals $a_1\le a_2\le \dots\le a_n$ satisfying $a_1+2a_2+\dots+na_n=0$, we have \[ a_1[x]+a_2[2x]+\dots+a_n[nx]\ge 0. \]The proof is easy induction: we use $[x]+[y]\le [x+y]$ and use $[nx]\ge [kx]+[(n-k)x]$ uniformly for each $k$ in order to keep the ordering of the first $(n-1)$ weights $a_i$. To elaborate, $n=1$ is trivial and when proving the claim for $n$, we note that $a_n\ge 0$, and so we may write $\frac{a_n}{n-1}[nx]\ge \frac{a_n}{n-1}[kx]+\frac{a_n}{n-1}[(n-k)x]$ for $k=1,2,\dots,n-1$ and add these babies up to get \[ a_n[nx]\ge \frac{2a_n}{n-1}([x]+[2x]+\dots+[(n-1)x]), \]so $a_1[x]+a_2[2x]+\dots+a_n[nx]\ge b_1[x]+b_2[2x]+\dots+b_{n-1}[(n-1)x]\ge 0$, where the last inequality was the induction hypothesis for the $(n-1)$-tuple \[(b_1,b_2,\dots,b_{n-1})=\left(a_1+\frac{2a_n}{n-1},a_2+\frac{2a_n}{n-1},\dots,a_{n-1}+\frac{2a_n}{n-1}\right)\]which clearly satisfies \[ b_1+2b_2+\dots+(n-1)b_{n-1}=a_1+a_2+\dots+(n-1)a_{n-1}+(1+2+\dots+(n-1))\frac{2a_n}{n-1}=0.\quad \blacksquare \]

mavropnevma wrote: In fact, for $x=m+\varepsilon$, with $m$ a non-negative integer and $0\leq \varepsilon< 1/n$ we also have equality. Actually, the inequality holds for all real $x \ge 0$ such that $\frac{k-1}{n} \le \{ x \} < \frac{k}{n}$ where $k \le n$ is a positive integer and $\gcd (k,n)=1$. In my solution I use rearrangement inequality which leads to this equality.

let $[x]=m, x-[x]=l$ case 1: there exists $1\leq k \leq n-1$ such that ${1\over k+1}\leq l<{1\over k}$, note that $[xj]=mj+[jl]$, and: for $j=1,2...k: [jl]= 0$ for $j=k+1,...2k: [jl]=1$ . . . hence, if we let $n=tk+r$ where $0\leq r<k$, then: $RHS=mn+({1\over k+1}+...+{1\over 2k})+({2\over2k+1}+...+{2\over3k})+...+({t\over tk+1}+...+{t\over tk+r})$ it can be checked that each of the summations above is $\leq1$ and at least one is $<1$. hence : $RHS< mn +t$, however, $LHS=mn+[nl]$, and ${tk+r\over k+1}\leq nl\leq {tk+r\over k}$ with $0\leq r<k$ thus $LHS=mn+t> RHS$ as desired. case 2: $0\leq l<{1\over n}$ using a similar argument to the latter, one can prove $RHS=LHS=mn$.

Binomial-theorem wrote: If $x$ is a positive real number, and $n$ is a positive integer, prove that \[\lfloor nx\rfloor > \frac{\lfloor x\rfloor}1 + \frac{\lfloor 2x\rfloor}2 +\frac{\lfloor 3x\rfloor}3 + \cdots + \frac{\lfloor nx\rfloor}n.\]

http://www.artofproblemsolving.com/community/c6h1302311p6989779: Let $A_n=\sum_{k=1}^n \frac{\lfloor kx\rfloor}{k}$, suppose that $A_n\leq \lfloor nx\rfloor$ is true for all real number $x$ for all $n=1,2,...,m$ We have $(m+1)A_{m+1}=\sum_{i=1}^{m+1}{\lfloor ix\rfloor} +\sum_{i=1}^{m}{\frac{m+1-i}{i}\lfloor ix\rfloor} =\sum_{i=1}^{m+1}{\lfloor ix\rfloor} +\Big( A_1+A_2+...+A_m \Big) \leq \sum_{i=1}^{m+1}{\lfloor ix\rfloor} +\sum_{i=1}^{m}{\lfloor ix \rfloor} =\lfloor (m+1)x\rfloor +2\sum_{i=1}^{m}{\lfloor ix\rfloor} =\lfloor (m+1)x\rfloor +\sum_{i=1}^{m}{\Big( \lfloor ix\rfloor +\lfloor (m+1-i)x\rfloor \Big)} \leq \lfloor (m+1)x\rfloor +\sum_{i=1}^{m}{\lfloor (m+1)x\rfloor} =(m+1)\lfloor (m+1)x\rfloor $, so this complete induction step and we are done.

Any solution with Abel summation? I hear rumor that we can solve with this method...

And any with Hermite's identity?!

A solution via Abel's Summation We have \begin{align*} &\frac{\lfloor x \rfloor}{1}+\frac{\lfloor 2x \rfloor}{2}+\cdots +\frac{\lfloor nx \rfloor}{n} \\ =& \left( \lfloor x \rfloor + \lfloor 2x \rfloor + \cdots \lfloor nx \rfloor\right) \left(\frac{1}{n}\right)+\sum_{k=1}^{n-1} \left( \lfloor x \rfloor + \lfloor 2x \rfloor + \cdots \lfloor kx \rfloor\right) \left(\frac{1}{k}-\frac{1}{k+1}\right) \\ \leq &\lfloor x+2x+\cdots +nx \rfloor \left(\frac{1}{n}\right)+\sum_{k=1}^{n-1} \left(\lfloor {x+2x+\cdots +kx} \rfloor \right)\left(\frac{1}{k(k+1)}\right)\\ =&\frac{1}{n}\lfloor {\frac{n(n+1)}{2}} \rfloor+ \sum_{k=1}^{n-1} \frac{1}{k(k+1)} \lfloor {\frac{k(k+1)}{2}x} \rfloor \\ \leq & \lfloor {\frac{n+1}{2}x} \rfloor+ \sum_{k=1}^{n-1} \lfloor {\frac{1}{2}x} \rfloor \\ \leq & \lfloor {\frac{n+1}{2}x} \rfloor+ \lfloor {\frac{n-1}{2}x} \rfloor\\ \leq & \lfloor {nx} \rfloor . \blacksquare \end{align*}

you could use induction

\begin{align*} =&\frac{1}{n}\lfloor {\frac{n(n+1)}{2}x} \rfloor+ \sum_{k=1}^{n-1} \frac{1}{k(k+1)} \lfloor {\frac{k(k+1)}{2}x} \rfloor \\ \leq & \lfloor {\frac{n+1}{2}x} \rfloor+ \sum_{k=1}^{n-1} \lfloor {\frac{1}{2}x} \rfloor \\ \end{align*} I think this is a mistake? It's the reverse of $\lfloor x + y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor. $