<s>[INST] Sum of $\{n\sqrt{2}\}$ I would like to prove (rigorously, not intuitively) that
$$\sum_{n=1}^N \{n\sqrt{2}\}=\frac{N}{2}+\mathcal{O}(\sqrt{N})$$
where $\{\}$ is the "fractional part" function. I understand intuitively why this is true, and that's how I came up with this claim - $\{n\sqrt{2}\}$ behaves like a random variable uniformly distributed in $(0,1)$, and treating it as a random variable makes the sum analogous to a random walk, and the $\mathcal{O}(\sqrt{N})$ bound can be shown using expected values. 
However, just saying that $\{n\sqrt{2}\}$ behaves "like a random variable" is highly non-rigorous. Can someone show me how to justify this in a more airtight way (ideally without using any theorems that require specialized background knowledge)?
Thanks!
 [/INST] Writing
\begin{align}
&\quad \sum_{n=1}^N \left( n\sqrt{2} - \lfloor n\sqrt{2} \rfloor \right) \\
&=\int_1^N \left( n\sqrt{2} - \lfloor n\sqrt{2} \rfloor \right) {\rm d}n + {\cal O}(1) \tag{1} \\
&=\frac{1}{\sqrt{2}} \int_\sqrt{2}^{\sqrt{2}N} \left(x- \lfloor x \rfloor \right) {\rm d}x + {\cal O}(1)  \\
&=\frac{1}{\sqrt{2}} \Bigg( N^2 - 1 - \Bigg[ \frac{\sqrt{2}N \left(\sqrt{2}N-1\right)}{2} + \frac{\left\{\sqrt{2}N\right\} \left(1-\left\{\sqrt{2}N\right\}\right)}{2} \\
&\quad - \frac{\sqrt{2} \left(\sqrt{2}-1\right)}{2} - \frac{\left\{\sqrt{2}\right\} \left(1-\left\{\sqrt{2}\right\}\right)}{2} \Bigg] \Bigg) + {\cal O}(1) \\
&=\frac{N}{2} + {\cal O}(1)
\end{align}
where we used
$$
\int_0^x \lfloor t \rfloor \, {\rm d}t = \frac{x(x-1)}{2} + \frac{\left\{x\right\}\left(1-\left\{x\right\}\right)}{2} \, .
$$
The order follows from the fact that
$$
\frac{\left( \sqrt{2}N - \lfloor \sqrt{2}N \rfloor \right) + \left( \sqrt{2} - \lfloor \sqrt{2} \rfloor \right)}{2} = {\cal O}(1) \tag{2}
$$
and
$$\int_1^{N} \left( n\sqrt{2} - \lfloor n\sqrt{2} \rfloor \right)'' {\rm d}n \tag{3} \\
= \left( \sqrt{2}n - \lfloor \sqrt{2}n \rfloor \right)'\big|_{n=N} - \left( \sqrt{2}n - \lfloor \sqrt{2}n \rfloor \right)'\big|_{n=1} \\
=\sqrt{2} \sum_{k=-\infty}^{\infty}\left[ \delta\left( \sqrt{2} - k   \right) - \delta\left( \sqrt{2}N - k  \right) \right]
$$
but this requires Euler-Maclaurin.

