Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers 3

up vote 26 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|improve this answer
1  
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
3  
@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
1  
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
2  
Yes, by the very definition of the big O notation. –  Najib Idrissi May 28 '11 at 19:20
add comment

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|improve this answer
7  
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
1  
@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
add comment

As say @user9176, 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|improve this answer
2  
Haha nice one the integral trick. We don't use this really often. –  Patrick Da Silva May 29 '11 at 5:45
2  
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
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}.$$ –  leo May 29 '11 at 18:42
add comment

Your Answer

 
discard

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.