Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 29 down vote accepted

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$.

share|cite|improve this answer
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 '15 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.

share|cite|improve this answer
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}.$$

share|cite|improve this answer
Haha nice one the integral trick. We don't use this really often. – Patrick Da Silva May 29 '11 at 5:45
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.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.