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

  • 2
    $\begingroup$ 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)$? $\endgroup$ – Michael Chen May 28 '11 at 1:26
  • 4
    $\begingroup$ @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)$ $\endgroup$ – Eric Naslund May 28 '11 at 1:32
  • 1
    $\begingroup$ Aha! Thank you. I assume that in general, $f(n) O(g(n)) = O(f(n)g(n))$? $\endgroup$ – Michael Chen May 28 '11 at 11:39
  • 2
    $\begingroup$ Yes, by the very definition of the big O notation. $\endgroup$ – Najib Idrissi May 28 '11 at 19:20
  • 3
    $\begingroup$ 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. $\endgroup$ – 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.

  • 8
    $\begingroup$ 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. $\endgroup$ – N. S. May 29 '11 at 1:24
  • 1
    $\begingroup$ @user9176: Aha! Then I would not have needed my way of showing the lower bound (which I thought was a little shaky/kludgy). $\endgroup$ – 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}.$$

  • 2
    $\begingroup$ Haha nice one the integral trick. We don't use this really often. $\endgroup$ – Patrick Da Silva May 29 '11 at 5:45
  • 1
    $\begingroup$ 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}.$$ $\endgroup$ – 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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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