21
$\begingroup$

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

4 Answers 4

30

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
    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](http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition)). Can you explain why the righthand side of your first equation is $O(1/n)$ and not $O(1/n^2)$?2011-05-28
  • 4
    @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)$2011-05-28
  • 1
    Aha! Thank you. I assume that in general, $f(n) O(g(n)) = O(f(n)g(n))$?2011-05-28
  • 2
    Yes, by the very definition of the big O notation.2011-05-28
  • 3
    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.2015-08-16
15

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
    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.2011-05-29
  • 1
    @user9176: Aha! Then I would not have needed my way of showing the lower bound (which I thought was a little shaky/kludgy).2011-05-29
12

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
    Haha nice one the integral trick. We don't use this really often.2011-05-29
  • 1
    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}.$$2011-05-29
4

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