# How to show $\lim_{n \to \infty} a_n = \frac{ [x] + [2x] + [3x] + \dotsb + [nx] }{n^2} = x/2$?

This question came from the prelim exam I took last month. I have a proof that seems a bit unwieldy to me (posted as an answer), so I'm opening it up to ask if there are other ways of showing this.

Let $x$ be any positive real number, and define a sequence $\{a_n\}$ by $$a_n = \frac{ [x] + [2x] + [3x] + \dotsb + [nx] }{n^2}$$ where $[x]$ is the largest integer less than or equal to $x$. Prove that $\displaystyle{\lim_{n \to \infty} a_n = x/2}$.

-

Since $[x]=x+O(1)$ we see that $$\frac{[x]+[2x]+\cdots+[nx]}{n^2}=\frac{x+2x+\cdots+nx}{n^2}+O\left(\frac{1}{n}\right).$$ Summing, since $x$ is a fixed constant, this becomes $$\frac{x}{2}+O\left(\frac{1}{n}\right)$$ which converges to $\frac{x}{2}$ as $n\rightarrow \infty$.

-
I just gave myself a crash course in Big O notation, so I think I understand what's going on (at least, the general limit definition through the Wikipedia article). Can you explain why the righthand side of your first equation is $O(1/n)$ and not $O(1/n^2)$? –  Michael Chen May 28 '11 at 1:26
@Michael: Of course. Each term in the numerator contributes $O(1)$, but there are $n$ terms so we get $O(n)$. Dividing this by $n^2$ yields $O\left(\frac{1}{n}\right)$ –  Eric Naslund May 28 '11 at 1:32
Aha! Thank you. I assume that in general, $f(n) O(g(n)) = O(f(n)g(n))$? –  Michael Chen May 28 '11 at 11:39
Yes, by the very definition of the big O notation. –  Najib Idrissi May 28 '11 at 19:20
Your comment is actually misleading. It is not enough that each term contributes $O(1)$. It must be uniform $O(1)$. The better way would be to use an explicit bound of $[0,1]$ for each contribution. –  user21820 Aug 16 at 8:37

Proof by squeeze theorem, by establishing upper and lower bounds for the limit.

Upper Bound: Since $[x] \leq x$, then

\begin{align*} a_n &= \frac{ [x] + [2x] + [3x] + \dotsb + [nx] }{n^2} \\ &\leq \frac{x + 2x + 3x + \dotsb + nx}{n^2} \\ &\leq \frac{\left( \sum_{i=1}^n i \right) x}{n^2} = \left( \sum_{i=1}^n i \right) \frac{x}{n^2} = \frac{n(n+1)}{2} \frac{x}{n^2} = \frac{n(n+1)x}{2n^2} \end{align*}

Taking $n \to \infty$, then $$\lim_{n \to \infty} a_n \leq \lim_{n \to \infty} \frac{n(n+1)x}{2n^2} = \frac{x}{2}.$$

Lower Bound: consider $x=1/m$. For $km \leq n < (k+1)m$, where $k \in \mathbb{N}$, minimize the numerator and maximize the denominator (since $x$ is positive) to get: $$a_n \geq \frac{\left(\sum_{i=1}^{k-1} i\right)m}{((k+1)m)^2} = \frac{(k-1)k}{2(k+1)^2m}$$

Taking limits,

\begin{align*} \lim_{n \to \infty} a_n &\geq \lim_{n \to \infty} \frac{(k-1)k}{2(k+1)^2m} \\ &\geq \frac{1}{2m}. \end{align*}

Since limits respect sums, then this lower bound holds for any sum of fractions of the form $1/m$. Any positive real number $x$ can be written as a (possibly) infinite series where the terms are of the form $1/m$ and are monotonically decreasing. (This is true since $1/n \to 0$ but $\sum 1/n \to \infty$. For example, $\pi = 1/1 + 1/1 + 1/1 + 1/8 + 1/61 + \dotsb$. Incidentally, this representation is also not necessarily unique.) Taking the limit of partial sums of this series, the lower bound to $\lim_{n \to \infty} a_n$ approaches $x/2$.

Therefore by the squeeze theorem, since $x/2$ is both a lower and upper bound to $\lim_{n \to \infty} a_n$, then $x/2$ is the limit.

-
By using $x-1 \leq [x] \leq x$ you can get at once $\frac{x + 2x + 3x + \dotsb + nx -n}{n^2} \leq a_n \leq \frac{x + 2x + 3x + \dotsb + nx}{n^2}$ in your upper bound computation. –  N. S. May 29 '11 at 1:24
@user9176: Aha! Then I would not have needed my way of showing the lower bound (which I thought was a little shaky/kludgy). –  Michael Chen May 29 '11 at 4:44

As @user9176 says, you get $$\frac{x+2x+3x+\ldots +nx-n}{n^2}\leq a_n\leq \frac{x+2x+3x+\ldots +nx}{n^2},$$ for all $n\in \mathbb{N}$. It's clear that the limits of the extremes of the inequality are equal. Calculate the right: \begin{align*} \lim_{n\to \infty} \frac{x+2x+3x+\ldots +nx}{n^2} &= \lim_{n\to \infty} \sum _{k=1}^{n} \frac{1}{n}\cdot \frac{k}{n}x\\ &= \lim_{n\to \infty} \sum _{k=1}^{n} \frac{1-0}{n}\cdot \left( 0 + \frac{(1-0)k}{n} \right)x\\ &= \int_0 ^1 tx \text{ dt}\\ &= \frac{x}{2}. \end{align*} Then $$\frac{x}{2}\leq \lim_{n\to \infty} a_n\leq \frac{x}{2}.$$

-
Haha nice one the integral trick. We don't use this really often. –  Patrick Da Silva May 29 '11 at 5:45
The lower bound of $a_n$ you start from is not correct (and not what user9176 said). –  Did May 29 '11 at 14:26
This is snazzy. Thanks! @Didier Piau: I just suggested an edit to fix that; I believe the lefthand side should otherwise behave the same way as the right one when taking the limit. –  Michael Chen May 29 '11 at 18:01
Yep, I'll fix it @Didier. –  leo May 29 '11 at 18:34
The limits remain the same, because $$\frac{x+2x+3x+\ldots +nx-n}{n^2}-\frac{x+2x+3x+\ldots +nx}{n^2}=-\frac{1}{n}.$$ –  leo May 29 '11 at 18:42

By definition of the floor function,

$$kx-1\le\lfloor kx\rfloor\le kx.$$

Then summing on $k$ from $1$ to $n$,

$$\frac{n(n+1)}2x-n\le\sum_{k=1}^n \lfloor kx\rfloor\le \frac{(n+1)n}2x.$$

Dividing by $n^2$ and taking the limit,

$$\frac x2\le\frac1{n^2}\sum_{k=1}^\infty \lfloor kx\rfloor\le \frac x2.$$

-