# How to prove that $a<S_n-[S_n]<b$ infinitely often

Let $S_n=1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}$, where $n$ is a positive integer. Prove that for any real numbers $a,b,0\le a\le b\le 1$, there exist infinite many $n\in\mathbb{N}$ such that $$a<S_n-[S_n]<b$$ where $[x]$ represents the largest integer not exceeding $x$.

This problem is from China 2012 China Second Round (High school math competition) competition last problem, I think this problem has more nice methods, maybe using analytic methods.

-
HINT: Density of $\mathbb{Q}$ in $\mathbb{R}$ –  Don Larynx Sep 29 '13 at 7:55
@DonLarynx, not all rational numbers are of the form $S_n-[S_n]$. –  njguliyev Sep 29 '13 at 10:47
By $a\le b$ you mean $a\lt b$, right? –  bof Oct 16 '13 at 12:47

I think the direct approach works pretty well here.

Let $N > \max(a^{-1},( b - a ) ^ {-1})$, so that $S_{n+1} - S_{n} < ( b - a )$ and $S_{n+1} - S_{n} < a$ when $n > N$. Now suppose there are only finitely many $n$ with the desired property, and increase $N$ so that it's larger than the greatest index for which the property holds. Finally, let $n_{0} > N$ be smallest such that $a <S_{n_0 + 1} - \lfloor S_{n_0 + 1} \rfloor$. Then $\lfloor S_{n_0} \rfloor = \lfloor S_{n_0 + 1} \rfloor$ and $a > S_{n_0} - \lfloor S_{n_0} \rfloor$ since $S_{n_0 + 1} - S_{n_0} = \frac{1}{n_0 + 1} < a$. Then we also have $S_{n_0+1} - \lfloor S_{n_0 + 1} \rfloor < b$ since $$b > a + \frac{1}{n_0 + 1} > S_{n_0} - \lfloor S_{n_0 } \rfloor + \frac{1}{n_0+1} = S_{n_0 + 1} - \lfloor S_{n_0 + 1} \rfloor$$ Which means we've found another index where the property holds, contradicting the assumption that $N$ is larger than the largest index for which the property holds.

-

Let $i\geqslant1/(b-a)$ and $k=\lceil S_i\rceil$. Since the sequence $(S_j)_{j\geqslant1}$ is unbounded, some values of this sequence are greater than $k+a$, hence $n=\min\{j\mid S_j\gt k+a\}$ is well defined and finite. Then $S_{n-1}\leqslant k+a\lt S_{n}$ and $n\gt i$ since $S_i\lt k+a$ hence $$S_{n}=S_{n-1}+1/n\lt k+a+1/i\leqslant k+b.$$ Thus, $k+a\lt S_{n}\lt k+b$, in particular, $\lfloor S_{n}\rfloor=k$ and $a\lt S_{n}-\lfloor S_{n}\rfloor\lt b$.

For every $i$ large enough, this provides some $n\gt i$ such that $a\lt S_{n}-\lfloor S_{n}\rfloor\lt b$. To get infinitely many indexes $n$ such that $a\lt S_{n}-\lfloor S_{n}\rfloor\lt b$, just iterate the construction.

This approach works for every unbounded sequence $(S_n)_n$ such that $S_{n+1}-S_n\to0$.

-

Since $H_n = \log n +\gamma + O\left(\frac{1}{n}\right)$, it is sufficient to prove the density of the sequence $\{\log n\pmod{1}\}_{n>1}$ in $[0,1]$. But since $\sum_{n=1}^{+\infty}\log\left(\frac{n+1}{n}\right)$ diverges, there must be an element of the sequence in every sub-interval of $[0,1]$: otherwise, take an accumulation point of the sequence (it must exist, because $\{\log n\pmod{1}\}_{n>1}$ is a sequence of distinct real numbers, since all the numbers of the form $e^m$ with $m\in\mathbb{N}_0$ are irrational) and slowly move towards the right ($\log N\rightarrow \log(N+1)\rightarrow\ldots$, with the possibility to choose $N$ arbitrarily big) until falling into the chosen sub-interval.

-

since $$S_{2^n}=1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}+\cdots+\dfrac{1}{2^n}>1+\dfrac{1}{2}+\left(\dfrac{1}{2^2}+\dfrac{1}{2^2}\right)+\cdots+\left(\dfrac{1}{2^n}+\cdots+\dfrac{1}{2^n}\right)$$ so $$S_{2^n}>\dfrac{1}{2}n$$

-
This is true, but doesn't prove the "density" result the OP is looking for. –  Callus Oct 16 '13 at 7:59