1
$\begingroup$

Find this limit:

$\lim_{n \rightarrow +\infty}{\frac{\sum_{i=1}^{n} \lfloor{i \sqrt{2}}\rfloor}{n^2}}$

It is like that we want to find the limit of the sequence $\frac{[\sqrt2] +[2\sqrt2] + ... + [n\sqrt2]}{n^2} $ at infinity.

At the first glance, It seem it should be like $0$ but I somewhere read that its limit is $\frac{\sqrt2}{2}$ or something like that. I know that it must be something other than zero but is it right that its limit is $\frac{\sqrt2}{2}$? If yes how? and if it is not, then what is its limit at infinity?

$\endgroup$
5
$\begingroup$

For every $i$, you have by definition of the floor function $$ i\sqrt{2} - 1\leq \lfloor i\sqrt{2}\rfloor\leq i\sqrt{2} \tag{1} $$ From this, summing for $i$ ranging from $1$ to $n$ and dividing by $n^2$, $$ \sqrt{2}\sum_{i=1}^n \frac{i}{n^2} - \frac{n}{n^2} \leq \sum_{i=1}^n \frac{\lfloor i\sqrt{2}\rfloor}{n^2} \leq \sqrt{2}\sum_{i=1}^n \frac{i}{n^2} \tag{2} $$ and recalling that $\sum_{i=1}^n i = \frac{n(n+1)}{2}$, we get $$ \sqrt{2}\frac{(n+1)}{2n} - \frac{1}{n} \leq \sum_{i=1}^n \frac{\lfloor i\sqrt{2}\rfloor}{n^2} \leq \sqrt{2}\frac{(n+1)}{2n}\,. \tag{3} $$ By the squeeze theorem, the limit is therefore $$ \boxed{\lim_{n\to\infty }\sum_{i=1}^n \frac{\lfloor i\sqrt{2}\rfloor}{n^2} = \frac{\sqrt{2}}{2}\,.} $$

$\endgroup$
2
$\begingroup$

If you do not have the floor function, then the result follows easily from the identity $\sum_{i=1}^n i = n(n-1)/2$. $$\frac{\sum_{i=1}^n (i \sqrt{2})}{n^2} = \sqrt{2} \frac{\frac{n(n-1)}{2}}{n^2} \to \frac{\sqrt{2}}{2}.$$


The idea is that the floor function does not really change much, and will have the same behavior in the limit.

To show this rigorously, find two functions $f$ and $g$ such that $$f(n) \le \frac{\sum_{i=1}^n \lfloor i \sqrt{2} \rfloor}{n^2} \le g(n)$$ for all $n$, and such that $f$ and $g$ both tend to $\sqrt{2}/2$ in the limit.

Hint: I already found $g$ for you.

Take $g=\frac{\sum_{i=1}^n (i \sqrt{2}) }{n^2}$ and $f = \frac{\sum_{i=1}^n (i\sqrt{2} - 1)}{n^2}$.

$\endgroup$
2
$\begingroup$

Since $\sqrt{2}\not\in\mathbb{Q}$, the fractional part $\{k\sqrt{2}\}$ is equidistributed $\!\!\pmod{1}$. In particular

$$ \sum_{k=1}^{n}\lfloor k\sqrt{2}\rfloor = \sqrt{2}\,\frac{n(n+1)}{2}-\sum_{k=1}^{n}\{k\sqrt{2}\}=\frac{1}{\sqrt{2}}n(n+1)-\frac{n}{2}+o(n)$$ and we even know the second term of the asymptotic expansion:

$$ \frac{1}{n^2}\sum_{k=1}^{n}\lfloor k\sqrt{2}\rfloor = \frac{1}{\sqrt{2}}+\color{red}{\frac{1}{(2+2\sqrt{2})n}}+o\left(\frac{1}{n}\right).$$

$\endgroup$
  • $\begingroup$ Nice! (Probably a tad overkill given the specific OP's question, but in general -- pretty neat.) $\endgroup$ – Clement C. Nov 7 '17 at 17:57
  • $\begingroup$ Very interesting! How does one get the higher order terms (e.g. the red term)? $\endgroup$ – angryavian Nov 7 '17 at 18:18
  • 1
    $\begingroup$ @angryavian: the other terms depend on the discrepancy of the sequence of fraction parts. To compute them one has to investigate the structure of the continued fraction of $\sqrt{2}$, which luckily is fairly simple, $\sqrt{2}=[1;2,2,2,2,2,\ldots]$. $\endgroup$ – Jack D'Aurizio Nov 7 '17 at 18:27
  • 1
    $\begingroup$ @angryavian from the previous line: you have $$\frac{n^2}{\sqrt{2}}+\frac{n}{\sqrt{2}} - \frac{n}{2} + o(n)$$ so after dividing by $n^2$ you get $$\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}n} - \frac{1}{2n} + o\left(\frac{1}{2}\right)$=\frac{1}{\sqrt{2}}+\frac{1}{(2+2\sqrt{2})n}+ o\left(\frac{1}{n}\right)$$ I am assuming there may be a typo in the answer? $\endgroup$ – Clement C. Nov 7 '17 at 18:27
  • 1
    $\begingroup$ @ClementC.: you are right, $\frac{1}{\sqrt{2}}-\frac{1}{2}=\frac{1}{2+2\sqrt{2}}$, now fixed. $\endgroup$ – Jack D'Aurizio Nov 7 '17 at 18:29

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.