Due to the harsh critic about my somewhat heuristic argument I want to correct my approach as far as possible.
Set $$f(x)=x-\lfloor x \rfloor$$ and $$f_n(x)=\frac{1}{2} - \frac{1}{\pi} \sum_{k=1}^n \frac{\sin(2\pi k x)}{k} \, ,$$such that
$$
\lim_{n\rightarrow \infty} f_n(x) = f(x) \, .
$$
Since $f_n$ is differentiable we can use Euler-Maclaurin to calculate the sum
$$
\sum_{k=1}^N f_n(ak)
$$
with some $a$. The integral in (1) does not create much of an issue in the limit $n \rightarrow \infty$, since the limit is piecewise continuous and the integral can be splitted accordingly and then integrated. Also the limit of (2) is of ${\cal O}(1)$. So the problematic term which needs to be examined is the remainder $R_2$ ((3) was very heuristic) which can be written as
$$
R_2=\int_1^N B_2\left(t-\lfloor t \rfloor\right) \frac{\rm d}{{\rm d}t} f_n'(at) \, {\rm d}t
$$
neglecting unnecessary constants and $B_2$ is the second Bernoulli polynomial. We can express
\begin{align}
f_n'(at) &= 1-\sum_{k=-n}^{n} {\rm e}^{i2\pi k at} = 1 - \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \\
B_2\left(t-\lfloor t \rfloor\right) &= \left(t-\lfloor t \rfloor\right)(\left(t-\lfloor t \rfloor - 1\right) + \frac{1}{6} = \lim_{M \rightarrow \infty} \sum_{k=1}^M \frac{\cos(2\pi kt)}{\pi^2 k^2}
\end{align}
and integrate by parts
$$
R_2=-B_2\left(t-\lfloor t \rfloor\right) \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \Bigg|_{1}^{N} - 2 \sum_{k=1}^{M} \int_1^N   \frac{\sin(2\pi kt)}{\pi k}  \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \, {\rm d}t \tag{4} \, .
$$
For $a$ not an integer, the first term is bounded and ${\cal O}(1)$ as $n \rightarrow \infty$. The integral can be viewed as a functional for $n \rightarrow \infty$ in which case the Dirichlet kernel acts as a periodic delta-distribution $\sum_{m=-\infty}^{\infty} \delta(at-m)$
$$
\lim_{n \rightarrow \infty} \int_1^N   \frac{\sin(2\pi kt)}{\pi k}  \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \, {\rm d}t = \sum_{m=\lceil a \rceil}^{\lfloor Na \rfloor} \frac{\sin\left(\frac{2\pi km}{a}\right)}{\pi k a} \, .
$$
Evaluating
$$
\sum_{m=\lceil a \rceil}^{\lfloor Na \rfloor} \lim_{M\rightarrow\infty} -2\sum_{k=1}^{M} \frac{\sin\left(\frac{2\pi km}{a}\right)}{\pi k a} = \sum_{m=\lceil a \rceil}^{\lfloor Na \rfloor} \frac{2\{m/a\}-1}{a} \tag{5}
$$
and using $\sum_{n=1}^{N}\{an\} = \frac{N}{2} + {\cal O}(?)$
this becomes ${\cal o}(N)$. So it is actually true ${\cal O}(1)$ does not follow.

We continue with the integral in (4) for $N$ integer
\begin{align}
&\quad -2\sum_{k=1}^\infty \int_1^N   \frac{\sin(2\pi kt)}{\pi k}  \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \, {\rm d}t \\
&=-4\sum_{m=1}^n \sum_{k=1}^\infty \int_1^N \frac{\sin(2\pi kt)\cos(2\pi m a t)}{\pi k} \, {\rm d}t \\
&=\frac{4}{\pi^2} \sum_{m=1}^n \sum_{k=1}^\infty \frac{\cos^2(N\pi m a)-\cos^2(\pi ma)}{k^2-m^2 a^2} \\
&=2\sum_{m=1}^n \left[ \frac{\cos^2(N\pi m a)-\cos^2(\pi ma)}{\pi^2 m^2 a^2} - \frac{\cot(\pi ma)\left(\cos^2(N\pi ma) - \cos^2(\pi ma)\right)}{\pi ma} \right]
\end{align}
where $a$ must be an irrational number now. The first term is ${\cal O}(1)$ for $n\rightarrow \infty$.
Any idea for the second? 
It can be rewritten as
\begin{align}
&\quad \, \, \sum_{m=1}^n \frac{\cot(\pi ma)\left(\cos^2(N\pi m a) - \cos^2(\pi ma)\right)}{\pi ma} \\
&= \sum_{m=1}^n \frac{\cot(\pi ma)\left(\cos(N2\pi ma) - \cos(2\pi ma)\right)}{2\pi ma} \\
&= - \sum_{m=1}^{n}\cos(m\pi a) \, \frac{\sin\left((N+1)m\pi a\right)}{m\pi a} \, \frac{\sin\left((N-1)m\pi a\right)}{\sin(m\pi a)} \\
&= - \sum_{m=1}^{n} \frac{\sin\left((N+2)m\pi a\right)}{m\pi a} \, \frac{\sin\left((N-1)m\pi a\right)}{\sin(m\pi a)} + \sum_{m=1}^n \frac{ \sin\left(N2\pi ma\right) - \sin\left(2\pi ma\right) }{2\pi ma}
\end{align}
so the second sum is bounded again $\forall N$ and $n \rightarrow \infty$.
Not sure if it helps, but I have the following two identities for the sines
$$
\frac{\sin\left((N-1)nx\right)}{\sin(nx)} = \sum_{l=2}^N \cos\left((N-l)nx\right) \cos^{l-2}(nx) 
$$
and
$$
\frac{\sin\left((N-1)nx\right)}{\sin(nx)} = 1+2\sum_{l=1}^{\frac{N}{2}-1} \cos\left(l2nx\right) \, ,
$$
but evaluating this feels as if I'm running in circles.
I added a Figure of the RHS of (5) up to $N=10^6$ which doesn't look anything like $\log$, so either the numbers are just too small or I dont why it has to be $\log$.

</s>