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

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?

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

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

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

• Nice! (Probably a tad overkill given the specific OP's question, but in general -- pretty neat.) – Clement C. Nov 7 '17 at 17:57
• Very interesting! How does one get the higher order terms (e.g. the red term)? – angryavian Nov 7 '17 at 18:18
• @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]$. – Jack D'Aurizio Nov 7 '17 at 18:27
• @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? – Clement C. Nov 7 '17 at 18:27
• @ClementC.: you are right, $\frac{1}{\sqrt{2}}-\frac{1}{2}=\frac{1}{2+2\sqrt{2}}$, now fixed. – Jack D'Aurizio Nov 7 '17 at 18:29