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

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

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

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